用有偏硬币函数构造等概率输出
哪些公司问过
陌陌1
答案要点
- 连续调用 f 两次,(0,1) 与 (1,0) 的概率都是 p(1-p),天然对称
- (0,1) 输出 1,(1,0) 输出 0,(0,0) 和 (1,1) 丢弃重来
- 不需要知道 p,只要求 0<p<1 且两次调用相互独立
- 期望轮数 1/(2p(1-p)),期望调用 f 次数 1/(p(1-p))
- p 越偏向 0 或 1 拒绝率越高;p=0 或 1 时算法不终止
易错点
- 把期望轮数和期望调用次数混为一谈,相差 2 倍
- 丢弃 (0,0)/(1,1) 时直接输出某个值而不是重来,会破坏均匀性
- 忘记说明 p=0 或 1 时无法终止的边界情况
面试官常见追问
- 如何提高效率,减少浪费的调用?
- 如果要等概率输出 1 到 n 呢?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。