> Interview Breeze

Write a rand 2 function with rand 5

Problem

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.

Non uniform distribution

The initial intuition would be to take the modulo of rand5() directly, but just as was the case with the rand 5 question, you will not get an even distribution since rand5() has an odd number of elements. You will however have a O(1) function, so if uniform distribution is not that important, this may be an okay solution.

Uniform distribution

In order to get a uniform distributions, we will need to make a trade off in terms of potential computational cycles. We can query for any number that is less than 4, and take the modulo of that, which will give us an equal chance of getting 1 or 2, but at the cost of the loop executing multiple times.

def rand2():
    i = 5
    while i == 5:
        i = rand5()
    return (i % 2) + 1

You may also want to read:

Write a rand 7 function with rand 5

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.

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 >>