## Amazon Interview Question

• 0

Country: India

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

probably this would help
geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/

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

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.

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

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

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

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

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

@ Chih.Chiu.19

You seem to read and understand things in a hurry :-).

It has already been mentioned that his solution does not generate random numbers with equal probability.

>> If it is does not matter to generate numbers with equal probability, a simpler version could be:

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

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.

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

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)

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

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) + ...``````

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

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

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

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.

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

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

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

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

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

I suck at posting, I wish I could edit lol
sorry first post...

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

this way randm = ( rand5() + ( m - 5 ) ) % (m + 1) where m > 5

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

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.

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

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.

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

typo: randN should produce {0,1,...,N-1}

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

why to do so much.u can do it a simple way
rand(7) generate number between 0 to 7.
rand(5) generate no between 0 to 10 .o map this number to 0 to 7.
rand(7)=(rand(5)+rand(5))%8

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

while(true)
{
x = rand5()*5 + rand5() gives a random number from [0..25)
if x < 7*3
return x/3
else
continue
}

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

while(true)
{
x = rand5()*5 + rand5() gives a random number from [0..25) //it should be [0...30]
if x < 7*3
return x/3
else
continue
}

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

Submit

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

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

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

r = rand5() + 2;
any problem with this ?

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

how ll you get 0 and 1

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

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

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

Recheck the above solution

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

When u do rand5()*rand5(), it will not give any prime numbers and hence a%7 will not generate the numbers 1-7 with equal probability

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.