面试题库 › Java 后端 › 蓄水池抽样算法的原理与实现

蓄水池抽样算法的原理与实现

难度 ★★☆在 2 场真实面经中被问到 方向:Java 后端考点:数学与智力题

哪些公司问过

网易1阿里高德1

常见岗位:Java 后端、游戏服务端

答案要点

  1. 适用场景:数据流长度未知或无法全部装入内存时等概率抽样
  2. 前 k 个元素直接入池,第 i 个元素以 k/i 概率替换池中随机一个位置
  3. 证明:被选入概率 k/i,后续每步保留概率 (j-1)/j,连乘得 k/n
  4. 大文件按行流式读取,单次遍历,时间 O(n)、空间 O(k)
  5. k=1 时退化为第 i 个元素以 1/i 概率替换当前结果

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题