Amazon Interview Question
Country: India
I came up with this >>>
//ASSUMING rand5() GENERATES A RANDOM 'i' SUCH THAT 1<=i<=5
int rand7(){
int r;
do{
r = 10*rand5() + rand5(); // Now r = a random number between 11 and 55;
r -= 10; // Now r = a random number between 1 and 45;
}while(r>=43);
// Now r = a random number between 1 and 42;
return r%7+1;
}
The above code can be easily generalized.
It works. But, although not specified here, the question at other places wants the numbers from 1 to 7 to be generated with equal probability. Your algorithm generates numbers from 1 to 7, but with unequal probabilities as r and r%7 in () below depict.
1(1) 2(2) 3(3) 4(4) 5(5)
11(4) 12(5) 13(6) 14(0) 15(1)
21(0) 22(1) 23(2) 24(3) 25(4)
31(3) 32(4) 33(5) 34(6) 35(0)
41(6) 42(0) 43(1) 44(2) 45(3)
r%7 +1 count
1 4
2 4
3 3
4 4
5 4
6 3
7 3
If it is does not matter to generate numbers with equal probability, a simpler version could be:
do{
r = rand5() + rand5() -1;
} while(r>=8);
return r;
@Ayahuasca
Hi, nice catch, but your suggestion does not work either. For example the probability of taking
4 = 2+2 = 1+3 = 3+1
if different from the probability of taking
2 = 1+1
(I skipped your "-1" here).
However you could use multiplication to maintain the equal-probable condition.
In fact this problem naturally takes two steps:
1) How to generate a random number in [0,M-1] given a generator randN giving results in [0,N-1] with N>M?
Answer: use randN() % M but discard the last N - (N / M) numbers (see Ayahuasca's solution).
2) When M>N.
First generate uniformly distributed random variable using randN()*N + randN(), this function generates random numbers in the range [0,N^2-1] with equal probability; then the problem goes back to 1).
Logic to generate rand7() with the help of rand5():
rand5() - function to generate random number b/w 0 to 5
rand7() = [sum of rand5() generated 7 times] % 7
rand7() = [rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5()] % 7
In this way [sum of rand5() generated 7 times] will vary from 0 to 35
and rand7() will generate random number between 0 to 7 with equal probability.
It works, but the generation of random numbers will not happen with equal probability.
The sum
[rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5()]
actually creates numbers between 7 and 35 with unequal frequencies. There is only one way(7C0) to generate 7 & 35. There are 7(=7C1) ways[Any one of the seven invocations of rand5() returns 2 and the rest all return 1] to generate 8 and 34, 28 ways (7C1+ 7C2) to create 9 and 33 and so on. Therefore the frequency of generation of numbers between 0 and 6(you cannot return 7 when using %) will not be uniform.
There are solutions at: stackoverflow.com/questions/137783/expand-a-random-range-from-15-to-17 that work but needs to be modified to include the generation of number 0(The methods there are generating random numbers between 1 and 7 though)
As @Apostle said this solution too does not generate numbers with equal probability.
For example consider this:
Let P5(i) = Probability of generating i using rand5(). P5(i) = 1/6 for 0<=i<=5
Let P7(i) = Probability of generating i using rand7() and 0<=i<=7.
Now,
P7(0) = P5(0)*P5(0)*P5(0)*P5(0)*P5(0)*P5(0)*P5(0) = 1/(6^7)
Also,
P7(4) = P5(1)*P5(3)*P5(0)*P5(0)*P5(0)*P5(0)*P5(0) +
P5(2)*P5(2)*P5(0)*P5(0)*P5(0)*P5(0)*P5(0) + many more combinations ...
= 1/(6^7) + 1/(6^7) + ...
int random(int n, int m)
{
Randomizer rand = new Randomizer();
int ans = 0;
int maxpow = maxpow(n, m);
while (ans < m)
{
int mult = 1;
while (mult < m)
{
ans += mult * rand(0, n);
mult *= n;
}
}
return ans;
}
sorry please ignore the maxpow call I meant to remove that....
Works by creating a base n number with max digits ceil[logn(m)]. If the number created is greater than m it retries until it gets it.
int random(int n, int m)
{
Randomizer rand = new Randomizer();
int ans;
while (ans < m)
{
int mult = 1;
ans = 0;
while (mult < m)
{
ans += mult * rand(0, n);
mult *= n;
}
}
return ans;
}
int random(int n, int m)
{
Randomizer rand = new Randomizer();
int ans = 0;
while (ans < m)
{
int mult = 1;
ans = 0;
while (mult < m)
{
ans += mult * rand(0, n);
mult *= n;
}
}
return ans;
}
I want to give a better explanation. If you consider the problem where u can only use the function rand2() to generate rand7() you can generate a random binary (base 2) string. in this example we would need 3 bits to get a number between 0 and 6. The possible solution set is:
000, 001, 010, 011, 100, 101, 110, and 111. They all have equal probabilities. If we get 111 (7) redo the algorithm. Notice the amount of digits is ceil(log2(7))
This can be generalized. In my solution we use randN and make a randM number. So we generate a baseN number with the amount of digits logN(M). If the solution is greater then M redo the random creation of the number.
I thought of a better generalization. Creating a base N number maybe problematic once you start getting to large numbers.
Instead we can reduce our randN function to a rand2 function then use the rand2 explanation above.
Reducing to randN to rand2 is easy. Assuming randN produces {0,1,...N}.
When N is even return (randN + 1) % 2
if N is odd let r = randN + 1. while (r != N) { r = randN + 1); This reduces the solution set down to an even amount of numbers giving equal probability to rand2.
while(true)
{
x = rand5()*5 + rand5() gives a random number from [0..25)
if x < 7*3
return x/3
else
continue
}
//generates random number 0 to 4
int rand4() {
return rand5() - 1;
}
//account only for pairs (0,1),...(0,5),(1,5),(2,5) where first element of tuple represents result of rand4, reject others
int rand7(){
int first, second, num;
do{
first = rand4();
second = rand5();
num = first + second;
}while !(first == 0 || (first == 1 && second==5) || (first==2 && second==5))
return num;
}
You could model
rand5 = rand1 * 5 ( rand1 gives random number 0 to 1)
rand7 = rand1* 7
hence
rand7 = rand5*7/5
generic
randN = rand5*N/5
probably this would help
- akie July 22, 2013geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/