Simulate sending red envelopes through wechat and N individuals grab red envelopes with a total amount of M. Please design an algorithm and implement it

This topic is I met in bytes to beat interview last Tuesday, written or a violent version at the time, then come back to communicate with friends, a lot of people are met, so this topic is a byte to beat development/test/measuring series is often the topic, it is quite interesting, record the share

Preliminary thoughts. – Violent version

To be honest, when I first saw this topic, my thoughts were like this:

Each random value in the interval (0, m) is called r;
Calculate the remaining amount m-r, the remaining amount m-R must be greater than (n-1)*0.01, or the following n-1 person can not complete the allocation;
Random n-1 times in order, the last amount left can be directly as the last red envelope, do not need to be random;

Well, that sounds good, so I went ahead and implemented my version of the solution:

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:
        There are two details to note here:
        Uniform (A, B) uniform(A, B) ≥ A &≤ B
        Uniform (A, B) -random. Uniform (A, B) : 0.0012032010230123
        alloc_result = round(random.uniform(0.01, m-0.01), 2)
        The judgment of # (m-alloc_result) < (n * 0.01) is to ensure that after the randomness of this time, the subsequent total amount can continue to be allocated, otherwise the condition will be re-randomly guided to meet this condition
        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
Copy the code

It looked OK, then I tested myself with relatively normal data, like this:

for _ in xrange(10) :print money_alloc(10.5)
Copy the code

The following output is displayed:

[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]
Copy the code

From the random result, we found a characteristic of this solution, that is, the red envelope amount is getting smaller and smaller, which is equivalent to saying: the one who grabs the red envelope first will get the larger amount.

Then, when we tested it again with relatively extreme conditions (e.g., $1, 100 people points), the tragedy occurred, and the program fell into a deep randomness. The reason for this was that the further we went, the smaller the range of available amounts became, and the greater the randomness pressure became.

To summarize this violent solution:

Public thinking, suitable for the scene of more money and fewer people, in the case of less money and more people will fall into a random cycle;
Fairness is too poor, the advantage of the first grab is too large, obviously not in line with the fairness of the current wechat red envelope;

Violent Version 2

Since less money and more people lead to a random loop, is there no solution? Of course not

def money_alloc(m, n) :
    if n * 0.01 > m:
        raise ValueError("not enough money or too many people")
    result = []
    m = round(m, 2)
    # Add random number statistics
    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
            # Random 10 times still no result, directly give ya a 0.01, ok?
            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
Copy the code

Here violent version 2 inside, the main added a random number of statistics random_count, to avoid random into the “infinite loop”, the code logic is relatively simple, will not repeat

Then we test the algorithm again as follows:

for _ in xrange(10) :print money_alloc(1, random.randint(10.99))
Copy the code

The test results are as follows:

[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]
Copy the code

OK, it feels OK. Although violent version 2 solved the problem of the infinite loop in violent version 1, the fairness problem is still not solved.

Next, I will introduce two other solutions: the double mean method and the line segment cutting method. These two methods refer to xiao Hui’s algorithm ideas.

Double mean method

In the violent version, the unfair problem is mainly reflected in the large front interval and the small available random interval, which leads to the serious imbalance of the red envelope amount. Therefore, the core of the two-fold mean method is to stabilize the random interval.

Here’s the idea of the double mean:

Calculate an average, such as 10 yuan, 10 people, each person will get 1 yuan;
For the first random, the random interval is defined between (0, 2), and a value R1 is randomly obtained, that is, the first red envelope;
Then the second random, calculate the remaining amount 10-R1, calculate the remaining per capita (10-R1)/9, and then randomly select the second red envelope in [0, per capita * 2];
And so on, complete the process of red envelope distribution;

When I first saw this idea, I had this question:

Why would I just randomize the mean times 2? Why not just randomize the interval of 0? Let’s say 10 people share 10 dollars, why don’t you go directly to the (0, 1) range the first time and go to the (0, 2) range?

The random problem, which is a little bit more general, is the random in the interval (a, b), so the random value is more likely to be around (a+b)/2

According to this idea to continue to analyze, for the above example, basically we can let everyone grab a red envelope at about 1 yuan

Let’s implement it in 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
Copy the code

Then, using normal test cases, test:

$10 for five
for _ in xrange(10):
    print money_alloc(10, 5)

# Distribution results, random results near 2 are at first glance the majority
[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]
Copy the code

Then, with the extreme test case, test:

# 1 yuan 50 points, distribution results (too much data, two randomly selected)
[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]
Copy the code

The two-fold mean method is a good solution to the problem of fairness in the violent version, so that the difference between the red packets that each person can grab is not too big

To summarize the double mean method:

Solve the problem of fairness in the violent version, but the actual wechat red envelopes are not equal in the distribution of results, we should all have experience

Line segment cutting

In order to make the final distribution result reflect the difference and be closer to the actual wechat red envelope snatching process, line segment cutting method can be considered.

The idea of line segment cutting method is roughly as follows:

1. Imagine the distribution process of red packets as line segment cutting, and the total amount of red packets is the total length of line segment;

2. When n-1 non-repeating points are marked on the line segment, the line segment is cut into small line segments with different length (amount) of N points;

3. Marking method: a value is randomly selected in the interval (0, m) every time, which is the marking point;

4, finally calculate the gap between adjacent marker points (subline length) is the red envelope amount;

Without further ado, let’s get straight to Python implementation:

def money_alloc(m, n) :
    if n * 0.01 > m:
        raise ValueError("not enough money")
    # 0 is the starting point of the line segment
    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 is the end of the line segment
    result.append(m)
    result.sort()
    return [round(result[index+1]- item, 2) for index, item in enumerate(result) if index < len(result) - 1]
Copy the code

Test it out:

[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]
Copy the code

OK, so at this point everything seems to have been solved perfectly, so this solution looks perfect.

But… Is that really the case?

Now, let’s leave the actual scenario behind and go back to the algorithm itself. Let’s test 10,000 pieces and 30,000 points. The test code is as follows:

for _ in xrange(5):
    a = time.time()
    money_alloc(10000.30000)
    b = time.time()
    print b - a
Copy the code

The test results are as follows:

7.04587507248
7.84848403931
7.50485801697
7.98592209816
8.28649902344
Copy the code

On my computer, it takes about seven or eight seconds, which is…

Without panicking, let’s first examine possible problems with the code:

Random 3W+ times, this process is really time-consuming, but there is no room for improvement;
alloc_result in resultWhen the result is very large, the search efficiency is too low and time-consuming, so this must be changed.
result.append(alloc_result)If the insertion is ordered, then the subsequent list.sort is unnecessary;
Also, is list.sort() time-consuming?

What data structure is the most efficient to find? Of course it is hashmap, dict, and list.sort() takes less than 10ms. There is not much room for optimization, so ordered inserts are not considered.

Line segment cutting – optimized version

The final optimized code is as follows:

def money_alloc(m, n) :
    if n * 0.01 > m:
        raise ValueError("not enough money")
    result = [0]
    # Sacrifice part of space to improve the efficiency of duplicate search
    tmp_dict = dict()
    m = round(m, 2)
    while n > 1:
        alloc_result = round(random.uniform(0.01, m - 0.01), 2)
        # version 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]
Copy the code

After the optimization, let’s test it again with the test code to see what happens:

0.197105169296
0.169443130493
0.162744998932
0.167745113373
0.147526979446
Copy the code

7 seconds to 200ms efficiency increase, not too intuitive

As for the space complexity, I leave it to my friend Ben to study, I hope there is a better version can learn

The problem summary

Three solutions of the red envelope grabbing algorithm: violent distribution, double mean, line segment cutting;
The distribution of violence can only be applied to the problem itself and has no application value in the actual process.
The double mean solved the problem of violent distribution, but lacked the surprise of big red envelopes;
In the actual wechat red envelope distribution process, the difference between line cutting optimization and non-optimization should not be too great, but the pursuit of performance, the optimized version still has more room for improvement;

Appendix: About random.uniform

Uniform is used to generate floating point numbers. Random. Uniform

|  uniform(self, a, b)
     |      Get a random number in the range [a, b) or [a, b] depending on rounding.
Copy the code

Now that’s not an accurate description

In practice, I always thought the random interval was [a, b], but it wasn’t

>>> 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
Copy the code

So you can actually do floating-point randomization when a is greater than b, and the random interval is not absolute in the sense that the minimum is a and the maximum is B

Did you, did you learn?

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Bytedance high frequency programming problem – simulation of Wechat sending red envelopes

Preliminary thoughts. – Violent version

Violent Version 2

Double mean method

Line segment cutting

Line segment cutting – optimized version

The problem summary

Appendix: About random.uniform

Bytedance high frequency programming problem – simulation of Wechat sending red envelopes

Preliminary thoughts. – Violent version

Violent Version 2

Double mean method

Line segment cutting

Line segment cutting – optimized version

The problem summary

Appendix: About random.uniform

Related Posts

Sliding window algorithm learning journey

SpringCloud Upgrade Path 2020.0. X version -12. Introduction and internal principles of UnderTow

Do you really understand the meaning of n in int(n)