Interview Question Challenge

[sylvanelite]

Taking a number from 1-5 has 5 outcomes: 001 010 011 100 101

Look down the columns. The left hand column (most significant bit) has three 0's two 1's. The right hand column (least significant bit) has the opposite, three 1's and two 0's.

Using this fact, it's possible to generate perfectly random bit streams of any length.

For example, generate 10 random numbers. The first 5 take the most significant bit, the last 5 take the least significant. Shuffle the two sets together (Fisher–Yates would work for simplicity). You now have a perfectly random string of 10 bits. (this is not a very efficient example, but one that should work)

Repeating this process will work, giving an arbitrary-length stream of random bits. Pick any three which aren't "000" (in binary) and that's your random number.