## Amazon Interview Question

• 0

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

Plz Help

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

hi.
simply use this rand generator as bit filler.
( rand() << 1 + rand() ) << 1 + .. + rand() //9 times
the problem would be with 0, 1001, 1002, ... 1023 => regenerate to have probability equal to 1/1000.

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

you can just ignore these : 0, 1001, 1002, ... 1023, and rerun if that happens.
still guarantee equal prob.

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

Can you please elaborate .... I did not understood .... that would be of great help ......... and anyways n was lying between [1 , 1000].

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

First generate N (0<N<1024) :
func()
{
unsigned int N = 0;
unsigned int n = sizeof(unsigned int) - 1; // I'll recommend n to be as large as possible

//First generate a random N (0<= N<= 2^n) :
for (i = 0; i < n; i++)
N = (N << 1) | rand(); // rand() generates either 0 or 1 randomly

// Now scale N so that 0 <= N <= 1000
N = (int)((float)N/ ((pow(2,n)-1) ) * 1000);

}

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

I am sorry for not explaining my logic. Here it is:
First generate a large N (as large possible) by filling its bit positions with rand(). this will ensure that probability of every no. in this large universe is equal. Now scale this N to a no. between 0 to 1000.
Here comes the utility of choosing a large universe earlier. Since you need to make the resulting probability equal (or I say almost equal) you need to choose the universe large so as to minimize the difference between the smallest and largest probability. These probabilities would be given as :
// M is the largest no. of the universe used to generate N
Smallest prob = Floor(M/1000)
Largest prob = ceil(M/1000)

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

First generate N (0<N<1024) :
func()
{
unsigned int N = 0;
unsigned int n = sizeof(unsigned int) - 1; // I'll recommend n to be as large as possible

//First generate a random N (0<= N<= 2^n) :
for (i = 0; i < n; i++)
N = (N << 1) | rand(); // rand() generates either 0 or 1 randomly

// Now scale N so that 1 <= N <= 1000
N = 1 + ((int)((float)N /(pow(2,n)) * 1000) );
// 1 + 0 <= number <=999
}

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

the logic is this.
1. generate the 0 or 1
2. bit shift that 0 or 1 by 1 bit position to the left
3. do it 10 times (10 because 2^10 = 1024)
4. return the number

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

sorry incomplete algo

the logic is this.
1. generate the 0 or 1
2. bit shift that 0 or 1 by 1 bit position to the left
3. bitwise OR the shifted number with the next generate 0 1
4. do it 10 times (10 because 2^10 = 1024)
5. return the number

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

{
public static int bitbitbit()
{
int num = 0;
Random rand = new Random();
num = rand.nextInt(2); //generate 0 or 1
num = num << 1; //bitwise shift num by 1 to the left
for(int i=0; i<8; i++)
{
num = num | rand.nextInt(2);
num = num << 1;

}

return num;
}
}

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

<pre lang="" line="1" title="CodeMonkey56060" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static int bitbitbit()
{
int num = 0;
Random rand = new Random();
num = rand.nextInt(2); //generate 0 or 1
num = num << 1; //bitwise shift num by 1 to the left
for(int i=0; i<8; i++)
{
num = num | rand.nextInt(2);
num = num << 1;

}

return num;
}
}

</pre><pre title="CodeMonkey56060" input="yes">
</pre>

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

This above code gave me an output of 1020 too..

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

1. Divide the set of 1 - 1000 numbers into two: 1-500, 501 to 1000
2. Use the rand() method for generating random number of 0 or 1, based on its result choose 1-500 if its 0 and 501 to 1000 if its one
3. Repeat step two for the selected set being divided into two halves - e.g. if 0 was returned earlier, divide it into 1-250 and 251-500 and select 1-250 if rand returns 0 and 251-500 if it returns 1
4. We repeat step 2 and 3 until only one number is left. That will be our random number.

We will do log(N) steps to calculate this.

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.