A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast

1. The subject

Given a function rand7(), return 1 to 7 random natural numbers, let use this rand7() to construct rand10() random 1 to 10.

2.

This problem is basically looking at the understanding of probability.

To ensure the uniform distribution of rand10() in integers 1-10, construct a uniform distribution of random integer interval 1-10n (n is any positive integer). Assuming x is a random integer on the interval 1-10n, then x%10+1 is an integer evenly distributed on the interval 1-10. Since (rand7()-1)*7+rand7() can construct random numbers evenly distributed in 1-49 (see the reasons below), random numbers such as 41 ~ 49 can be eliminated, and the obtained numbers 1-40 are still evenly distributed in 1-40, because each number can be regarded as an independent event.

Before I get into the topic, I want to give the reader an example. Consider a simple example. Given that rand2() can generate random numbers of [1,2] uniformly, what should we do to generate random numbers of [1,4] uniformly?

I think if you’re dealing with this problem for the first time, as I am, you might want to consider adding the two rand2() and doing the necessary corners. As follows:

rand2() + rand2() = ? ==> [2,4] 1 + 1 = 2 1 + 2 = 3 2 + 1 = 3 2 + 2 = 4 ==> [1,3] 0 + 1 = 1 0 + 2 = 2 1 + 1 = 2 1 + 2 = 3Copy the code

As you can see, the most fatal point of this approach is that it produces results that are not equally likely. In this simple example, there is a 50% chance of producing a 2, and a 25% chance of producing a 1 and a 25% chance of producing a 3. The reason, of course, is easy to understand, because there are multiple combinations of certain values, so simply adding them up will make the result not equally likely.

Looking closely at the example above, let’s try multiplying the (rand2()-1) part by 2 and change it as follows:

(rand2()-1) × 2 + rand2() =? ==> [1,3] 0 + 1 = 1 0 + 2 = 2 2 + 1 = 3 2 + 2 = 4Copy the code

Amazing things happen, strange knowledge increases. Through this process, the results are just in the range of [1,4], and each number is taken with equal probability. Thus, using this approach, rand4() can be implemented with rand2(). So try this example:

(rand9()-1) × 7 + rand7() = result
     a               b
Copy the code

As you can see, this example generates random numbers in the range [1,63] with equal probability. In fact, we can get the following rule:

(rand_X() -1) × Y + rand_Y() ==> rand_XY() can generate random numbers in the range of [1, X * Y] with equal probability. (rand_X() -1) × Y + rand_Y() ==> Can generate random numbers in the range of [1, X * Y] with equal probability.Copy the code

And now we’re going to apply that to this problem.

First rand7()-1 yields a discrete set of integers {0,1,2,3,4,5,6}, where the probability of occurrence of each integer is 1/7. Then (rand7()-1)7 gives A discrete set of integers A={0,7,14,21,28,35,42}, where the probability of occurrence of each integer is also 1/7. And the probability of each integer in the set B={1, 2, 3, 4, 5, 6, 7} obtained by rand7() is also 1/7. It’s clear that any combination of two elements in A and B can uniquely correspond to an integer between 1 and 49, which means that any number between 1 and 49 can uniquely identify A combination of two elements in A and B, and vice versa. Since the elements in A and B can be viewed as independent events, according to the probability formula P(AB)=P(A)P(B), the probability of getting each combination is 1/71/7=1/49. Thus (rand7()-1)*7+rand7() produces integers evenly distributed between 1 and 49, each with a probability of 1/49.

Some people might be wondering, why don’t you just multiply by 6, multiply by 5? Because it’s not equally probable, you have to multiply it by 7 to make it equally probable.

So, here’s how:

Rand7 ()−1, a2=rand7()−1a_1=rand7()-1, a_2=rand7()-1a1=rand7()−1, A2 =rand7()−1.

If a_17+a_2<40,b=(a_17+a_2)/4+1; If a_1 times 7 plus a_2 is greater than or equal to 40, repeat step 1.

int rand10()
{
    int x=0;
    do
    {
        x=(rand7()-1)*7+rand7();
    }while(x>40);
    return x%10+1;
}
Copy the code

The advanced

But if you’re careful, you’ll notice that we’re going to drop the numbers from 41 to 49, leaving the numbers from 1 to 40 for equal probability. If it’s greater than 40, the while loop will continue. In order to improve efficiency, we do not abandon random numbers greater than 40, and use 9 numbers for operation.

1.(a random number greater than 40− 40−1)∗7+rand7(). In this way, we can get random numbers between 1 and 63. We only need to discard 3 of them. For these 3 discarded numbers, we can do another round:

2.(random number greater than 60 -60-1) * 7+rand7() (random number greater than 60− 60−1)∗7+rand7()

So we can get a random number between 1 and 21, just by dropping 1

int rand10(){ while (true){ int num = (rand7() - 1) * 7 + rand7(); If (num <= 40) return 1 + num % 10; Num = (num - 40-1) * 7 + rand7(); if(num <= 60) return 1 + num % 10; Num = (num - 60-1) * 7 + rand7(); if(num <= 20) return 1 + num % 10; }}Copy the code

Randm ()-> Randn ()

Given that random_m() is in the range of [1, m], ask for random_n() to generate [1, n], m < n && n <= m*m

int random_n() { int val = 0; int t; Do {val = m* (random_m() -1) + random_m(); // do {val = m* (random_m() -1) + random_m(); }while(val > t); return val; }Copy the code

A few big names from Microsoft and Google have organized an interview question brushing group. You can add the administrator VX: SxxZs3998 to participate in the discussion and live broadcast