1. 题目与适用场景
数据流中的每条记录都有正权重，但总条数和总权重未知。请实现容量为 k 的无放回带权样本：每条记录最多出现一次，记录进入最终样本的机会与其权重成正比，算法只能单次扫描数据流。说明随机 key 的构造、如何维护候选集、如何处理极端权重，以及怎样测试分布是否正确。
2. 面试官考察点
- 是否区分有放回和无放回抽样，并理解“概率与权重成正比”的定义。
- 是否能用随机优先级或指数变量把带权抽样转化为保留 top-k key。
- 是否选择大小为
k的最小堆，给出单条记录的O(log k)更新时间。 - 是否处理权重为零、极大或极小、随机数边界、重复 ID 和可复现种子。
3. 回答前需要澄清的问题
- 权重是否保证为有限的正数，零权重要丢弃还是保留？
- 需要无放回样本还是允许同一记录多次出现？
- 只要求最终样本，还是每个前缀都要保持正确分布？
- 是否需要合并多个分片、持久化状态或提供可复现的随机结果？
4. 30 秒回答框架
对每条权重为 w 的记录生成独立随机 key，并保留最大的 k 个 key。一个稳定做法是抽取 u 属于 (0, 1] 的均匀随机数，计算 key = log(u) / w；因为值为负，等价于保留最接近零的 k 个 key。使用大小为 k 的最小堆保存当前样本，堆顶是最小 key；新 key 更大时替换堆顶。单次扫描时间 O(n log k)，空间 O(k)，权重必须先校验，随机源要可测试。
5. 分步骤深入解答
第一步：明确分布目标
无放回带权抽样不是独立地按 w / total 选择 k 次，因为那会产生重复记录。目标是从所有记录中抽出大小为 k 的集合，其顺序统计分布等价于依次从尚未抽中的记录按剩余权重抽取。算法必须让每个前缀都能解释为当前数据的样本，而不是等读完整个流后再回放。
第二步：生成数值稳定的随机 key
指数竞赛给出一种方便实现：从均匀随机数 u 生成 key = log(u) / w，再选最大的 key。u 越接近零，log(u) 越负；更大的权重使 key 更接近零，因此更容易进入 top-k。不要直接计算 u ** (1 / w)，极大或极小权重可能导致下溢或失去区分度。
sample_key(weight):
require finite(weight) and weight > 0
u = uniform_random_open_interval()
return log(u) / weight第三步：用最小堆维护 top-k
堆中保存 (key, sequence, item)，其中 sequence 用来打破完全相同的 key。样本未满时直接入堆；样本已满时比较新 key 与堆顶，只有更大才替换。若 k 为零则直接丢弃所有记录。不要用排序数组在每条记录后重新排序，否则更新时间会变成 O(k log k)。
第四步：处理输入和随机性边界
拒绝 NaN、无穷和负权重；零权重记录不会被正权重样本选中，可直接跳过。随机源应避免返回零，否则 log(0) 不可用；可以把零重抽或钳制到最小正浮点数。重复 ID 仍按记录出现次数处理，除非题目明确要求按 ID 去重。测试时注入伪随机源，让失败样本可复现。
第五步：复杂度、验证与分布式扩展
n 条记录的单机实现时间为 O(n log k)，额外空间为 O(k)。用固定权重的模拟检验边际频率是否随权重上升，并检查样本没有重复。分布式场景可以让每个分片生成同一规则的 key，再在协调器合并各分片的 top-k；但需要明确随机种子、分片状态、更新删除和通信成本，不能简单把各分片样本再次均匀抽样。
6. 高质量示范回答
我会为每条正权重记录生成key = log(u) / w，其中u是开区间上的均匀随机数，然后保留最大的k个 key。因为 key 为负，权重越大越容易接近零。用容量为k的最小堆保存样本，堆顶是当前最小 key；新 key 更大时替换堆顶。权重非法、随机数为零、k 为零和重复记录都要有明确规则。扫描n条记录的时间是O(n log k)，空间是O(k)；用蒙特卡洛频率和无重复断言验证分布，分布式时按相同 key 规则合并 top-k。
7. 常见错误
- 每次按
w / total独立抽取 → 产生重复且不是无放回分布 → 使用随机 key 的 top-k 方法。 - 直接计算
u ** (1 / w)→ 极端权重下数值下溢 → 使用对数形式比较 key。 - 用最大堆保存 top-k → 还要遍历堆找最小值 → 使用最小堆让替换点在堆顶。
- 允许
u = 0→log(0)变成负无穷 → 使用开区间随机源或重抽。 - 只测试一组输出 → 看不出长期偏差 → 做固定权重的多轮模拟并检查无重复。
8. 追问及应对
追问一：为什么 key = log(u) / w 能按权重抽样？
把 -log(u) 看作速率为 1 的指数变量后，除以权重相当于得到速率为 w 的指数变量。最小的指数时间最可能来自更大的速率；把符号取反后就是保留最大的 key，因此 top-k 对应无放回的带权抽样。
追问二：如何支持可复现结果？
注入带显式种子的伪随机源，并把记录唯一标识、权重版本和算法版本纳入实验元数据。不要依赖线程调度或全局随机状态，否则同一输入可能得到不同样本。
追问三：可以合并两个已经生成的 reservoir 吗？
如果两个分片对各自记录使用独立且同分布的 key，可以把两边候选的 key 合并并取全局 top-k；直接把两个最终样本当作普通数据再次抽样会丢失被淘汰记录的信息。还要处理分片增量、删除和键的持久化。
追问四：权重随时间变化怎么办？
权重变化会改变抽样分布，旧 key 不能继续代表新权重。可以重新生成受影响记录的 key，或把权重版本作为新事件重新进入流；更新策略要说明是否接受短暂近似，以及如何回收旧样本。