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.



Possible solution:



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()
function.



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:

n=rand5();

if n>3 then choose 0;
if n 3) sum += (int)Math.Pow(2, i);
else
if (rand == 3) continue;

i++;
}
}

return sum;
}


Company where asked this question: Google, Microsoft








Answers and Comments











Agile project management



100 Common Interview Questions, audio book