The task is given a function rand5() which produces a random integer in the range 1 to 5, write a function rand7() which produces a random integer in the range 1 to 7.
The random numbers should be distributed uniformely in the range.
There are number of possible solutions, I particulary like the one which deals with randon bit generation. Idea behind this solution is to generate bits in the number randomly based on rand5()
i.e. 1=0x00000001 and 7 = 0x00000111
So you need populat three first bits of the number with either 1 or 0 and based on the rand5() we can think of following uniform distribution:
if n>3 then choose 0;
if n 3) sum += (int)Math.Pow(2, i);
if (rand == 3) continue;
Company where asked this question: Google, Microsoft