Microsoft Interview Question
Software Engineer / DevelopersTeam: Windows Live
Country: United States
Interview Type: In-Person
I agree. But the issue is, the worst case would be range = (2^32 - 1) / 2 + 1 and then mod will be (2^32 - 1) / 2 - 1. The possibility of number > (2^32 - 1 - mod) will be around 1/2 for each loop. The possibility of a infinite loop will be extremely low after several rounds, say 20 rounds.
The possibility of loop continue will be as low as 1 / (2^20). I think the above solution will be good enough for the question. Point me out if I am wrong, thx
If you are that worried about an infinite loop just put a maximum loop limit like 100. If it hits that just return a number using the nonuniform function.
I actually just more or less proposed the same solution in another comment. Oracle's JVM implementation's Random class uses this approach.
i agreee but in this types of question dat issue dat worst case wpuld be range (26^32-1)/2+1;will be around 1/2 for each loop and only unlimited worst case execution time only
I would use something like that:
public uint Random(uint r1, uint r2)
{
if (r2 < r1)
{
throw new ArgumentException();
}
uint r;
uint range = r2 - r1 + 1;
if (range == 0)
{
return Random();
}
uint limit = uint.MaxValue - uint.MaxValue % range;
do
{
r = Random();
}
while (r >= limit);
return r % range + r1;
}
The worst case is when the range is equals to uint.MaxValue/2 + 1. It means that probability of condition in the loop to be true is about 1/2. It means that expected value of Random() calls in Random(r1, r2) equals to 2. In others cases expected value will be close to 1. So number of calls inside Random(r1, r2) can be very large, but there expected value in worst case is 2 and about 1 in most cases, this is not too bad.
It is not so simple. The result will not be equally distributed over the region. See other answers for discussion.
Everyone is using modulus. As people pointed out, this will lead to slightly non-uniform probability.
We should use divide
x = r1 + ( random() / Int32.MaxValue ) * ( r2 - r1 )
probability of the same number coming out is very high:
like R1=100 and R2=200
so for numbers like 1057,2057 ... it will return the same random number in that range.....
how about this
int GenRand(int R1, int R2)
{
return R1 + (((double)rand() / (double)RAND_MAX) * (R2 - R1 + 1));
}
@saurabhrungta,
The probability of other numbers will also be (almost) same...
The only difference will be for the numbers which [for max N] x=2^32-N*(R2-R1) and x>0. The probability for x will be slightly higher then others. and that will be in ration (N+1):N
@vishnu... : There's a very simple fix. Namely, you just get another random number if you happen to be in that range that you mention. This event has prob. < 1/2 even for the worst inputs, so this fix at most doubles the running time.
I recommend readers refer to the (open-source) implementation of this kind of function in the Random class of Oracle's JVM implementation. The exact technique I describe is used.
will this work?
- HT January 17, 2012int randomR1R2(int R1, int R2) {
int range = R2 - R1 + 1;
int mod = (2^32 - 1) % range;
int number = -1'
do {
number = randomInt(); //randomInt()returns a random integer between 0 and integer max (2^32 - 1) on a 32bit machine
}while (number > (2^32 - 1 - mod))
return number % range +R1;
}