蓄水池抽样算法的原理与实现
哪些公司问过
网易1阿里高德1
答案要点
- 适用场景:数据流长度未知或无法全部装入内存时等概率抽样
- 前 k 个元素直接入池,第 i 个元素以 k/i 概率替换池中随机一个位置
- 证明:被选入概率 k/i,后续每步保留概率 (j-1)/j,连乘得 k/n
- 大文件按行流式读取,单次遍历,时间 O(n)、空间 O(k)
- k=1 时退化为第 i 个元素以 1/i 概率替换当前结果
易错点
- 替换概率写成 1/i 却用于 k 个样本的情况
- 把整个文件读进内存再随机,违背题目约束
- 随机数区间差一,导致概率不均
面试官常见追问
- 文件太大,能并行处理吗?
- 随机数生成要注意什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。