## Amazon Microsoft Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
5
of 13 vote

This is a trick question and there is no correct solution. There are only solutions which are close to correct. The reason for this is that 5 and 7 are relatively prime (also called coprime), so no mapping between them is possible. This means that any solution either (a) does not have the correct probability, or (b) has the possibility of never terminating. All of the solutions given above are therefore incorrect. Lest you think that you can simply convert to binary and back, note that 2 is also relatively prime to both 5 and 7.

I was once asked this question in a phone interview and I tried to explain to the questioner why it was an invalid question, but he didn't understand what "relatively prime" meant.

http://mathworld.wolfram.com/RelativelyPrime.html
http://en.wikipedia.org/wiki/Coprime

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

you're right man, great !

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

You didn't get the job, did you?

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

Maybe it can't be mapped one to one but what about the following?

Make a matrix 5 x 5. One axis is the first roll of the dice. The other axis is the second roll. So there are twenty five boxes. Pick 7 of those and label 1-7. Then start rolling and only count the ones which correspond to the selected boxes 1-7. So the evaluation is not on the total but on the individual rolls and their intersection. There will be a lot of rolls which do not count but this is a simulation and I believe it will completely and correctly simulate the desired outcome. Please let me know if am am wrong and give a good explanation.

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

Maybe this question is too old, but this problem CAN BE SOLVED in simple way:
Throw dice 2 times and make a number from 0 to 24(think in base 5), if N (note the number N)is between 0 and 20, N%7 gives us the desired result. If N is between 21 and 24 throw again(start from beginning).

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

It has correct solution..
See my method...

1. substract 1 from Rand(5) So that you can have values from 0 to 4.
2. convert value to base 2 i.e. 0 or 1. While doing this consider only 0,1,2,3 values. If it is value 4 then do random again(This is for balancing probablity of number of 0 and 1)
3. Do this three times to get 3 different bits.
4. Now you will get binary number from 000 to 111

Done.

``````int bit()
{
do{
Rand(5);
}while(i==4)
i=i%2;
return i;
}

main()
{
int a,sum=0;
for(i=0;i<3;i++)
{
a[i]=bit();
}
for(i=0;i<3;i++)
{
sum+= 2^i * a[i];
}
}``````

What if you have to make random generator 6 instead 7.
Simply neglect value 111.

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

Throw the dice 5 times. Calculated the sum of all the throws. The sum will be in the range [5, 25], i.e. 21 different results. For the different results do the following

Result 7-side simulation result
------ ------------------------
5,6,7 1
8,9,10 2
11,12,13 3
14,15,16 4
17,18,19 5
20,21,22 6
23,24,25 7

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

That formatting did not work, it took all the blanks away. Probably some sort of automatism that SW does so nicely. I will register a trademark for that kind of stuff "Automatically Wrong".

Result 7-side simulation result
------ ------------------------
5,6,7 ====> 1
8,9,10 ===> 2
11,12,13 => 3
14,15,16 => 4
17,18,19 => 5
20,21,22 => 6
23,24,25 => 7

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

This is incorrect because it will not output a uniform distribution if numbers between 1 and 7 (it highly prefers 3,4,5, especially 4). This is because there are many more combinations of numbers that add to produce 11 to 19 (especially 14-16) than in the outer range.

Proof:

``````import java.util.Random;

public class dice {

public static void main(String[] args) {
int[] track = {0,0,0,0,0,0,0};
for(int i = 0; i<=1000000; i++){
int cur = rollD7();
track[cur-1]=track[cur-1]+1;
//System.out.print(cur + " ");
}
System.out.println("Distrubution of dice rolls using this method:");
for (int i =0; i<track.length;i++){
System.out.println(i+1 + ": " + track[i]);
}
}

public static int rollD7(){
int cumulator = 0;
Random r = new Random();

for (int i = 0; i<=5;i++){
cumulator += r.nextInt(4) + 1;
}
switch(cumulator){
case 5:
case 6:
case 7: return 1;
case 8:
case 9:
case 10: return 2;
case 11:
case 12:
case 13: return 3;
case 14:
case 15:
case 16: return 4;
case 17:
case 18:
case 19: return 5;
case 20:
case 21:
case 22: return 6;
default: return 7;
}
}
}``````

Output:
Distrubution of dice rolls using this method:
1: 1716
2: 48045
3: 246051
4: 408084
5: 246087
6: 48334
7: 1684

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

This solution is inspired from Nanmaga...
Throw the dice twice and do the following:

function rand7() {
throw the dice twice and perform the following checks

1,1 return 1
1,2 return 2
1,3 return 3
1,4 return 4
1,5 return 5
2,1 return 6
2,2 return 7
2,3 return 1
2,4 return 2
2,5 return 3
3,1 return 4
...
...
...
5,1 return 7 [at this point we have returned numbers from 1 to 7, 3 times each]
5,2 rand7()
5,3 rand7()
5,4 rand7()
5,5 rand7()
}

In short, in the last 4 cases, we are subdividing the remaining probability into equal proportions by calling rand7() again.

Any idea if this solution sounds okay?

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

I think the approach is correct! Each number 1 to 7 will have probability of 3/25. 4/25 probability of having the repeat when result is outside the range!

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

ur a genius!

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

for any case: rand7();
This is the same as your solution, and I don't think this can be the right answer.

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

Oh,sorry, my mistake, ur right

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

common solution I saw in some other post:

look at the end bits of the numbers generated by 5:
000
001
010
011
100
101

the lsb is generated wth equal probablity ... hence .. all we need to do is call rand5() 3 times and keep on appending the results to a variable num .. to get our value between 0 and 7

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

I meant the lsb of the result to the variable num

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

Well, you could hardly get 000 in one throw...

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

I believe you are simulating an 8 sided die with a 6 sided die.

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

int dice7() {
while (true) {
int num = 5 * (dice5() - 1) + (dice5() - 1);
if (num < 21) return (num % 7 + 1);
}
}

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

this method is called Rejection Sampling. Although not perfect (which is not possible) it is close

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

Could you please explain this a bit?..I mean i can throw the die only once per turn?

I mean what is the expected behavior?

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

the idea here: all sides of the die just should have similar probability to appear:

we throwing 7 times (for each side of 7-sided die) five-sided die and remember sides which got 5, i.e. "qualified" to next round. Then continue until single side left, i.e. got number from 7-side die. (If none got "5" we can either repeat or "qualify" those with "4" and so on).

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

guys its simple... let me reframe the question in a different way-
write the code for rand7() (that will generate random nos from 0 to 6 each with equal probability) given a function for rand5().

Ans:

rand7()
{
return (rand5() + (rand5()%3));
}

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

u r right nerd

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

This is wrong man..
bcoz, die means it is supposed to generate unbiased numbers.
So, rand5() generates unbiased numbers in 0-4 ( meaning each number with equal probability) . But rand5()%3 will be biased bcoz:

using rand5()%3,

rand5():
0 1 2 3 4
|
v
rand5()%3:
0 1 2 0 1

So, 0,1 have higher probability comapred to 2.So the die becomes biased and that die is wrong
meaning finally :
rand7() will not generate all numbers with equal probability which it is supposed to g4enerate. menaing your rand7() function is wrong

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

Good catch GhostRider!

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

is it that simple?

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

1. Generate random bits, by calling rand5 until we get something other than 5
2. Output the value mod 2.
3. For generating rand7, call steps 1 and 2 three times, so that you get three random bits and treat them as three-bit binary numbers(range 0..7).
4. Do step 3 until you dont get a 0, then output the value.

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

Looks good and different too :-)
0 1 2 3 4 5 => 6 numbers
by Rand5()%2 the probabilities of getting a 0 and a 1 are equal
P(getting a 0) == P(getting a 1) = 3/6 =1/2

now we have to generate a 3(_ _ _)digit number with these 0 and 1s which are already having a proper distribution.

Rand7()
return (Rand5()%2)*4+(Rand5()%2)*2+(Rand5()%2)*1

good job algooz.

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

Looks good and different too :-)
0 1 2 3 4 5 => 6 numbers
by Rand5()%2 the probabilities of getting a 0 and a 1 are equal
P(getting a 0) == P(getting a 1) = 3/6 =1/2

now we have to generate a 3(_ _ _)digit number with these 0 and 1s which are already having a proper distribution.

Rand7()
return (Rand5()%2)*4+(Rand5()%2)*2+(Rand5()%2)*1;

good job algooz.

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

Looks good and different too :-)
0 1 2 3 4 5 => 6 numbers
by Rand5()%2 the probabilities of getting a 0 and a 1 are equal
P(getting a 0) == P(getting a 1) = 3/6 =1/2

now we have to generate a 3(_ _ _)digit number with these 0 and 1s which are already having a proper distribution.

Rand7()
return (Rand5()%2)*4+(Rand5()%2)*2+(Rand5()%2)*1;

good job algooz.

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

Looks good and different too :-)
0 1 2 3 4 5 => 6 numbers
by Rand5()%2 the probabilities of getting a 0 and a 1 are equal
P(getting a 0) == P(getting a 1) = 3/6 =1/2

now we have to generate a 3(_ _ _)digit number with these 0 and 1s which are already having a proper distribution.

Rand7()
return (Rand5()%2)*4+(Rand5()%2)*2+(Rand5()%2)*1;

good job algooz.

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

Looks good and different too :-)
0 1 2 3 4 5 => 6 numbers
by Rand5()%2 the probabilities of getting a 0 and a 1 are equal
P(getting a 0) == P(getting a 1) = 3/6 =1/2

now we have to generate a 3(_ _ _)digit number with these 0 and 1s which are already having a proper distribution.

Rand7 => Rand5%2*4+Rand5%2*2+Rand5%2*1;

good job algooz.

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

Let's say that 5 sided die generates numbers from 0 to 4.
Then throw the die for 7 times and get the total value of each die.
We will get one of 0, 1, 2, 3, ..., 28.
The permutation of 0 happen is 1.
The permutation of 1 happen is 7.
....
The permutation of 27 happen is 7.
The permutation of 28 happen is 1.
(Symmetric)

Get to total value of all the permutations and devide by 7.
Let's say the value from above is V.
Get 7 combination to get V.
Each of 0 to 28 must be used, no duplicat but number of numbers does not matter.
We get unviased 7-sided die.

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

It can be done in two throws:
Roll the die twice: and simply take XOR of result1 and ~result2.
Explanation:
from 1-5 the three bits have certain probability for 1 on them. By taking 1's complement of the second throw, u find make the probability same for 1 and 0 on each bit. So, 1-7 has same probability.

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

how about result1=result2? then you got a 0. But 0 is not in 1-7?

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

how about result1=result2? then you got a 0. But 0 is not in 1-7?

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

how about result1=result2? then you got a 0. But 0 is not in 1-7?

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

how about result1=result2? then you got a 0. But 0 is not in 1-7?

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

how about result1=result2? then you got a 0. But 0 is not in 1-7?

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

how about result1=result2? then you got a 0. But 0 is not in 1-7?

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

Throw the dice seven times, number each trial from one to seven, and pick the one with maximum number face-up.
If there is a tie, throw tied ones again to break the tie.
Since all dice are identical, the outputs are distributed uniformly from 1 to 7.
I think andy78 means the same thing bus hasn't explained well.

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

hi,guys,the followings are the correct solutions.
Throw the dice5 for 7 times, and sum the number we get. The sum will be a number between 7 and 35, with the same probility. Then, get the modul of the sum devided by 7, which is a number from 0 to 6. Just plus 1, we can get a dice7.

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

This is not correct!! From 7 to 35, there are 29 numbers. You cannot modulo them evenly to 0 - 6. The probability for 0 is bigger!!!

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

Call the function that generates the random numbers between 1 to 5 twice and add these two results and return modulo 7 of the sum.

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

NO.........THAT WONT BE A GOOD RANDOM FUNCTION.......
BECAUSE THE SUM OBTAINED FOR A PARTICULAR NUMBER CAN BE FROM DIFFERENT COMBINATIONS.e.g.:

2+2,1+3,3+1 = 4
2+1, 1+2 =3

which means the probability of getting 4 is more than 3

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

int rand7()
{
int i, sum;

for(i = 0, sum = 0; i < 5; ++i)
sum += rand5();

/* sum is in [5, 25] now, but that is not
* a uniform distribution, so subtract 2
* to put it in [3, 23] so that division by
* 3 gives us a nice even [1, 7].
*/

return (sum - 2) / 3;
}

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

wrong!......i am sorry........even this is wrong

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

what if I take modulus of rand5() function?
-mod[rand5()*7]

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

forgot to mention modulus 5
i.e. Mod 5 of Rand5()*7

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

r1=ran15
r2=ran15
r3=ran15
r4=ran15

ranum=(r1+10*r2+100*r3+1000*r4) - 1111

return(Floor(ranum/635)+1)

Explanation:
number of possible values is 4444-0+1=4445. 4445/635 =7
we'll have a range of [0,4444]
min is 0+1=1
max is 4444/635=6.999=6+1=7

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

I gave same answer as uday (after a lot f confusion) not as easy as it seem but i think: return (rand5()+ rand5()+...7 times) % 7 is OK (truely random)

as far as Tuatha's explanation .. hopefully it's doesn't need to be that complex, i can't imaging coming up with that stuff while on a phone interview.

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

Actually that would give 0-6 so need to add 1
so:
int rd7=0
for(int i=0;i!=7;i++)
rd7+=random5();
rd7=1+rd7%7
return rd7;

I think that would work fine, anybody think not ?

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

in the above scheme:
let p be the probability of getting a any number between 1 & 5 using rand5. then probability of getting a 5 using rand7 == probability (rd5+rd5..7times)%7 is 4 => numerator can be 4,11,18,25,32 => probability depends upon the number of ways in which you can get a 4 or 11 or 18 ... If then number of ways is x, then the needed probability is xp.

probability of getting a 7 using rand7 can be computed similarly - its the probability that the term is 6 => numerator can be 6,13,20,27,34 => probability is the number of ways in which you can get 6 or 12 or 20 ...If ys is the number of ways, the needed prob is yp.

Is xp == yp ?

consider 4, Lets say there are n ways to get 4. Then to each such way, you can increment two of the 7 terms by 1 and get 6. You can choose these two terms in 21 ways! Thus the number of ways to get a 6 is more than then number of ways to get a 4. This shows that its not likely that xp = yp which means that the suggested method is non-uniform :(

I'm not sure about the above argument! What do you think ?

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

Heres another scheme -
(rand5-1)*6/4 + 1

explanation:
subtracting by 1 gives a random# between 0 & 4. Dividing by 4 gives a random# between 0 & 1. Multiplying by 6 gives a random number between 0 & 6. Adding 1 to this gives a random number between 1 & 7.

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

according to ur formula, we can only have following values:
1
2.5
4
5.5
7

if you floor decimal values 3 and 6 will never appear and if u decide to ceil decimal then 2 and 5 will never appear

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

How come summation become uniform distribution? It is becoming Welghted..
I think we can improve the range with complete uniform solution... But we can use rejection... for example:

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

How come summation become uniform distribution? It is becoming Welghted..
I think we can improve the range with complete uniform solution... But we can use rejection... for example:
---------
int rand7(){
int x = 21;
while( x > 20){
x = 5*(rand5()-1) + (rand5()-1);
}
int r = 1 + (x % 7);
return r;
}
---------
we can improve it if we take to 1-125 range...

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

Hey, what about using shifting ?
function rndBit()
{
// equal prob. of 0 or 1
return rand5() & 1;
}

rand7= 1+ (rndBit()<<3 | rndBit()<<2 | rndBit()<<1 | rndBit()) & 6;

would not this give us random bits (not weighted) and work ?

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

T.C

- rndBit does not have equiprobability to produce 0 and 1. 1,3,5 will return 1 and 2,4 will return 0.

- do we need rndBit()<<3 here as it is ANDed with 6(0x110)?

- adding 1 and ANDing with 6 will always result in 0 in LSB. so it won't generate odd numbers.

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

I couldn't find an answer myself. :(

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

int evenrand()
{
return (rand()%4)*2;
}
rand()
{
//returns no between 1 to 5
}

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

The point of the question is equal distribution. Think about two dimension array (rand(), rand()). This will generate total 25 cases: (1,1), (1,2), ..., (5,5).

In case of (1,1) return 1.
In case of (1,2) return 2.
In case of (1,3) return 3.
In case of (1,4) return 4.
In case of (1,5) return 5.
In case of (2,1) return 6.
In case of (2,2) return 7.
In case of (2,3), in this case, return 1.
Then (2,4) returns 2. And make it recursively until you hit the (5,1). In case of (5,2), (5,3), (5,4) and (5,5) run this logic again. In this way, we can obtain equal distribution.

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

If the uniformity of numbers among random numbers from 1 to 7 is the most important.

Clacualte:
factor = GCD( <1st_Number>, <2nd_Number> )
iff ( GCD is same as { <1st_Number> or <2nd_Number> )
lcmNo = LCM( <1st_Number>, <2nd_Number> )
factor = lcmNo
Generate 1....factor random numbers of range <1...1stnumber>
Sum them and take modulo of <2nd_Number>

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

int rand7(){
int random7= 0;
for(int i =0;i<7;i++){
random7 += rand5();
}
return (random7%7);
}

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

algooz is absolutely correct... his solution is perfect...!!!!

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

I believe acoder's solution is correct. It will help if someone can argue against it.

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

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

Why not something like this:

1) From R5(), we can generate R2() with uniform distribution. How?...
1-ret 1
2-ret 1
3 ret 2
4 ret 2
5 repeat R2()

Modification of this would be

R34()
1-ret 3
2-ret 3
3-ret 4
4-ret 4
5-repeat R34()

Similarly for 5,6 with R56()

Now, to simulate R7(),

1-ret R12()
2-ret R34()
3-ret R56()
4-ret 7
5-repeat R7()

This should be uniformly distributed....anybody thinks otherwise?

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

do rand5()+rand5()
2(1,1) 3(1,2) 3(2,1) 4(1,3) 4(2,2) 4(3,1) 5 5 5 5 6 6 6 6 6 7 7 7 7 8 8 8 9 9 10(5,5)

if
1,1 = return 1
1,2 = return 2
2,1 = return 3
1,3 = return 4
2,2 = return 5
3,1 = return 6
5,5 = return 7

For all other combinations repeat rolling the dies till one of the above combinations come.

Probability calculation:-
Selection probability for the above case = 1/25.
Rejection probability = 18/25

1/25 + (18/25)*1/25 + (18/25)^2*1/25 + ....

1/25*(18/25 + (18/25)^2 + (18/25)^3 +....)

1/25*(25/7)
= 1/7

Since this thread is very long, i apologize if some1 has already posted this solution.

Thanks,
Rohith Menon.

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

This is the right solution, based on conditional probability and algebra. Thank you so much.

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

what non sense

see bro if you wish to consider failure take 18/25 and sucess take 7/25

do not mix 1/25 with 18/25 because both probability are for different.
1/25 is sucess for one case then fail is 24/25

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

Easy:
rand7 = ((ran5 + rand5 + rand5 + rand5 + rand5 - 5) % 7) + 1

The 5 rand will give range 5-25 : 21 numbers.

Equal probability for all.

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

not uniform distribution, dude.

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

The solution from lensbo would seem to work if you throw the 5-sided die 14 times. The sum of the die throws will get you a number from 14 to 70 where the range is 56 (a multiple of 7). Take the sum modulo 7, and you get a number from 0 to 6 evenly distributed. Add 1, and you have a 7-sided die.

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

function rand7() {
v3 = 7;
while (v3 > 6) {
v1 = 4;
while (v1 > 3) {
v1 = rand5();
}
v2 = 4;
while (v2 > 3) {
v2 = rand5();
}
v3 = (v2 << 2) | v1;
}
return v3;
}

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

why not just sum the result of two rolls, and if it is bigger then 6 try again?

``````function rand7(){
X1=rand5();
X2=rand5();
X3=x1+x2;
If result>6 return rand7(); // try again
return result;
}``````

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

why not just sum the result of two rolls, and if it is bigger then 6 try again?

``````function rand7(){
X1=rand5();
X2=rand5();
X3=x1+x2;
If result>6 return rand7(); // try again
return result;
}``````

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

this is correct, though result should be replaced by x3

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

suppose rand5() returns any number in {1, 2, 3, 4, 5}.

int rand7(){
int X1=rand5();
int X2=rand5();
int result = X1 + X2; //If rand5() returns {0, 1, 2, 3, 4} then {0, 3, 4} must be excluded.
If result >= 8 return rand7(); // try again
return result;
}

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

same here :)

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

i think we can follow this approach:

basically we need three diff bits to mkae those (8) numbers then we could discard 000 from there.
so what we need is a routine whcih generates 0 and 1 with equal probability
int rand2()
{
while(1)
{
int randomNum = rand5();
return randomNum%2; // (equal numer of cases of 1 and 0)
}
}

Main routine to generate 8 randomnumbers btwn (0to 7)

int rand7(

int bit1 = rand2();
int bit2 = rand2();
int bit3 =rand2();
int finalNum = bit1<<2 | bit2<<1 | bit3
if(finalNum! =8)
return finalNum;
}

This will guarantee equal probabilitu for all (0 to 7)

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

This seems correct to me. All bits have equal probability.

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

surprised no one has found the "correct"/optimal answer. Took me 3 days to solve it and its an elegant solution. One guy I saw was close.

here's some hints, how do you turn a 10 sided die to a 7 sided die?
And then how do you turn a 2 sided die (a coin) into a 4 sided die?

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

are you alluding to the fact that we can toss the coin twice and get 4 different cases?
and in a 10 sided die, you can neglect any three predefined cases?

in such a case (like 10 and 7) there is a chance that you will be in a non-terminating experiment.

if you know the answer, why not just tell rather than act f'cool..

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

rand5()+randr()+.....12times..
This gives numbers between 12 to 60 uniformly....
so there are 60-12+1 = 49 numbers in total.....
do mod 7 with result and add 1...
this gives 1-7 with equal prob!
same with dice...can be thrown 12 times..n add the results % 7..

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

Change each five-sided die into a binary digit (1-2 are zero, 3-4 are 1, five is a re-roll) and then roll three of them. Interpret the number as binary, with zero being a re-roll
PS: Found this on someone s blog about their google interview experience

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

I am not sure if this is correct-
Result Set contains [000,001,010,011,100,101,110,111] with equal probability. This is something of a Rand8();

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

hmmm yea but 000 is 0 so that is a re-roll. so the remaining set will be [001,010,011,100,101,110,111].

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

I think there is no possible solution; as there are no common powers of 5 and 7. (Note: rolling a die of 6 sides twice, gives 6^2 = 36 possibilities such that (6^2)%6=0 and a number occuring has equal probabilities from 1 through 6. Thus for this to work with 5 and 7 we need a number x such that (5^x)%7=0. Such a number does not exist. Refer to post by anonymous on relative prime.

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

this is correct. it's impossible

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

Can't we simply do it like this:

floor(rand5() * 7 / 5)?

If you think a little how rand() works, it just gives you a float between 0 and 1, and we just multiply it to get a number within our range.

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

int dice7() {
while (true) {
int num = 5 * (dice5() - 1) + (dice5() - 1);
if (num < 21) return (num % 7 + 1);
}
}

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

The idea behind this solution is to use the previously generated random as seed to generate the next random number.

int Random7()
{
static int random7 = 0;
random7 = (Random5() + random7)%7;
return (random7+1);
}

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

my thought is:
Nos from 1 to 7 can be written in binary form as 000 to 111
Now, throw dice for getting all the binary digits.
if Dice Number != 5, digit = (Dice number) % 2
else throw again.
this way we can find all 3 digits with equal probability and hence the number.

Thoughts invited.

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

small correction.
If all 3 digits are 0 then play dice again.

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

``````//assuming rand5() returns a number in range 0 to 4
int rand7(){//returns a number in range 0 to 6
sum = (rand5()+rand5()+rand5()+rand5()+rand5());//0 to 20
return sum/3;``````

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

There are some other answers here:
rosettacode.org/wiki/Seven-sided_dice_from_five-sided_dice

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

Sorry I'm a noob here, but why can we simply:

roll the 5-sided dice 7 times, and then divide by 5

I realise we won't get whole numbers. But if we are allowed to get non-whole numbers, then would this solution be OK?

I notice people are saying something about "uniform distribution" - and that this is part of the answer as to why the above solution is wrong. Can someone please explain how this works here ... sorry and thanks

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

Throw the 5 sided die repeatedly until it shows either a 1 or 2.
If it is 1 write down 0. If it is 2 write down 1.

Repeat the above until you have written down 3 digits.

If you have 3 zeros start again from the beginning.

You end up with a non zero 3 bit binary number. i.e. a number between 1 and 7.

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

throw 5 times, sum up the value of each time and get the remainder of sum % 7.

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

This is the reply to the message by Bk:

===== quote begin =======
It has correct solution..
See my method...

1. substract 1 from Rand(5) So that you can have values from 0 to 4.
2. convert value to base 2 i.e. 0 or 1. While doing this consider only 0,1,2,3 values.
If it is value 4 then do random again (This is for balancing probablity of number of 0 and 1)
3. Do this three times to get 3 different bits.
4. Now you will get binary number from 000 to 111
===== quote end =======

Isn't the uniformity of the distribution broken here :"If it is value 4 then do random again"?

It looks like it is.

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

int rand7(){
return (rand5()+ rand5()+...7 times) % 7
}

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

i think this is wrong solution. rand5() if we call 7 times, we get between 7 and 35. there are 29 numbers between them. so it is not uniform distribution

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

Finally got a simple solution for this tricky question!

Our aim should be to generate sets of numbers whose set count (number of elements in a set) is multiples of 7 so that we can map them to rand(7) values i.e 1 to 7.

Consider this: ((rand 5) * rand(5)) generates the following set:
{1,2,3,4,5,6,8,9,10,12,15,16,20,25}

Luckily, it generates 14 values!

int rand7 () {

int random_7;

Switch ((rand(5) * rand(5)):

Case 1,2: random_7=1;
break;

case 3,4: random_7=2;
break;

case 5,6: random_7=3;
break;

case 8,9: random_7=4;
break;

case 10,12: random_7=5;
break;

case 15,16: random_7=6;
break;

case 20, 25: random_7=7;
break;

}

However, this is just a trial and error solution which works but cannot be generalized for other combinations like rand 5 from rand 3 and so on.

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.