## Yandex Interview Question for Software Engineers

Country: Russia

Comment hidden because of low score. Click to expand.
4
of 4 vote

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

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````int rand3() {
int a, b;

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

return a+b;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.