## Amazon Interview Question for SDE1s

• 4

Country: India
Interview Type: In-Person

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

My solution is similar to dalvik_king's solution:
It generates 25 numbers (0 - 24) with same probability and since 21 = 3*7 and 25-21 = 4 we discard these 4 numbers (by trying again) and return x%7 where x is between 0 and 20 and for each possible result modulus 7 (0-6) we have 3 possibilities, so the probability is the same.

``````static public int rand7() {
result = 0;
while (result >= 21)
result = rand5()*5 + rand5();
return result%7;
}``````

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

You need to initialize result to 21 so that it goes into the loop!

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

Thanks PJ, that's right. Let this one pass.

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

I tried to play with this to do better but this is probably the simplest way to use rand(5) without clobbering the likely hood of generating any particular number.

Did you come up with this off the top of your head?

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

``````static public int rand7() {

// This will gives us a result of
// 0 to 7 (binary 000 to 111)
// which should be evenly distributed.
// reject 7 so we have 0 to 6
int result = 7;
while (result == 7) {
result = randBit() * 4 + randBit() * 2 + randBit();
}

return result;
}

// gets a random 0 or 1
static public int randBit() {

// Eliminate zero so we have an equal number
// of even/odd values (1, 2, 3, or 4)
int result = 0;
while (result == 0) {
result = rand5();
}

return result % 2;
}``````

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

int rand7()
{
int vals = {
{ 1, 2, 3, 4, 5 },
{ 6, 7, 1, 2, 3 },
{ 4, 5, 6, 7, 1 },
{ 2, 3, 4, 5, 6 },
{ 7, 0, 0, 0, 0 }
};

int result = 0;
while (result == 0)
{
int i = rand5();
int j = rand5();
result = vals[i-1][j-1];
}
return result;
}

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

Two words: Stack Overflow :D

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

This solution consider two random generator from 1 to 5 and from 1 to 7, that is not what is required here. Next time, before copying and pasting, compare better the assignment. :)

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

I feel it should be something like

``````int rand7()
{
return ( rand5()*7 + rand5() )%7;
}``````

This should preserve the uniformity. In fact, rand5()*7 + rand5() provides a number between 0 and 34 and there's only one way to generate each of these 35 numbers. Also, since 0%7=0 and 34%7=6, you have that all numbers between 0 and 34 are transformed to a number between 0 and 6 with the same probability.

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

I found out this doesn't really work this way.

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

``````public class Random7 {

public static int val=0;
public int random7(){
return (new Random().nextInt(5)*5 +new Random().nextInt(5) )%7;
}
}``````

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

Thi is not correct as 25 is not divisible by 7. Some numbers will have bigger probability of getting generted

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

So close to the correct answer. Use the comment above as a guide to make it uniform.
Hint: An infinite loop might be needed.

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

There are many ways to solve this problem, below is my attempt

``````int rand7()
{
int k = rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5();
return k % 7;
}``````

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

Hey buddy, are you sure we have a uniform distribution here?

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

Yes, he does. I checked it

``````static void Main(string[] args)
{
Random r5 = new Random();

Dictionary<int, int> stats = new Dictionary<int,int>();
for(int i=0; i < 7; i++)
stats[i] = 0;

for (int i = 0; i < ITERATIONS; i++)
{
int res = (r5.Next(5) + r5.Next(5) + r5.Next(5) + r5.Next(5) + r5.Next(5) + r5.Next(5) + r5.Next(5)) % 7;
stats[res] = stats[res] + 1;
}

Console.WriteLine("Results:");

for (int i = 0; i < 7; i++)
{
double cnt = stats[i];
double percentage = (cnt / ITERATIONS) * 100;
Console.WriteLine(i.ToString() + " = " + percentage);
}
}``````

ITERATIONS = 1,000,000.

Language is VS C#.

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

Only one combination to generate 0 from that.

Yet there are 7 different permutations to generate 1.

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

If all are 1's 2's ...5's also the result will be zero...I think this logic works.

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

rand5 is not the random of .NET

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

If all are 1's 2's ...5's also the result will be zero...I think this logic works.

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

Combining 7 independent events does not make for a random distribution.
Think Craps: 1 die is a random number generator 1-6 with equal probability for each number. With 2 die the odds of rolling a 7 is way more likely than rolling a 2.

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

does rand(5) generate real numbers between 0 and 4, or only integers? the below works for real numbers:

return (((rand(5) + 1) * 7) - 1) / 5;

(note that the division by 5 is integer division)

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

(((rand(5) + 1) * 7) - 1) / 7;

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

This is a general solution that works for any +ve integer with a equal dristribution.
for this question n is 7 and m is 5

so rand_5() is given, which has been represented as rand_m below. The point is we need to find random of N where random of m is given.
Calculating the factor value is what trivial here...
for this example
7x-1 has to be divisible by 4 for a smallest integer value of x. and then (7x-1)/4 = 5 (where x = 3), so 5 is the factor.
so (rand_5 + rand_5 + rand_5 + rand_5 + rand_5)%7 is the result.
above sum can generate values in range of "0 to 20" with equal distribution, that means equal number of change (3 chances of each value) of getting 0 to 6.

static int getRandom(int n, int m) {
int i = 1;
while((n*i-1)%(m-1) != 0) i++;

int factor = (n*i-1)/(m-1);

int randomSum = 0;

while(factor > 0){
randomSum += rand_m();
factor--;
}
return randomSum%n;
}

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

Use the previous ideas only add rejection sampling. S that the number taken into acciunt be divisible by 7

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

rand(5) + rand(5)%2

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

Or

``````int rand7() {
int rand5 = rand(5);
return rand5 + (rand5 % 2);
}``````

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

Not uniform.

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

Why not?

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

Well, we can count the number of the ways that we can obtain a given value in the range (0,6). For example, let's count the number of possible ways of obtaining 0 and 1.

For 0 we have: 1st rand == 0 and ( 2nd rand == 0 or 2 or 4 ) so we can make a 0 in three ways.

For 1 we have: [ 1st rand == 0 and ( 2nd rand == 1 or 3 ) ] + [ 1st rand == 1 and ( 2nd rand == 0 or 2 or 4 ) ] so there are five possible ways to get a 1.

That's why :-P

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

num = rand(5) + rand(5);
return(num%7);

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

Not uniform.
The ways that we can get a 0: (0, 0) , (3, 4) , (4, 3)
The ways that we can get a 4: (0, 4) , (4, 0) , (1, 3) , (3, 1) , (2, 2)

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

I think we can use rand5 to implementation rand2 and rand10 first.
int rand2()
{
int k = 0;
do
{
k= rand5();
}
while(k > 2);
return k;
}

int rand10()
{
return rand2() * 5 + rand5();
}

for the rand7(). we can use rand10 to implementation:
int rand7()
{ k = 0;
do
{
k = rand10();
}while(k > 7);
return k;

}

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

Doesn't this work?

``````int rand7() {
return rand(3) + rand(4);
}``````

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

@All, this question has been discussed quite well on Stack Overflow, just google for "rand 5 to rand 7"

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

Thanks hulk for posting this problem. It refreshes some discrete math skills, which is great!

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

int randomNumber = random.nextInt(max - min) + min;

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

``````int rand7()
{
int x,y,z,n=0;
while((x=rand5())==2);
x/=2;
while((y=rand5())==2);
y/=2;
while((z=rand5())==2);
z/=2;
n=4*x+2*y+1*z;
return n;
}``````

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

``````package com.test.careercup;

import java.util.Random;

public class Test {

public static void main(String[] arg)
{
System.out.println("int : "+rand(7));
}
public static int rand(int maxNum)
{
Random r=new Random();
return r.nextInt(maxNum);

}
}``````

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

rand(5) + (int)rand(5)/2

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

I believe it should be simple. Just get sum of two rand5 values and find its mod according to 7;

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

lets test it with extreme and normal values;
both rand5 functions generate 0;
(0 + 0) % 7 = 0 <--- in the range
both rand5 functions generate 4;
(4 + 4) % 7 = 1 <--- in the range
both rand5 functions generate 3;
(3 + 3) % 7 = 6 <--- in the range

hmm looks ok but lets test if we can generate every number in the range;

2 and 3 generated and we got 5
2 and 2 generated and we got 4
1 and 2 generated and we got 3

looks like we can generate every number in the range. Only problem here is that the possibilities of the outcomes are not same. Since the question is not telling about the possibilities, I believe this should be the simplest answer.

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

int rand7()
{
return ( ((float)rand5() / 5.0f ) * 7.0f);
}

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

``````int get_rand7_from_rand5()
{
int rnd;
do {
int x = rand5(); //generates one of 0,1,2,3,4
int y = rand5(); //generates one of 0,1,2,3,4
rnd = 5*x + y; // generates a number between 0 to 24
} while (rnd > 20)
return rnd % 7;
//for numbers between 0 to 20 : if we take modulo 7 we can see that probability of picking 0 is 3/21 (for 0, 7 and 14), probability of picking 1 is 3/21 (for 1, 8, 15). Similarly for 2, 3, 4, 5 and 6. Hence any number between 0 to 6 has equal probability.
}
//probability of the while loop running n times before it returns is (4/25)^n``````

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

``````int rand7(){
int num=rand5()+1;
int result=0;

for(int i=0;i<num;i++){
result += rand5();
}

return result%7;
}``````

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

``````int rand7(){
int num=rand5()+1;
int result=0;

for(int i=0;i<num;i++){
result += rand5();
}

return result%7;
}``````

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

rand5() generates the values from 0 to 4 i.e., 0,1,2,3,4
expected is 0 to 6, i.e., 0,1,2,3,4,5,6 . using rand5().

My solution is:
rand7() = rand5() + rand5()/2

Example: Assume first rand5 is generating 4, and second rand5 is generating 0 to 4, then
rand5() + rand5()/2 will have following values for rand7() i.e, 4,5,6

4, ==> 4,5,6

4 + 0/2 = 4
4 + 1/2 = 4
4 + 2/2 = 5
4 + 3/2 = 5
4 + 4/2 = 6

repeat for 1, ==> 1,2,3

1 + 0/2 = 1
1 + 1/2 = 1
1 + 2/2 = 2
1 + 3/2 = 2
1 + 4/2 = 3

repeat for 1, ==> 1,2,3

0 + 0/2 = 0

Example: Assume rand5 is generating 4, then
rand

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.