Akamai Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Written Test
modified an answer a lot:
a+(b-a)-(random()*(rand()%(b-a+1))
where rand() is built in function and random is user defined
test case:
a=100
b=250
answer:100+150-0 =250 if random is zero
if random is 1 ans is 100+150 -(1*120)=130
120 generated by built in rand
min will be 100 and max will be 250
It should be ceil(log(b-a+1)), but that's a minor implementation bug. The general approach is correct, and is the only correct solution on this page.
How abt this....?
int newrandom(int a,int b)
{ int sum = 0;
for(int i = 0; i <= b-a; i++)
sum+=random();
return (a+sum);
}
How abt this....?
int newrandom(int a,int b)
{ int sum = 0;
for(int i = 0; i <= b-a; i++)
sum+=random();
return (a+sum);
}
The binary-search idea is leading to this:
Split the interval of [a, b] into two half and use the first-half if rand() gives 0 and use the 2nd half if it gives 1. Continue this until the size of the interval is 1, and this will be the random number.
Even the splitting (when the size is odd) must use rand() on which mid to use (lower or upper-mid), otherwise (e.g. using always the lower-mid) leads to wrong distribution.
An even better solution is to use real numbers when splitting - until the interval contains only one integer (size of interval becomes less than 2)
The first solution's not correct. See my comments on the other binary search solution posted here. The second solution might actually be OK. Like Manan's solution, it's not guaranteed to terminate after any fixed number of iterations, a property that every correct solution has. It does seem to be truly random if implemented correctly.
I honestly do not understand how this is not terminating when the size of the interval gets smaller and smaller at each and every step. Can you give an example?
public class RandomFunctionEx {
public static void main(String[] args) {
System.out.println(random(4, 8));
}
static int random(int a, int b){
if(b < a)
return -1;
int diff = b - a;
int bits = (int) Math.ceil(Math.log(b-a+1)/Math.log(2));
int sum = findRandom(bits, diff);
return a+sum;
}
static int rand(){
return Math.random() > .5 ? 1 : 0;
}
static int findRandom(int numBits, int diff){
int num = 0;
for(int i = 0 ; i < numBits ; i++){
int x = rand() << i;
num = num | x;
}
if(num > diff){
System.out.println("calling again " + num);
num = findRandom(numBits, diff);
}
return num;
}
}
int random(int a, int b)
{
return(a+rand()/(b-a));
}
//it will return a if rand() generates 0
//it will return b if rand() generates (b-a)*(b-a)
Even assuming you meant * instead of /, the question seems to be to generate an integer in the range [a, b] inclusive.
Do something like binary search...
int random (int [] arr, int len)
{
if (len > 0)
return arr[random_util(arr, 0, len-1)];
else
ERROR
}
int random_util (int [] arr, int first, int last)
{
if (first == last) return first;
int mid = (first + last)/2;
if (rand()) {
return (random_util(arr, mid+1, last));
} else {
return (random_util(arr, first, mid));
}
}
I knew this solution had to be wrong the moment I saw it because it doesn't have the property of potentially looping an unbounded number of times, a property every correct solution must have. It took me a while to figure out exactly where it's wrong, as the solution does seem very compelling.
The issue is with the treatment of elements when middle elements are present - it's not correct to include the middle with 1/2 probability! Consider the case of [1 2 3]. Your approach gives 37.5% chance for 1 to be chosen instead of 33.3%. Close, but no cigar.
Do something like binary search...
int random (int [] arr, int len)
{
if (len > 0)
return arr[random_util(arr, 0, len-1)];
else
ERROR
}
int random_util (int [] arr, int first, int last)
{
if (first == last) return first;
int mid = (first + last)/2;
if (rand()) {
return (random_util(arr, mid+1, last));
} else {
return (random_util(arr, first, mid));
}
}
Do something like binary search...
int random (int [] arr, int len)
{
if (len > 0)
return arr[random_util(arr, 0, len-1)];
else
ERROR
}
int random_util (int [] arr, int first, int last)
{
if (first == last) return first;
int mid = (first + last)/2;
if (rand()) {
return (random_util(arr, mid+1, last));
} else {
return (random_util(arr, first, mid));
}
}
lets b>a
ra = a(1+rand()) //ra >= a
rb = b(1+rand()) //rb >= b
res = (ra+rb)%(b+1)
res would be a when rand() will give 0 //lower limit
res would be b when ra+rb will give b //upper limit
and for others it'll work fine
algo -
1) Approximate ( b-a ) to the nearest power of 2 .
say b = 3000 , a = 1700 diff = 1300 = 1024 (10 bits ) + 256 (8 bits ) + 16 + 4 .
now generate random numbers within 1024 , 256 , 16 , 4 . ( say w,x,y,z) .
so the random number is a + ( w + x + y + z ) .
modified an answer a lot:
a+(b-a)-(random()*(rand()%(b-a+1))
where rand() is built in function and random is user defined
test case:
a=100
b=250
answer:100+150-0 =250 if random is zero
if random is 1 ans is 100+150 -(1*120)=130
120 generated by built in rand
min will be 100 and max will be 250
We can do it by bit logic (E,g, a=4 b=10)
- loveCoding January 31, 20121. Calculate difference b-a (for given e.g. 6)
2. Now calculate ceil(log(b-a+1)(Base 2)) i.e. no of bits required to represent all numbers b/w a and b
3. now call random(0,1) for each bit. (for given example range will be b/w 000 - 111)
4. do step 3 till the number(say num) is less than or equal to 110 i.e. we need only 7 levels since b-a is 6.
5. return num+a.