> Interview Breeze

Write a rand 7 function with rand 5

Problem

Given a function called rand5() that returns a random number between 1 and 5, write a function called rand7() that returns a number between 1 and 7.

Non Uniform Distribution Solution

There are a number of ways to approach this problem, but the key is to understand the trade offs involved with each. The most trivial solution is:

def rand7():
    return ((rand5() + rand5()) % 7) + 1

There is a serious issue with this approach. There is an uneven distribution between possible outcomes, and some numbers are more likely to be returned than others. We can illustrate this by looking at the frequency with which all the possible values are returned:

>>> Counter([rand5() + rand5() for x in range(1,1000)])
Counter(
    {
      6: 205, 
      5: 163, 
      7: 150, 
      8: 125, 
      9: 113, 
      4: 100, 
      3: 65, 
      10: 45, 
      2: 33
    }
)

As you can see, some numbers have a much higher probability of being returned than others (2 is only returned 3.3% of the time, but 6 is returned 20.5%). From the perspective of a random function, this is highly undesirable.

Uniform Distribution Solution

If we are willing to make some tradeoffs, we can create a function that has an even distribution of returned values. In a loop, we will get a uniformly random number from 1 to 25, which we will call i, using (5 * (rand5() - 1)) + rand5(). We will exit the loop when i is less than or equal to 21. Since 21 is evenly divisible by 7, We can return the modulus 7 of i, leading to a uniformly random number from 1 to 7.

def rand7():
    i = 25
    while i > 21:
        i = (5 * (rand5() - 1)) + rand5()
    return i % 7 + 1

The trade off with this approach is that we have written a function that is not constant time, and is unbound in the number of times it could loop (though in practice, it should rarely loop more than twice.)


You may also want to read:

Write a rand 2 function with rand 5

Given a function called rand5() that returns a random number between 1 and 5, write a function called rand2() that returns a number between 1 and 2.

Read More >>
Reverse a singly linked list

Given a singly linked list, write a function that returns a linked list with all the nodes in reverse order.

Read More >>
Max Stack

Design a data structure that is similar to a stack. It will only contain unique integers (no integer will ever repeat), and should have a pop, push, peek, and max function that have O(1) time complexity.

Read More >>