## A9 Amazon Interview Question for Software Engineer / Developers

• 0

Country: United States
Interview Type: Phone Interview

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

``````int 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.
}``````

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

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

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

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

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

Yep, there are exactly 3 situations in which the code returns each digit. Equiprobable.

@sravanreddy001:

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.

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

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

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

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.

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

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.

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

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

Comment hidden because of low score. Click to expand.
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 + ...)

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

@danielpiedrahita : Small correction in your combination to generate 7 , its a = 0, b = 4.

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

@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 ?

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

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.

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

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

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

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.

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

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!

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

``R(7) = R(5) + R(5)%3``

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

a = rand(5)
b = rand(5)
roll again if a+b > 7
else return a+b
doesn't fall afoul of the Central Limit Theorem, does it?
Expected number of rolls = 10/7, not as good as 25/21, admittedly.

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

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

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

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)

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

Why the round at the end?

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

Your method does not produce uniform random numbers:

For example:
To get 2: 2=1+1; 2=9 mod 7(9=4+5=5+4)
To get 5: 5=4+1=4+1=2+3=3+2

In other word, the probability to get 5 is larger that to get 2.

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

7 * 4 = 28 rand (0, 4) do 7 times mod % 7 + 1

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

actually still not uniform

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

1. using randfive write a function (rand_0_or_1) to generate no 0 or 1 with uniform probablity.

I think that this would eventually work. Is number for each? Repeat with prob 0.5 for those that yielded yes. This would actually mean pick with equal probability..

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

number%5=randfive();
number=(k*5)+randfive();
randseven()=((k*5)+randfive())%7;

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

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

Comment hidden because of low score. Click to expand.
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.

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

int randseven()
{
int a = randfive()%2;
int b = randfive()%2;
int c = randfive()%2;
if((a==0)&&(b==0)&&(c==0))
//return 1;
return randseven();
/*if we write return 1 then probablity of getting 1 is slightly higher than other cases.*/
else
return (a*pow(2,2)+b*pow(2,1)+c*pow(2,0));
}

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

there does not seem to be a good answer here...guys c'on...

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

http://gist.github.com/105929
This link has a better solution which is uniformly distributed.

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

the given link does not contain a good answer, its teh same what somene has already mentioend here....generating random number between 1 and 21 and then %7...sucks!

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

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

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

seriously, what is rand1() ??
If E= rand5()/5;
Then, P(E=0) =4/5
P(E=1)= 1/5

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

7*randfive()/5

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

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;

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

mr's reasoning is correct and your solution will never give purely random answers: junma

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

1. Use randfive to generate a number.
If it's 3 try again.
Otherwise: record 0 if it's less than 3 or 1 otherwise.
2. Repeat 1. three times.
3. If you got 3 0's start again.
4. Once you reach this point you have a binary representation of the result from 001 to 111.

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

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
}

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

The probability is not equal.
For example, p(5)=1/5^5, p(6)=5/5^5, p(7)=15/5^5, etc.

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

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

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

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.

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

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

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

Basically you are using base 2 but since we are given base 5 random already we can do that using base 5;
rand5() : take output - 1;

repeat 2 times.
if output greater than 6 repeat (you can also do output greater than 21 in decimel and return 21 mod 7 + 1) return output + 1;

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

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

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

prob of getting 2,4 >> prob of getting 7 here

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

awesome @ Anonymous

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

This gives uniform distribution
int rand7()
{
return rand5() + ((rand5() + rand5())%3);
}

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

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

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

This question cannot be solved in deterministic time,this is the clue that gayle had given me when I asked her.

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

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

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

i didn't see how your function generates a uniform distribution from 1 through 555,555. what's the probability of generating the number 6 in your function?

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

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!

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

Does this work, assuming the numbers need not be integers:

rand5()-1: Uniform distribution between 0 and 4
(rand5()-1)/2: Uniform distribution between 0 and 2

rand5() + (rand5()-1)/2: Uniform distribution between 1 and 7 ??

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

sorry that won't work.. ignore!

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

this is simpler problem in Probability & Stochastic Processes.
If X is uniform in [c1,d1], then aX+b is uniform in [c2,d2] where a=d2-c2/(d1-c1) & a*c1+b=c2.

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

This looks perfect to me!!

int rand7()
{
int num=rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5();
return ((num%7)+1); //because numbers between 1-7
}

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

int rand7()
{
int i, num=0, ans;
for(i=0;i<12;i++)
{
num = num+rand5();
}
num = num - 5;
ans = num/7;//returning the quotient
}//check it,its uniformly distributed

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

2 words: rejection sampling.

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

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.

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

The only way.
We can reduce the probability of a rejection by increasing the size of our ordered pair (vector)
For example if we ran randfive() 10 times the probability of rejection would decrease from 4/25 (about 12.5%) to 2/9,765,625 (about 10^-9 %)

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

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

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

-1 Incorrect. r is not distributed uniformly at random when it's the sum of a and b

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

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

}

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

No. It's not correct. Read about the "central limit theorem", or just make a table of all the possible combinations of a and b to see that i is not distributed uniformly at random.

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

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

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

The sum of two uniformly distributed numbers is not distributed uniformly. For the range [0:4] the distribution will looks like 1 2 3 4 5 4 3 2 1

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

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

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

This should be fine:

int randY()
{

}

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

BAZINGA !!!!

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

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;

}``````

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

Absolutely not. For one, it would have to be 0-20 to even have a chance. Then there's the fact that you called rand5() a fiuxed number of times, which also cannot possibly be correct, as I have argued in the comments to my post.

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

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;

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

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

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

You need to normalize according to the range and the lower limit.

``````int rand7()
{
return round(1 + (7-1)*(rand5() - 1)/(5-1) )
}``````

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

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.

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

``hello``

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

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;

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

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

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

``r(7) = r(5) + r(5)%3``

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

Best O(n) Solution, Express result as binary, convert if needed:

``````int main() {
string total = "XXX";
srand(time(0));

for (int x = 0; x < 3; x++)
{
if (((rand() % 5 + 1) + (rand() % 5 + 1)) > 5 )
total[x] =  '0';
else
total[x] = '1';
}
}``````

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

5*(rand5()-1) + (rand5()-1) doesn't give uniform distribution, because it assumes:

Uniform[0..20] + Uniform[0..4] = Uniform[0..24], which is incorrect:

P(24) = P(20) + P(4) = 2*P(any), while P(4) = (P(0) + P(4)) + (P(1) + P(3)) + (P(2) + P(2)) + ...

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

@TheShocker1999 you're generating a number between 0 and 7, not 1 and 7.

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

int rand(int max){
int rand = random() + random()-1;
while(rand >= max+1)rand =random() + random()-1;
return rand;
}

int random(){
int range = (5 - 1) + 1;
return (int)(Math.random() * range) + 1;
}

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

int rand(int max){
int rand = random() + random()-1;
while(rand >= max+1)rand =random() + random()-1;
return rand;

}

int random(){
int range = (5 - 1) + 1;
return (int)(Math.random() * range) + 1;
}

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

``````int rand(int max){
int rand = random() + random()-1;
while(rand >= max+1)rand =random() + random()-1;
return rand;
}
//Random function->
int random(){
int range = (5 - 1) + 1;
return (int)(Math.random() * range) + 1;
}``````

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

Both 7 and 5 are co-prime numbers. So it's not possible to uniformly generate 7 numbers using rand5().

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

int random7(){
int a=random5();
int b=random5();
if (a==1&&b==1)
return 1;
if (a==1&&b==2)
return 2;
if (a==1&&b==3)
return 3;
if (a==1&&b==4)
return 4;
if (a==1&&b==5)
return 5;
if (a==2&&b==1)
return 6;
if (a==2&&b==2)
return 7;

return random7();
}

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

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.

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

How do you get 5 or 6 in ur c%7 if its not going to be greater than 21.. anyway its not equal probability either..

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

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.

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

How does calling it 3 times satisfy??

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

Run randfive() twice and generate a and b.
Add a and b and determine c, c = a + b.
If c > 7, then take c = c mod 7.

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

ceil((rand(1,5)/5)*7)

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

Why isn't this the right approach?

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

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.

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

``return rand(5)+(rand(5)%3)``

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

No. Summing two random variables doesn't produce results that are distributed uniformly at random. And rand(5) % 3 is biased towards getting 0 and 1.

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

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()

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.