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