面试场景题:如何设计一个抢红包随机算法
面试官:咱来写个算法题吧
设计一个抢红包的随机算法,比如一个人在群里发了 100 块钱的红包,群里有 10 个人一起来抢红包,每人抢到的金额随机分配。
1.所有人抢到的金额之和要等于红包金额,不能多也不能少。
2.每个人至少抢到 1 分钱。
3.最佳手气不超过红包总金额的 90%
解题思路 1:随机分配法
钱的单位转换为分,每次在[1, leaveMoney]这个区间内随机一个值,记为 r;
计算一下剩余金额 leaveMoney-r,剩余金额(单位:分)必须大于剩余人数,不然后面的人无法完成分配,例如 10 个人,有 1 个人抢了红包,剩余的 money 至少还需要 9 分钱,不然剩余的 9 人无法分;
按照顺序随机 n-1 次,最后剩下的金额可以直接当做最后一个红包,不需要随机;
解题代码:
以下是多次运行的结果:
通过多次运行的结果,可以看到越早抢红包的人,抢到的金额越大,所以题目还可以变形
要求红包金额分布均衡
面试官:继续改进红包生成算法,要求:
1.要保证红包拆分的金额尽可能分布均衡,不要出现两极分化太严重的情况。
解题思路 2:二倍均值法
二倍均值法:假设剩余红包金额为 m 元,剩余人数为 n,那么有如下公式:
每次抢到的金额 = 随机区间 [0.01,m /n × 2 - 0.01]元
这个公式,保证了每次随机金额的平均值是相等的,不会因为抢红包的先后顺序而造成不公平。
举个例子如下:
假设有 5 个人,红包总额 100 元。100÷5×2 = 40,所以第 1 个人抢到的金额随机范围是[0.01,39.99]元,在正常情况下,平均可以抢到 20 元。
假设第 1 个人随机抢到了 20 元,那么剩余金额是 80 元。80÷4×2 = 40,所以第 2 个人抢到的金额的随机范围同样是[0.01,39.99]元,在正常的情况下,还是平均可以抢到 20 元。假设第 2 个人随机抢到了 20 元,那么剩余金额是 60 元。60÷3×2 = 40,所以第 3 个人抢到的金额的随机范围同样是[0.01,39.99]元,平均可以抢到 20 元。以此类推,每一次抢到金额随机范围的均值是相等的。
解题代码:
生成结果测试如下,结果值比较随机了,领取的红包金额和先后顺序无关了
解题思路 3:线段切割法
考虑一种新的解法,把红包总金额想象成一条很长的线段,而每个人抢到的金额就是这条主线段上的某个子线段,如下图:

假设有 N 个人一起抢红包,红包总金额为 M,就需要确定 N-1 个切割点;
切割点的随机范围是(1,M),所有切割点确认后,子线段长度也就确定了
如果随机切割点出现重复,则重新生成切割点
解题代码如下:
最后跑几次看看生成的随机效果,可以看到手气最佳的有到 37 块钱的,相比较二倍均值法,该方法手气最佳获取的金额可能更高
以上就是关于红包随机算法的所有解题方法了,面试中如果遇到考这道算法题,需要问清楚红包随机的情况,有没有要求分布均衡。
如果觉得对面试有帮助的话,记得给文章点赞哦~
版权声明: 本文为 InfoQ 作者【卷福同学】的原创文章。
原文链接:【http://xie.infoq.cn/article/55304d0b4216f7ddefdab36ef】。文章转载请联系作者。
评论