用 rand16 从 30 万员工中均匀抽取 1 万人
哪些公司问过
答案要点
- 两次 rand16 拼接得到 32 位均匀随机数,覆盖 30 万范围
- 直接取模会产生模偏差,需拒绝采样:超过 n 的最大整数倍就重抽
- 部分 Fisher-Yates 洗牌只做前 k 次交换,得到无放回均匀样本
- 蓄水池抽样适合数据流或总数未知的场景,时间 O(n)
- 结果每人入选概率都是 k/n = 1/30,且不会重复
易错点
- 直接 rand16()*rand16() 或简单相加,结果分布不均匀
- 用 r % n 而不做拒绝采样,产生模偏差
- 洗牌时每次在整个区间选 j,导致排列不均匀
面试官常见追问
- 为什么不能随机 1 万次,用哈希表去重?
- 如何证明部分 Fisher-Yates 是均匀的?
- 只用 19 位行不行?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。