Amazon Microsoft Interview Question
Software Engineer / DevelopersMaybe 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.
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).
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[3],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.
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
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
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
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?
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!
Ur solution makes no sense, think about this :
for any case: rand7();
This is the same as your solution, and I don't think this can be the right answer.
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
int dice7() {
while (true) {
int num = 5 * (dice5() - 1) + (dice5() - 1);
if (num < 21) return (num % 7 + 1);
}
}
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).
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));
}
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
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.
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.
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.
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.
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.
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.
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.
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.
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.
Even algooz's answer looks good.
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.
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.
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;
}
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.
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 ?
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 ?
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.
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...
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 ?
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.
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>
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?
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
Comments/criticisms welcome.
Since this thread is very long, i apologize if some1 has already posted this solution.
Thanks,
Rohith Menon.
This is the right solution, based on conditional probability and algebra. Thank you so much.
Easy:
rand7 = ((ran5 + rand5 + rand5 + rand5 + rand5 - 5) % 7) + 1
The 5 rand will give range 5-25 : 21 numbers.
Equal probability for all.
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.
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;
}
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;
}
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)
your views?
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?
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..
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
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();
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.
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.
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
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.
I had trouble replying to the actual message, so trying to reply here.
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.
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
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.
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.
- Anonymous November 16, 2008I 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