## Amazon Interview Question

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.

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

}

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)

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

}

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

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

How about this: Do a binary search for the number based on result of rand():

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.

Plz Help

- Mr X July 08, 2011