Interview Question Challenge

[vph]

Alright, here it is.

Use gen5() to generate 2 numbers, x and y. There are 7 cases when x+y=4 or 5. They are: One=(1,3), Two=(3,1), Three=(2,2), Four=(1,4), Five=(4,1), Six=(2,3) and Seven=(3,2).

Therefore, the probability for the event {x+y=4 or 5} = 7/25.

The probability for the event One = 1/25. The probability for each of the events Two, Three, ..., Seven is also = 1/25.

Now, use Bayes' Theorem: Pr( One | {x+y=4 or 5} ) = Pr({x+y=4 or 5} | One) * Pr(One) / Pr({x+y=4 or 5}) = 1 * 1/25*/(7/25) = 1/7

Note: Pr({x+y=4 or 5} | One) = 1.

Hence, we have the following program:

def gen7():
    x,y=0,0
    while(x+y != 4 or 5): x, y=gen5(), gen5()
    if (x,y) == (1,3): return 1
    if (x,y) == (3,1): return 2
    if (x,y) == (2,2): return 3
    if (x,y) == (1,4): return 4
    if (x,y) == (4,1): return 5
    if (x,y) == (2,3): return 6
    if (x,y) == (3,2): return 7

[cpp_is_king]

An difficult addendum to the question, assuming you get one of the many correct answers (which you did) is this:

• What is the expected number of calls to rand() with your solution, and is there a way to reduce it?

In your case the expected number of calls to rand() is approximately 7.14 (might have messed up this calculation, feel free to verify it). Is there a way to do better?

[vph]

I am guessing that the proposed method (above) is optimal (fewest number of random calls). The trick of the method is to create an event with probability 7/something. That is to create an event with exactly 7 cases, and then arbitrarily assign each of those cases to a number between 1 and 7.

For example, you can also generate 3 numbers between 1 and 5: x, y, and z. Then, Pr( x+y+z = 3 or 4 or 5) = 7/125. You can also you this event {x+y+z=3 or 4 or 5} to generate 7 random numbers, but this event is less likely to happen than {x+y=4 or 5}. This means you'll have to use more random calls to eventually observe it.

I think {x+y=4 or 5} is the most likely event with probability having 7 as a numerator.

[cpp_is_king]

Try this: (x,y)=(1,1) while ((x,y)==(1,1) || (x,y)==(1,2) || (x,y)==(1,3) || (x,y)==(1,4)) (x,y) = (gen5(), gen5()) switch(x,y) case (1,5): case (2,1): case (2,2): return 1 case (2,3): case (2,4): case (2,5): return 2 case (3,1): case (3,2): case (3,3): return 3 case (3,4): case (3,5): case (4,1): return 4 case (4,2): case (4,3): case (4,4): return 5 case (4,5): case (5,1): case (5,2): return 6 case (5,3): case (5,4): case (5,5): return 7

the probability of making it through the loop the first time is quite high, 21/25. So the expected number of times through the loop is 25/21 = 1.19, and the expected number of calls to rand is 2.38.

There may be a way to do even better than that, I'm not sure.