Yandex Interview Question
Software EngineersCountry: Russia
Generate two random numbers using rand2(). If you get 00 - return 0, if you get 01 - return 1, if you get 10 - return 2, if you get 1 - repeat.
#include <bitset>
using namespace std;
int rand3()
{
bitset<2> generatedNum;
while(true)
{
generatedNum[0] = rand2();
generatedNum[1] = rand2();
int generatedInt = static_cast<int>(generatedNum.to_ulong());
if(generatedInt < 3)
{
return generatedInt;
}
}
}
@BW and @madhur2k9,
I tried commenting a few minutes ago, but my comment didn't seem to post. I think it may be because I was including an external link to Wikipedia (on the binomial distribution). Here it is again, rewritten.
Your functions won't return 0, 1, and 2 with equal probability. This is because you're essentially sampling from a binomial distribution with n=2 and p=0.5. The probability of 0 is .25, probability of 1 is .5, and probability of 2 is .25.
In @BW's explanation, "0+1=1" is missing from the enumerations. Including that makes it clearer that 1 has higher probability than the others.
Given that rand2 uniformly samples from 0 and 1, my interpretation is that rand3 should uniformly sample from 0, 1, and 2.
- shane030716 June 20, 2016