A9 Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
how about this one?
x = sum ( result of rand(5) called 7 times)
return [(x mod 7)+1]
there is a possibility that your code won't exit at all...
also.. can u give a condition when your code returns
6 or 7
i couldn't find one...
to 6
a = 0, b = 1
a = 2, b = 2
a = 4, b = 3
to 7
a = 1, b = 1
a = 3, b = 2
a = 0, b = 3
those are the conditions to get 6 or 7
Yep, there are exactly 3 situations in which the code returns each digit. Equiprobable.
@sravanreddy001:
Your algorithm
x = sum ( result of rand(5) called 7 times)
return [(x mod 7)+1]
will NOT work. No approach that involves summing a bunch of values distributed uniformly at random is going to yield another value distributed uniformly at random (because of the central limit theorem). You really do need to use this try-and-repeat approach.
The probability that the code hasn't exited converges exponentially towards zero with the number of loops made. I suppose a real-world implementation would probably include a loop limit.
int rand7() //random number from 1 - 7
{
int r = 0;
int a = rand(5) - 1;
int b = rand(5) - 1;
r = 6*b + a; //28
return r % 7 + 1;
}
@eugene.yarovoi: I would like to know whether this distribution is random.
this is not truly random. 6b+a will produce numbers from 0-28 total of 29 numbers. so all numbers 1-7 does not have equal probability.
No solution that involves calling rand5() only a fixed number of times can be correct. That's because calling rand5() n times gives you 5^n possible outcomes, and no number of this form is divisble by 7. The potentially-infinite loop is the only way to do this correctly.
hw abt this.. wt do u guys think ?
int from1to5() {
return (rand()%5)+1;
}
int main() {
int rand1=from1to5();
int rand2=from1to5();
if(rand1==rand2) {
cout << rand1 << endl;
}
else if(rand1<rand2) {
cout << rand2+1;
}
else if(rand1>rand2) {
cout << rand1+2;
}
getch();
return 0;
}
@knoesis: nope. For one, 0 has quite a low chance of coming up - only 1/25. Which underlines the problem: no matter what probability each number has of coming up, it will take the form of some value k over some power of 5, which won't be equal to 1/7. In fact, the infinite loop is essentially expressing 1/7 in terms of powers of five: since it can't be done with a finite amount of terms, it has to be an infinite series. 1/7 = 3/25 (1 + 4/25 + (4/25)^2 + ...)
@danielpiedrahita : Small correction in your combination to generate 7 , its a = 0, b = 4.
@eugene.yarovoi
how did you come with the multiplication factor of 5 and limited value of r<20. if we had r(6) and we had to write r(8) using r(6) what should be the nos ?
Here's how. By calling rand5() twice and combining them using 5*firstValue + lastValue, I got a number uniformly at random between 0 and 24 (see why?). Now, I simply decided to accept only numbers between 0 and 20, since those numbers taken mod 7 give each value mod 7 exactly 3 opportunities to come up. So thus far things are equiprobable. Now what to do for the range 21-24? Since there's 4 numbers in that range and no way to distribute 4 numbers into 7 buckets equally, I simply roll again.
If you wanted to make rand8 with rand6, you'd be looking at rolling twice to get a number from 0 to 35 uniformly at random. Then you'd accept 0-31 (gives each number mod 8 four opportunities to occur), and you'd roll again for 32-35. But that would be kind of dumb for 6 and 8, because some numbers of the form 6^N are divisible by 8. You could actually roll exactly 3 times, get a number in the range 0-215 and take that modulo 8. Since each bucket would have 27 values exactly, this would be equiprobable. No such finite solution is available for 5 and 7 because they are coprime. More generally, the roll number needs to contain all the distinct prime factors contained in the target number for a finite solution to be available. 5 does not have as factors all the distinct prime factors of 7. 6 does in fact have as factors all the distinct prime factors of 8.
@eugene. Thanks for the explanation. Why do you even have to accept up to 21? How about the below change to your code?
do
{
-----
} while(r>=7);
return r+1;
That would work. It would just be less efficient because we'd have an expectation of 25/7 rolls instead of 25/21 rolls. it would be a constant factor less efficient.
Wondering why this works - (Though must admit this works perfectly well). The key here is to get up to n^2 eg. for the given input case of 5 and 7. I tried 4*a + b (expecting to give random numbers in the range 0 to 16 - that didn't work). Tried a more general solution -- below .. Is there a way of getting this to work when m > n^2?
#### Given a random number generator from 1 to n, generate a random number
#### from 1 to m (m > n)
import random
def randN(n):
return random.randint(1,n)
def randM(m,n):
a = randN(n) - 1
b = randN(n) - 1
r = n*a + b
if r > max :
return None
return r
m = 15
n = 5
a = [0] * m
max = n * n
max = max - max % m
print max
max = max - 1
for i in range(100000):
r = randM(m,n)
while r is None:
r = randM(m,n)
r = r % m
a[r] = a[r] + 1
print a
As usual - proper indentation is left as an exercise!
//Binary random - return 0 and 1 uniformly
br(1){
while (1){
t = r(5);
if (t == 1){
return 0;
} else if (t == 2) {
return 1;
} else { //re-generate t, this preserves the randomness
//Do nothing
}
}
}
//This function returns number 1-7 randomly
r(7) {
while (1){
a = br(1);
b = br(1);
c = br(1);
if (a == 0, b == 0, c ==0){ //re-generate a b c in this case.
//do nothing
}
else if (a == 0, b == 0, c ==1)
return 1;
else if (a == 0, b == 1, c ==0)
return 2;
else if (a == 0, b == 1, c ==1)
return 3;
else if (a == 1, b == 0, c ==0)
return 4;
else if (a == 1, b == 0, c ==1)
return 5;
else if (a == 1, b == 1, c ==0)
return 6;
else if (a == 1, b == 1, c ==1)
return 7;
}
}
Okay, this might be cheating, but nobody said "integers only".
randfive()- returns a number from 1.0 to 5.0 (a range of 4.0)
We need "randseven()" - that will return a number from 1.0 to 7.0 (a range of 6.0)
So:
randseven() = round(((randfive() - 1.0) * 1.5) + 1.0)
int randseven()
{
int a = randfive()%2;
int b = randfive()%2;
int c = randfive()%2;
if((a==0)&&(b==0)&&(c==0))
return 1;
else
return (a*pow(2,2)+b*pow(2,1)+c*pow(2,0));
}
Nishank, can you please clarify how the outcome has uniform distribution? If randfive() produces values in the set { 1, 2, 3, 4, 5 }, then the odds (sic) for drawing an odd number is 3/5.
Or is the output of randfive() supposed to be a closed interval at either end?
thanks.
See the link below
http://gist.github.com/105929
This link has a better solution which is uniformly distributed.
If it's not an integer then the ans. is pretty simple. Use rand5() to get rand1()=rand5()/5;
and use rand1() to get rand7() = rand1()*7
randfive()==1 => result=1
randfive()==2 => result=3
randfive()==3 => result=4
randfive()==4 => result=5
randfive()==5 => result=7
...so, 2 and 6 will not be generated
int some_sum=randfive()+randfive()+randfive()+randfive()+randfive()+randfive()+randfive();//some number between 7 and 35
return some_sum/5;
int rand7()
{
int a1=rand5();
int a2=rand5();
int a3=rand5();
int a4=rand5();
int a5=rand5();
int num=(((a1+a2+a3+a4+a5); //range= 5-25 genrating 21 random numbers with equal probability
return ((num%7)+1); //because numbers between 1-7
}
Why isnt the probabilty uniform?
n n%7 (n%7)+1
5 5 6
6 6 7 x f(x)
7 0 1 1 3
8 1 2 2 3
9 2 3 3 3
10 3 4 4 3
11 4 5 5 3
12 5 6 6 3
13 6 7 7 3
14 0 1 21
15 1 2
16 2 3
17 3 4
18 4 5
19 5 6
20 6 7
21 0 1
22 1 2
23 2 3
24 3 4
25 4 5
probablity of each =1/7
It would be if the probabilities of individual sums were uniform, but they are not.
Following your approach: the outcome 1 would occur if the sum of a1,..,a5 is either 7, 14, or 21. The probability of getting 7 is 15/3125 (3125 is 5^5), the probability of getting 14 is 365/3125 and the probability of getting 21 is 70/3125. Thus the final outcome 1 occurs with the probability of 450/3125, which incidently is close to 1/7 but it's not the same.
Please note that regardless how many times you would run rand5 in a row you'd never get the exact 1/7.
rand5() : take 1 if no < 3 take 0 if >3
if = 3 repeat
This done 3 times generate 0-7 each prob 1/8 if 0 comes repeat the process then each has 1/64 but all in all 1-7 have equal prob to come
This gives uniform distribution
int rand7()
{
return rand5() + ((rand5() + rand5())%3);
}
How is this uniform?
Rand5() + Rand5()
= with a set { 2,3,3,4,4,4,5,5,5,5,6,6,6,6,6,7,7,7,7,8,8,8,9,9,10}
1 - 2
2 - 3
3 - 4
4 - 5
5 - 6
4 - 7
3 - 8
2 - 9
1 - 10
if we % 3 to the set
{2, 0 , 0, 1, 1, 1, 2, 2, 2, 2, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 0, 0, 1}
So we end up with
8 - 2's
8 - 1's
9 - 0's
Hence, not uniformly distributed. (Rand5() + Rand5()) %3 will not work
function [n] = rand7()
K = 0;
for i=1:6
K = 10*K + randi(5);
end
n = 1 + mod(K,7);
end
This builds a number from 1 to 555,555, each value with equal probability. We build by randomly generating each decimal digit. The number 555,555 is the first divisible by 7 that we can build with rand5(), hence, there is an equal probability to generate the modulo reminders.
We return 1 + mod(n,7) as the final answer.
The code is MATLAB, you can run on a large array and convince yourself f the correctness. As long as rand5() is deterministic, this one is deterministic as well.
Thanks!
I got ahead of myself above. The function does not generate all the numbers. Here is a non-deterministic, correct solution:
function [n] = rand7()
K = inf;
while(K>20)
K = 5*(randi(5)-1) + (randi(5)-1);
end
n = mod(K,7)+1;
end
We use rand5() to build a two-digit number in base 5 (0~24). We disregard values above 20, and return a modulo answer + 1 from that. Note that disregarding the values 21, 22, 23 does not change the fact that the numbers from 0~20 have equal odds.
Thanks!
To be more specific: call randfive() twice to get an ordered pair <n,m> of random numbers. There are 25 such pairs. Arbitrarily choose 21 of them to be in your sample space. Distribute these pairs evenly (however you like) among the numbers 1 through 7. This maps your two calls of randfive() to an output of randseven(). If you happen to get one of the remaining 4 pairs when you call randfive(), you just reject the outcome and do the procedure again.
I think this could work
function int random() //random number from 1 - 7
{
int a = r(5);
int b = r(5);
int r = a + b; (number from 2 to 10)
r = r - 2; (max number 8)
if(r == 8) // because never gonna get number 1,
{
r = 1;
}
return r;
}
i think ur distribution is correct but there would be some minor changes:
public int my_rand(int n)
{
int i;
int a=randomNumber(n)+1;
int b=randomNumber(n)+1;
System.out.println("a="+a);
System.out.println("b="+b);
i=a +b; // 2 to 10
i=i-1;
if(i==8 || i== 9)
return my_rand(n);
return i;
// return my_rand(n);
}
int rand()
{
int a=r(5)-1;//random(0-4)
int b=r(5)-1;//random(0-4)
int c=a+b;;//random(0-8)
if(c==0||c==8)
c=rand();//recursively distributing (0-8) over(1-7)
return c;
}
Consider this array:
0 0 0
1 0 1
0 1 0
0 1 1
1 0 0
Notice that every column has 2 ones and 3 zeros.
Random7()
Call Random5 method to chose index from 1 to 5. say ind1.
Keep calling Random5 utmost 5 times till you get another ind2 so that ind2 != ind1.
Now return ind1 XOR ind2.
Code:
int Random7()
{
Byte[][] byteMatrix= { (0,0,0},...};
int firstRand = Random5();
int currRand - firstRand;
while(firstRand != (currRand = Random(5));
return firstRand ^ currRand;
}
This should be fine:
int randY()
{
int a=rand(5)-1; //0-4
int b=rand(5)-1; //0-4
int c=2^a+b; // 1-20
int d=c%7;
return d;
}
1.Generate a random number between 1-5 say 1 using rand()%(5-1+1)+1
2.multiply it with 3 ,now my range will lie between 3-15 ,my number becomes 3
3.subtract by 1 range will become 2-14 ,my number becomes 2
4.Divide it by 2 will gibe the number between range 1-7 ,in my case it is 1;
Not correct. I immediately know it's wrong by the simple fact that you call rand5() only once. Think about it. If there are only 5 possible inputs to your program (the 5 possible outcomes of rand()%5), how can there be all 7 possible outputs? Everything else is deterministic. In fact, see the comments to my post for an explanation of why every correct solution can have no strict upper bound on the number of times random5() may need to be called (but can still have a constant number of calls in the expectation).
You need to normalize according to the range and the lower limit.
int rand7()
{
return round(1 + (7-1)*(rand5() - 1)/(5-1) )
}
Nope. The rand(5) in this problem doesn't give you something random in a continuous interval; rather, it gives you an integer.
If further explanation is required: rand(5) only produces 5 possible outputs. If those are the inputs to the rand7() function you're trying to build, your rand7() function can have at most 5 possible outputs, which is certainly wrong.
Random number generator for number 1-25 using above same PRNGs
random25{
do {
a=rand() - 1;//0-4
b=rand() -1; //0-4
n = 12a + b; // 52
}while(n>=50);
return (n%25 +1);
}
the above random function will generate 1-25 number without equal probability..... let me know if i m wrong.
and random number generator for 1-7
random7()
{
a=rand() - 1; // 0-4
b=rand() - 1; //0-4
n=3a + b;
}while(n>=14);
rnd=n%7 + 1;
tadaaaa
Random number generator for number 1-25 using above same PRNGs
random25{
do {
a=rand() - 1;//0-4
b=rand() -1; //0-4
n = 12a + b; // 52
}while(n>=50);
return (n%25 +1);
}
the above random function will generate 1-25 number without equal probability..... let me know if i m wrong.
let make it easier
a=rand()
b=rand()
return (5(a-1) + b)
and random number generator for 1-7
random7()
{
a=rand() - 1; // 0-4
b=rand() - 1; //0-4
n=3a + b;
}while(n>=14);
rnd=n%7 + 1;
tadaaaa
1.run randfive() twice to generate two numbers a and b.
2.generate a new number c = (a-1)*5+(b-1) (24>=c>=0)
3.if 24>=c>=21, go back to step 1.
4.else return c%7+1 as the random number.
1. using randfive write a function (rand_0_or_1) to generate no 0 or 1 with uniform probablity
2. use rand_0_or_1 in randseven to generate no between 1 to 7 with uniform probability
Hint - call rand_0_or_1 3 times.
Because integers are discrete, to make a long story short.
You see, the rand(5) in this problem doesn't give you something random in a continuous interval; rather, it gives you an integer.
If further explanation is required: rand(5) only produces 5 possible outputs. If those are the inputs to the rand7() function you're trying to build, your rand7() function can have at most 5 possible outputs, which is certainly wrong.
This probably isn't the most efficient method but it definitely works.
1. Use rand5() to generate an array of 7 random numbers between 1 and 5.
2. Find the index of the max of the array--if there is no tie, return this as result of rand7()
3. In case of a tie, repeat steps 1 and 2 (for however many elements are tied) until there is a winner--this is your rand7()
- eugene.yarovoi January 19, 2012int rand7() //random number from 1 - 7 { int r = 0; do { int a = rand(5) - 1; //uniformly at random from 0 to 4 int b = rand(5) - 1; //uniformly at random from 0 to 4 r = 5*b + a; //uniformly at random from 0 to 24 } while (r >= 21); // in this event, we have to roll again //postcondition of loop: we have a number uniformly at random between 0 and 20 return r % 7 + 1; //there are 3 numbers in [0, 20] for each possible return value //so each has equal probability. }