字节跳动高频编程题—模拟微信发红包 初步想法-暴力版本 暴力

发表于

模拟微信发红包，n个人抢总金额为m的红包，请设计一个算法并实现

这个题目是我在上周二面试字节跳动时候遇到的，当时写出来的还是一个暴力版本，回来之后就和朋友交流了一下，很多人也遇到过了，所以这个题目算是字节跳动研发/测试/测开系列经常出的题目，还挺有意思的，记录分享一下

初步想法-暴力版本

说实话，刚开始看到这个题目的时候，我的想法是这样的：

  • 每次在(0, m)这个区间内随机一个值，记为r；
  • 计算一下剩余金额m-r，剩余金额m-r必须大于(n-1)*0.01，不然后面的n-1个人无法完成分配；
  • 按照顺序随机n-1次，最后剩下的金额可以直接当做最后一个红包，不需要随机；

嗯，听上去不错，然后动手实现了一下这个解法版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
python复制代码def money_alloc(m, n):
    if n * 0.01 > m:
        raise ValueError("not enough money or too many people")
    result = []
    m = round(m, 2)
    while n > 1:
        # 这里需要注意两个细节：
        # - random.uniform(a, b)的随机区间是≥a&≤b,即[a, b]
        # - random.uniform(a, b)随机出来的值是0.0012032010230123，保留两位小数之后是有可能出现等于0.00的情况
        alloc_result = round(random.uniform(0.01, m-0.01), 2)
        # (m - alloc_result) < (n * 0.01)的判断是为了保证这一次的随机之后，后续的总金额可以继续分配，否则将重新随机指导满足这个条件
        if  (m - alloc_result) < (n * 0.01) or alloc_result <= 0.00:
            	continue
        result.append(alloc_result)
        n = n - 1
        m = m - alloc_result

    result.append(round(m, 2))
    return result

看上去OK的，接下来我用相对正常的数据自测了一下，类似这样：

1
2
python复制代码for _ in xrange(10):
    print money_alloc(10, 5)

输出结果如下：

1
2
3
4
5
6
7
8
9
10
python复制代码[3.73, 6.15, 0.06, 0.03, 0.03]
[4.28, 0.8, 1.09, 2.13, 1.7]
[0.66, 2.27, 5.5, 1.5, 0.07]
[6.55, 1.46, 0.82, 0.2, 0.97]
[5.48, 0.47, 0.65, 0.48, 2.92]
[6.4, 3.09, 0.29, 0.01, 0.21]
[9.94, 0.02, 0.01, 0.01, 0.02]
[4.98, 4.97, 0.01, 0.01, 0.03]
[8.17, 1.3, 0.18, 0.17, 0.18]
[3.49, 5.45, 0.36, 0.3, 0.4]

从这个随机结果里面，我们发现了这个解法的一个特点，就是红包金额越来越小，等于说：谁先抢，谁能抢到的红包金额就越大。

接着，我们用相对极限的情况（比如1块钱 ，100个人分）再次测试的时候，悲剧发生了，程序陷入了深深的随机当中无法自拔，究其原因在于越往后，金额的可用区间就越小，随机的压力就越大。

总结一下这个暴力解法：

  • 大众思路，适合钱多、人少的场景，在钱少、人多的情况下会陷入随机死循环；
  • 公平性太差，先抢的优势过大，显然不符合当前微信红包的这种公平性；

暴力版本二

既然钱少、人多的情况下会陷入随机死循环，那么是不是就无解了呢，当然不是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
python复制代码def money_alloc(m, n):
    if n * 0.01 > m:
        raise ValueError("not enough money or too many people")
    result = []
    m = round(m, 2)
    # 加入随机次数统计
    random_count = 0
    while n > 1:
        alloc_result = round(random.uniform(0.01, m-0.01), 2)
        if  (m - alloc_result) < (n * 0.01) or alloc_result <= 0.00:
            random_count += 1
            # 随机10次还没有结果，直接给丫来一个0.01，行不行?
            if random_count > 10:
                alloc_result = 0.01
                random_count = 0
                result.append(alloc_result)
                n = n - 1
                m = m - alloc_result
            continue
        result.append(alloc_result)
        n = n - 1
        m = m - alloc_result
    result.append(round(m, 2))
    return result

这里暴力版本二里面，主要加入了一个随机次数统计值random_count，来避免随机陷入“死循环”，代码逻辑比较简单，就不赘述了

接着我们再次对这个算法进行测试，如下：

1
2
python复制代码for _ in xrange(10):
    print money_alloc(1, random.randint(10, 99))

测试结果如下：

1
2
3
4
5
python复制代码[0.03, 0.13, 0.16, 0.01, 0.1, 0.2, 0.06, 0.02, 0.01, 0.01, 0.01, 0.01, 0.02, 0.01, 0.02, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.03]

[0.79, 0.02, 0.03, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.03]

[0.01, 0.08, 0.01, 0.01, 0.02, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.01, 0.03]

OK，感觉还凑合，暴力版本二虽然解决了暴力版本一当中的死循环问题，但是公平性问题还是没有被解决。

接下来介绍一下另外的两种解法：二倍均值法和线段切割法，这两种方法借鉴了小灰的算法思路。

二倍均值法

在暴力版本中，不公平的问题主要体现在前面的区间太大，后面可用的随机区间太小，导致了红包金额严重失衡的问题，所以二倍均值法的核心在于稳定随机的区间。

先介绍一下二倍均值的思路：

  • 计算一个平均值，比如10块钱，10个人，人均可得1块钱；
  • 第一次随机时，将随机区间定义在(0, 2)之间，随机得到一个值r1，即第一个红包；
  • 接着进行第二次随机，计算剩余金额10-r1，计算剩余人均(10-r1)/9，然后在[0, 人均 * 2]中随机出第二个红包；
  • 以此类推，完成红包分配的过程；

我当初看到这个思路的时候，有这样的一个疑问：

为什么要将均值*2呢，直接在(0, 均值)这个区间进行随机不行吗？比如说10人分10块钱，第一次为什么不直接在(0, 1)这个区间而要再(0, 2)这个区间呢？

关于随机的问题，有点超纲了，总结来说就是在(a, b)这区间内的随机，那么随机出来的值在(a+b)/2附近的概率更大

按照这个思路继续分析下去，对于上面这个实例来说，基本上可以让每个人抢到的红包都在1块钱左右

我们用Python实现一下看看：

1
2
3
4
5
6
7
8
9
10
11
12
13
python复制代码def money_alloc(m, n):
    if n * 0.01 > m:
        raise ValueError("not enough money or too many people")
    result = []
    m = round(m, 2)
    while n > 1:
        avg_money = round(m / n * 2, 2) - 0.01
        alloc_result = round(random.uniform(0.01, avg_money), 2)
        result.append(alloc_result)
        n = n - 1
        m = m - alloc_result
    result.append(round(m, 2))
    return result

接着用正常测试用例，测试一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bash复制代码# 10块钱5个人分
for _ in xrange(10):
    print money_alloc(10, 5)

# 分配结果, 随机结果在2附近的值一眼看下去还是居多的
[1.83, 0.78, 0.28, 2.74, 4.37]
[1.17, 4.13, 0.54, 0.66, 3.5]
[1.37, 1.67, 1.3, 5.57, 0.09]
[3.49, 2.5, 1.22, 0.75, 2.04]
[2.1, 3.2, 0.5, 3.19, 1.01]
[2.83, 2.01, 2.12, 1.2, 1.84]
[2.97, 0.79, 1.45, 1.52, 3.27]
[2.77, 1.64, 1.53, 0.41, 3.65]
[3.49, 0.88, 0.39, 3.26, 1.98]
[1.79, 3.61, 2.55, 1.21, 0.84]

接着用极限测试用例，测试一下：

1
2
3
bash复制代码# 1块钱50个人分，分配结果（数据太多，随机取了两个）
[0.01, 0.03, 0.01, 0.01, 0.01, 0.02, 0.03, 0.02, 0.03, 0.03, 0.01, 0.01, 0.01, 0.02, 0.02, 0.02, 0.01, 0.02, 0.02, 0.02, 0.02, 0.02, 0.03, 0.02, 0.02, 0.02, 0.02, 0.01, 0.02, 0.02, 0.03, 0.02, 0.02, 0.02, 0.02, 0.02, 0.03, 0.02, 0.01, 0.02, 0.03, 0.02, 0.01, 0.01, 0.02, 0.04, 0.03, 0.04, 0.01, 0.02]
[0.03, 0.03, 0.02, 0.02, 0.03, 0.03, 0.03, 0.02, 0.02, 0.01, 0.03, 0.02, 0.02, 0.02, 0.02, 0.01, 0.02, 0.01, 0.02, 0.03, 0.02, 0.01, 0.03, 0.02, 0.02, 0.03, 0.01, 0.02, 0.03, 0.02, 0.02, 0.01, 0.01, 0.03, 0.02, 0.01, 0.03, 0.02, 0.02, 0.02, 0.02, 0.01, 0.02, 0.02, 0.02, 0.01, 0.02, 0.01, 0.01, 0.02]

二倍均值法很好的解决了暴力版本当中的公平性问题，让每个人能够抢到的红包差距不会太大

总结一下二倍均值法：

  • 解决了暴力版本中的公平性问题，但实际的微信红包在分配结果上并不是均等的，具体大家应该都有体会

线段切割法

为了让最终的分配结果体现出差异性，更贴近实际使用中的微信抢红包过程，可以考虑线段切割法。

线段切割法的思路大致如下：

1、将红包的分配过程想象成线段切割，红包的总金额为线段的总长度；

2、在线段上标记处N-1个不重复的点，线段就被切割成了N分长度(金额)不同的小线段；

3、标记方法：每次都在(0, m)这个区间随机出一个值，即为标记点；

4、最后计算相邻标记点之间的差距（子线段长度）即为红包金额；

话不多说，直接上Python实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
python复制代码def money_alloc(m, n):
    if n * 0.01 > m:
        raise ValueError("not enough money")
    # 0为线段的起点
    result = [0]
    m = round(m, 2)
    while n > 1:
        alloc_result = round(random.uniform(0.01, m - 0.01), 2)
        if alloc_result in result:
            continue
        result.append(alloc_result)
        n = n - 1
    # m为线段的终点
    result.append(m)
    result.sort()
    return [round(result[index+1]- item, 2) for index, item in enumerate(result) if index < len(result) - 1]

测试一下：

1
2
3
python复制代码[1.07, 6.08, 2.85]

[0.04, 0.11, 0.02, 0.02, 0.02, 0.01, 0.01, 0.01, 0.07, 0.02, 0.02, 0.05, 0.12, 0.02, 0.01, 0.01, 0.01, 0.13, 0.02, 0.01, 0.05, 0.03, 0.02, 0.07, 0.01, 0.02, 0.02, 0.01, 0.03, 0.01]

OK，到这里似乎所有的问题都已经完美解决了，这个解法看起来好完美。

But…事实真的是这样吗？

现在，我们抛开实际的场景，回归到这个算法本身，不妨测试一下1万块3万人分，测试代码如下：

1
2
3
4
5
python复制代码for _ in xrange(5):
    a = time.time()
    money_alloc(10000, 30000)
    b = time.time()
    print b - a

测试结果大概如下：

1
2
3
4
5
python复制代码7.04587507248
7.84848403931
7.50485801697
7.98592209816
8.28649902344

在我的电脑上，大概需要耗时7、8秒的样子，这…

不慌不慌，我们先分析一下代码可能的问题：

  1. 随机3W+次，这个过程本省确实耗时，但感觉也没有什么改善空间了；
  2. alloc_result in result在result很大的时候，查找效率太低，非常耗时，这个必须改掉；
  3. result.append(alloc_result)如果是有序插入，那么后续的list.sort就没必要了；
  4. 另外，list.sort()耗时么？

什么数据结构的查找效率最高呢？当然是hashmap，也就是dict啦，并且在测试过程中发现list.sort()耗时基本在10ms以内，优化空间不大，所以没有考虑有序插入。

线段切割法-优化版本

最终优化之后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
python复制代码def money_alloc(m, n):
    if n * 0.01 > m:
        raise ValueError("not enough money")
    result = [0]
    # 牺牲一部分空间，提升查重的效率
    tmp_dict = dict()
    m = round(m, 2)
    while n > 1:
        alloc_result = round(random.uniform(0.01, m - 0.01), 2)
        # hash 版本
        if alloc_result in tmp_dict:
            continue
        tmp_dict[alloc_result] = None
        result.append(alloc_result)
        n = n - 1

    result.append(m)
    result.sort()
    return [round(result[index+1]- item, 2) for index, item in enumerate(result) if index < len(result) - 1]

优化之后，我们用刚才的测试代码再次测试一下看看效果：

1
2
3
4
5
python复制代码0.197105169296
0.169443130493
0.162744998932
0.167745113373
0.147526979446

7秒到200ms的效率提升，不要太直观

至于空间复杂度，留给小伙伴本自己研究吧，希望有更好的版本可以学习一下

问题总结

  • 抢红包算法的三种解法：暴力分配、二倍均值、线段切割；
  • 暴力分配仅仅只能适用于这个问题本身，实际过程中没有任何应用价值；
  • 二倍均值解决了暴力分配的问题，但缺少了大红包的惊喜；
  • 在实际的微信红包分配过程中，线段切割优化和不优化实际上差异应该不至于太大，但是追求性能，优化版本还是有更多的改进空间；

附录：关于random.uniform

uniform一般用于生成浮点数，关于random.uniform的功能描述：

1
2
python复制代码|  uniform(self, a, b)
     |      Get a random number in the range [a, b) or [a, b] depending on rounding.

现在看来这个描述并不准确

实际运用时，我一直认为这个随机区间是[a, b]，实则不然

1
2
3
4
5
6
7
8
9
10
python复制代码>>> random.uniform(0, 1)
0.15407896775722285
>>> random.uniform(0, 1)
0.16189270320003113
>>> random.uniform(0, 0)    # a == b
0.0
>>> random.uniform(0, -1)    # a > b
-0.8838459569306347
>>> random.uniform(0, -100)     # a > b
-76.93918157758513

所以其实a>b的时候也是可以进行浮点数随机的，随机区间并不是绝对意义的最小值是a，最大值是b

你, 学到了吗？

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%