CareerCup

int rand3() {
   int random = 2 * rand2() + rand2();
   if (random < 3) return random;
   return rand3();
}

int rand3() {
     int a, b;

     do {
          a = rand2();
          b = rand2();
     } while ( a == 1 && b == 0 );

     return a+b;
}

By eliminating one undesired event (a = 1, b = 3) and forcing one of the remaining 3 events probability of desired 3 events is exactly 1/3 for (0,0), (0,1) and (1,1). Their sum gives 0, 1 or 2. I think this is the right solution. Please see my code above.

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;
		}
	}
}

@nfokin - what is rand3() should return ? Just 0 or 1 again ?

@coder145 rand3() should return 0 or 1 or 2

Not only that rand3() should return 0, 1 or 2 but probability of that events should be about 1/3 to be a real random function. That makes this problem a little bit trickier. I am still thinking about it.

@jovicas of course probability of every choice (0,1,2) should be equal (1/3). This is the meaning of problem.

int rand3() {
int a, b;
do {
a = rand2();
b = rand2();
} while ( a == 1 && b == 0 );
return a+b;
}

I think the solution below is correct.

Public int rand3(){
return rand2()+rand2();
}

Because [1/2 - 1/3 = 1/6] :

________________________
First rand2() | Second rand2()
__________ |_____________

0 | 0
0 | 0
0 | 1
1 | 0
1 | 1
1 | 1

Assuming Rand3() returns values 0,1,or 2. You can just do rand2() + rand2(). The minimum generated value will be 0 and the maximum will be 2.

@madhur2k9 Just test this solution. For example for 10 000 iterations and count distribution of 0/1/2.

@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.

package fbinterview

import (
	"math/rand"
)

// 4 parts
func Rand2() int {
	return rand.Intn(2)
}

func Rand3() int {

	// generate 6 numbers
	var n int
	for i := 0; i < 6; i++ {
		n = n<<1 | Rand2()
	}

	switch {
	case n < 26:
		return 0
	case n < 41:
		return 1
	default:
		return 2
	}

}

Think about it. There's no need for ANYTHING complex here.

Public int rand3(){
    return rand2()+rand2();
}

This either returns 0+0=0, 1+0=1, or 1+1=2.