用不均匀的0/1生成器构造等概率生成器
哪些公司问过
答案要点
- 连续调用A两次,01和10的概率都是X(1-X)
- 01输出0,10输出1,00和11丢弃重试
- 输出严格等概率,且不需要知道X
- 要求0<X<1,否则无法终止
- 每轮成功率2X(1-X),期望调用次数1/(X(1-X))
易错点
- 输出00为0、11为1,概率不相等
- 忘记丢弃后要重新调用两次,而不是只重调一次
- 没说明X为0或1时算法无法终止
面试官常见追问
- 如何用等概率的0/1生成器构造1到n的等概率生成器?
- 已知rand7如何实现rand10?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。