算法 | GoCalf

单次遍历，带权随机选取问题（二）

本文介绍一个有趣的算法，用来解决带权随机选取问题：有一组数量未知的数据，每个元素有非负权重。要求只遍历一次，随机选取其中的一个元素，任何一个元素被选到的概率与其权重成正比。

发表于 2011年9月26日 interview question probability random sample 算法

问题描述：有一组数量未知的数据，每个元素有非负权重。要求只遍历一次，随机选取其中的一个元素，任何一个元素被选到的概率与其权重成正比。

发表于 2011年9月21日 interview question probability random sample 算法

问题描述：假设我们有一堆数据（可能在一个链表里，也可能在文件里），数量未知。要求只遍历一次这些数据，随机选取其中的一个元素，任何一个元素被选到的概率相等。O(n) 时间，O(1) 辅助空间（n 是数据总数，但事先不知道）。

发表于 2011年9月6日 interview question probability random sample 算法

问题描述：假设有一个数组，包含 n 个元素。现在要重新排列这些数据，要求每个元素被放到任何一个位置的概率都相等（即 1/n），并且直接在数组上重排（in place），不要生成新的数组。用 O(n) 时间、O(1) 辅助空间。

发表于 2011年9月1日 interview question probability 算法

问题描述：给定一个由 n 个各不相等的元素构成的循环有序数组（Circularly Ordinal Array），用 O(log n) 时间、O(1) 辅助空间在其中查找指定的元素。

发表于 2011年8月19日 interview question lookup algorithm 算法

问题描述：现在有一个叫做 Rand5 的函数，可以生成等概率的 [0, 5) 范围内的随机整数，要求利用此函数写一个 Rand3 函数（除此之外，不能再使用任何能产生随机数的函数或数据源），生成等概率的 [0, 3) 范围内的随机整数。

发表于 2011年8月2日 probability interview question 算法