腾讯面试题：微信抢红包算法详解

红太狼 2022-04-24 08:12 1931阅读 0赞

昨天在刷手机的时候看到毕导以前的一个视频，不知道大家有没有听说过毕导：清华大学化工博士，代表作品是：《微信红包先抢和后抢差距居然这么大》，百度百科如下：

![1240][]

博主昨天刷到的视频是毕导在某个平台上的发言分享，视频发言的主要内容如下：

1.  小发明：微信刷步数神器
2.  小发明：防雾霾神器和自动洗袜子机
3.  微信抢红包探究：末位红包抽屉原理
4.  非稳态传热温度场在鸳鸯锅和清汤锅的应用
5.  论火锅中的食物可吃性曲线
6.  论薯片掉地上的可吃性

视频很有趣，脑洞很大（文章的末尾可以直接观看毕导的这段视频，没有看过视频的同学真的不要错过）。

关于微信红包，大家最关心的应该是：运气王的分布，每次0.01真的是很丧很丧。毕导发了几亿次微信红包，统计得到了大家需要的答案（视频中的截图）：

![image][]

上面的统计结果图可以看出：手速最慢的同学最可能是运气王，所以大家以后抢红包记得让博主先来。上面这张图只是视频中众多结论中的一个，有兴趣的同学可以拉倒文末看看完整的视频。视频中另外一个关于微信红包算法的重要发现是：

每个人当前抢到的微信红包金额大小服从：

区间\[0.01，2\*当前剩余红包均值两倍)上的均匀分布。可能不太好理解，举个例子：某个时刻你抢到了红包，在你抢红包前红包余额为m，红包剩余个数为n，那么你抢到的金额一定是在\[0.01，2\*m/n）区间内，其中m/n就是你抢红包前每个人可以均分到的红包金额，即剩余红包均值。

更多关于微信红包的统计和结论请看文末的视频。视频中的微信红包算法让博主想起了腾讯内推一面面试时被问到的一道面试题，面试题与微信红包算法有关：你认为微信的红包算法是如何实现的？如果是你，你会如何实现红包算法？

微信红包算法也是很经典的面试题，身边同学在阿里的面试中也曾遇到过。这么经典的面试题当然要和大家一起分享啦。博主在面试的时候给出的答案并不怎么好，在面试官的引导下才逐渐答到点上。

现在回过头来看这个问题，微信红包算法应该主要考虑以下几个因素：

微信红包金额是随机数

只不过这个随机数有限制：精确到两位小数；最小金额是0.01；最大金额也有限制：2倍的剩余红包平均金额（2倍的数据是毕导视频给出的）

不能超发，就是你发了3块钱红包最后红包总额不能超过3块。

先抢和后抢的收益均值要大致相同

基于上面几点，博主写了一份示例代码，如下：

import java.util.\*;

public class WeiXinRedPackage1 \{

public static void main(String[] args) {
        double sum = 0;
        ArrayList<Double> res 
               = WXRedPackageAlgorithm(10,3);
    
        for(double money:res) {
            sum += money;
            System.out.print(money +" ");
        }
    
        System.out.println();
        System.out.println(sum);     
    }
    
    private static ArrayList<Double> WXRedPackageAlgorithm(double restMoney,int restNum){                
        ArrayList<Double> res 
                 = new ArrayList<>(restNum);
    
        Random random=new Random();
        while(restNum>1) {
            //最大的红包为：两倍的平均红包大小
            double max=(restMoney/restNum) * 2;
    
            //产生[0,1)之间的随机数
            double r=random.nextDouble();
    
            //抢到的红包区间[0,max)
            double money = r * max;
            if(money<0.01)
                money = 0.01;
            else 
                money= Math.floor(money*100)/100;        
    
            res.add(money);
    
            restNum--;
            restMoney -= money; 
        }   
    
        //最后一个红包为剩余余额
        res.add(Math.floor(restMoney*100)/100 );
        return res;
    }

接下来就是代码的测试和验证环节，博主写了一个测试脚本测试上述抢红包算法。博主用python脚本模拟抢红包场景主要是为了验证上述代码的统计特性与视频中毕导根据真实微信红包算法得到的统计特性之间的异同。使用python语言主要因为python对数据可视化支持比较好，python代码在文末可以获得。

python脚本重复执行上述红包算法50万次，每次循环的参数相同：红包金额为100，红包数目为20。脚本最后统计了**运气王的分布**和以及每个人的**平均红包收益**。

运气王分布统计，如下图所示：

![1240 1][]

100 RMB，20个红包：上面的横坐标是第i次抢到红包，纵坐标对应的是在50万次实验中第i次是运气王的次数。由上面的柱状图可以看出运气王分布的趋势：**后下手更可能是运气王**。这个统计结果与毕导在视频中给出的微信红包分布图整体趋势一致。说明我们的抢红包代码运气王的分布大致符合真实的微信抢红包算法。所以抢红包还是得谦让，谦让最后抢的更可能是运气王。

接下来统计的是50万次抢红包过程中，第i个抢红包获得的平均红包金额。毕导在视频中给出的结果表明：真实的微信红包算法先抢和后抢的平均收益大体是一致。我们的抢红包代码的**平均收益**统计分布如下图：

![1240 2][]

上图的横坐标是：第i次抢到红包；总坐标是在50万次抢红包中第i次抢到红包的平均红包金额收益。从上面的分布图可以看出，50万次抢红包：虽然运气王的概率分布不均匀，但是每个用户的平均收益大致是一样的。这个结论与毕导视频中的结果也相符。

当然微信的红包实现肯定不会是用java，上面的代码仅仅是用作说明而已。并且微信抢红包也可能不是预先分配好金额的，而是拆开红包之后随机分配，红包的数量和剩余金额可以使用Atomic包下的类进行处理 。另外，实际的微信抢红包肯定涉及Redis之类的缓存。

一个抢红包功能并不是像表面那么简单，涉及并发、缓存、数据库等等，有兴趣的读者可以进一步补充相关知识，微信抢红包是一个高频面试考点，**希望能够引起求职者们重视。**

上面的实现代码其实有个小问题，double类型存在精确度问题，所以有的时候会出现下面这种情况：

![1240 3][]

上图是在：红包总金额为10，红包数量为3时，上面给出的代码跑出的结果。第一行的三个数是每个人抽到的红包金额，第二行是3个人抽取到的总红包金额。明明发了10 RMB红包，最后用户只领到了9.99，所以上面代码肯定不能实际使用，要不微信用户肯定不干啊，腾讯也不好和用户解释那丢失的0.01到底哪去了。

上面问题是double类型运算时精度不足导致的，可以采用java的BigDecimal类来解决精度问题。对于不需要任何准确计算精度的数字可以直接使用float或double，但是如果需要精确计算的结果，则必须使用BigDecimal类，而且使用BigDecimal类也可以进行大数的操作，有兴趣的同学可以试试改进下上面代码。

[毕导视频链接][Link 1]

--------------------

扫描下方二维码，发送关键词“**微信抢红包算法**”即可获取本文的完整源码和详细程序注释  
![扫码关注，及时获取更多精彩内容。（博主今日头条大数据工程师）][1240 4]  
公众号专注：**互联网求职面经**、**java**、**python**、**爬虫**、**大数据**等技术、海量**资料分享**：公众号后台回复“csdn文库下载”即可免费领取【csdn】和【百度文库】下载服务；公众号后台回复“**资料**”:即可领取**5T精品学习资料**、**java面试考点**和**java面经总结**，以及**几十个java、大数据项目**，**资料很全，你想找的几乎都有**

[1240]: /images/20220217/22780f01d8a84fe49ad51e249ea46544.png
[image]: /images/20220217/d21025a50f6945a092372f4b4acb032c.png
[1240 1]: /images/20220217/96bdf9f4cc2348ee90f5e5b20b79d40f.png
[1240 2]: /images/20220217/44013dae4ec54b078b23b62ad4b9da0b.png
[1240 3]: /images/20220217/163f7f21e50a416ca2c086eabd2477e0.png
[Link 1]: https://v.qq.com/x/page/a0504kkrvmr.html
[1240 4]: /images/20220217/009dffb6edea4eab868f9c980823da7f.png