题干与适用场景
输入是只能顺序读取一次的数据流，长度 n 事先未知，目标是等概率选出 k 个不同元素。不能先把全部元素放进数组，也不能等读完后再随机选下标。Reservoir Sampling 用固定大小为 k 的 reservoir 解决这个约束：第 i 个元素到达时，以 k/i 的概率让它进入样本，并随机替换当前样本中的一个位置。
这道题考察随机化流式算法。Vitter 的论文研究了未知总长度的单次抽样，大学课程资料给出了均匀性归纳证明。核心分类是 coding，考察概率不变量与空间约束，不因应用于日志或数据平台改成 data。
面试官考察点
- 能否从“未知 n、单遍、固定内存”识别 reservoir pattern。
- 能否先讲清
k=1的1/i替换概率，再推广到k。 - 能否证明处理完第
i个元素后，每个元素入样概率都是k/i。 - 能否避免重复抽样、错误的
k/n预知假设和有偏随机数。 - 能否说明时间
O(n)、空间O(k)与加权抽样的边界。
回答前需要澄清的问题
k是否为正整数？若k <= 0或超过流长度，返回约定是什么？- 元素是否可重复？“不同元素”是不同记录还是按值去重，必须先定义。
- 流是否可能为空、无限长或中途失败？输出与可恢复策略不同。
- 需要最终样本还是实时查看当前样本？实时查看不能改变均匀性证明。
- 随机数生成器是否提供
[0,1)或无偏整数？不能直接假设取模无偏。 - 抽样是否带权或需要分层？加权目标不再是等概率 reservoir。
30 秒回答框架
“先处理前 k 个元素填满 reservoir。第 i 个元素（从 1 开始）到达后生成均匀整数 j，范围 [0, i-1]；若 j < k，就用新元素替换 reservoir[j]，否则丢弃。这样处理完 i 个元素后，每个元素都以 k/i 的概率在样本中：新元素直接以 k/i 进入，旧元素以 k/(i-1) 留存并乘以 1 - 1/i。单遍时间 O(n)，空间 O(k)。”
分步骤深入解答
第一步：从 k=1 开始。
第一个元素必选；第 i 个元素以 1/i 的概率替换当前候选。处理完 i 个元素后，每个元素的留存概率相同，都是 1/i。
第二步：推广到 k 个。
前 k 个元素先填入 reservoir。之后第 i 个元素以 k/i 的概率进入；一旦进入，在 k 个槽位中均匀选择一个替换。用整数随机数 j ∈ [0, i-1] 实现时，j < k 就替换槽位 j。
第三步：写出伪代码。
reservoir = first k items
for i = k+1 .. n:
j = uniformInteger(0, i-1)
if j < k:
reservoir[j] = item i
return reservoir若流对象不能预先填充，应在计数 seen <= k 时追加元素，之后使用相同分支。随机整数必须覆盖完整区间且无偏。
第四步：证明新元素的概率。
处理第 i 个元素时，它被选入的概率是 k/i。进入后不会再被替换的概率是之后每一步都不替换它：第 t 步替换某个特定槽位的概率是 1/t，因此留存概率为 ∏(1 - 1/t) = (i)/(n)；最终概率 k/i × i/n = k/n。
第五步：证明旧元素的概率。
归纳假设第 i-1 步每个旧元素在 reservoir 的概率是 k/(i-1)。第 i 步它被保留的概率为 1 - (k/i × 1/k) = 1 - 1/i，所以最终为 k/(i-1) × (i-1)/i = k/i。新旧元素都满足同一不变量。
第六步：分析复杂度与随机实现。
每个元素只处理一次，时间 O(n)；reservoir 存 k 个元素，额外空间 O(k)。当 i 超过安全整数范围时，使用支持无偏大整数范围的随机 API，避免浮点精度让概率失真。
第七步：处理输入边界。
空流返回空样本；k = 0 返回空样本或抛出约定异常；k > n 在未知 n 的流中只能读到结束后返回实际数量或报错。若元素按值去重，需要额外集合，空间可能不再是 O(k)。
第八步：说明加权与分布式扩展。
加权抽样需要按权重定义目标分布，不能继续使用等概率替换；可讨论 weighted reservoir 或 Efraimidis-Spirakis key。分布式场景要合并各分片样本并携带计数/权重，简单拼接各节点 reservoir 会产生偏差。
高质量示范回答
“我会维护容量为 k 的 reservoir。先填入前 k 个元素；从第 i = k+1 个开始，生成无偏整数 j ∈ [0, i-1]。若 j < k，就用当前元素替换第 j 个槽位，否则丢弃。对第 i 个新元素，它进入概率是 k/i；进入后每个槽位等可能，因此任意旧元素在这一步被替换的概率是 1/i，留存概率是 (k/(i-1)) × (1-1/i) = k/i。归纳可得处理完 n 个元素后，每个元素都有 k/n 的入样概率。算法单遍 O(n) 时间、O(k) 空间。我会验证空流、k=1、k=0、重复记录和多次模拟的频率，并明确加权或分布式扩展需要重新证明。”
常见错误
- 先存完整流再抽样 → 违反未知长度和内存约束 → 边读边维护 reservoir。
- 第 i 个元素总以
1/k进入 → 概率随 i 变化而失真 → 使用k/i。 - 用
random() % i→ 范围不整除时有偏 → 使用无偏整数采样。 - 替换槽位不均匀 → 某些样本组合概率更高 → 在 k 个槽位中均匀选择。
- 把
k/n当作处理中的进入概率 → n 未知且每步概率不同 → 按当前计数 i 更新。 - 忽略重复值定义 → “不同”可能指记录或值 → 先澄清去重语义。
- 声称分片样本直接拼接仍均匀 → 各分片大小不同会造成偏差 → 携带计数并重新合并。
- 加权场景继续用等概率算法 → 目标分布改变 → 使用加权 reservoir 并给出新证明。
追问及应对
追问一：为什么新元素的替换概率是 k/i？
在第 i 个元素到达时，算法从 i 个位置中均匀选一个，前 k 个位置代表 reservoir；命中这 k 个位置的概率就是 k/i。
追问二：k=1 时如何证明公平？
第一个元素概率为 1；第 i 个新元素以 1/i 替换。任一旧元素以 (1/(i-1)) × (1-1/i) = 1/i 留存，因此归纳成立。
追问三：如何做无偏随机整数？
使用语言提供的均匀整数 API，或采用拒绝采样丢弃超出最大可整除区间的随机值。不要假设简单取模总是无偏。
追问四：如果流长度小于 k 怎么办？
读到流结束时返回所有实际元素，或按接口约定报错。关键是不能凭空填充样本，也要在题目前说明行为。
追问五：如何抽取带权样本？
定义每个元素的权重目标，再使用 weighted reservoir 的随机 key 或指数/对数变换；均匀 reservoir 的 k/i 证明不能直接复用。
追问六：如何合并分布式 reservoir？
每个分片需携带已读数量及足够的随机优先级或权重，合并时按全局抽样规则重新选择。直接等量拼接或随机截断会偏向小分片。
追问七：如何验证均匀性？
对固定短流重复运行大量次，统计每个元素入样频率并与 k/n 比较；同时测试边界和随机种子可复现性。统计检验只能发现实现偏差，不能替代概率证明。