用一个随机数生成器等概率生成另一个范围
哪些公司问过
答案要点
- 直接取模或按比例缩放在范围不整除时会破坏均匀性,需要拒绝采样
- 多次调用组合成更大的等概率范围,如 6×a+b 得到 0~35
- 只保留目标范围的最大整数倍部分,取余映射,其余拒绝重试
- 每轮成功率 = 保留个数 / 总个数,期望轮数为其倒数,再乘每轮调用次数得期望调用次数
- 范围恰好是幂次关系时可直接按进制拼接,如 (r1-1)×100+r2
易错点
- 直接写 rand6()%8 或 rand6()+rand6():前者取不到 6 和 7,后者分布不均匀
- 两次结果相加而不是按进制组合,导致中间值概率更高
- 拒绝区间算错,保留的个数不是目标范围的整数倍
面试官常见追问
- 用 rand3(生成 1 到 3)生成 rand5,成功概率是多少?
- 怎么提升成功概率?
- 极限成功概率是多少?
- 只能等概率生成 3 和 7,怎么得到 0 到 15?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 赛马问题:最少比赛场次19 场
- 洗牌算法(Fisher-Yates)与随机选取11 场
- 判断点是否在三角形内(含边界)10 场
- 两个鸡蛋确定楼层9 场
- 小白鼠试毒(二进制编码)9 场
- 十进制与其他进制的转换8 场
- 天平称球找出轻球的最少次数7 场
- 不使用临时变量交换两个数6 场
- 阶乘末尾有多少个 05 场
- 整数反转(LeetCode 7)5 场