Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
I suppose what facebook guys wanted to hear is to design a (almost)nondeterministic source of randomness that makes the best generic use of what the machine or the OS would provide indirectly.
#OS scheduling provides us with such a mechanism:
Pseudo code:
Function randomBinary returns boolean
yield OS scheduler;
Get system processor cycles count or maybe RTC based nano level counter
Check if the counter is even or odd;
If odd
Return 1;
Else
Return 0;
Function Rand(int n ) returns integer
Declare new random number R = 0;
While (R < n)
Call randomBinary and modify the LSB of R
Shift R by 1
Return residual and random part of R
I think this will pass most of the statistics test.
# other solution would be linear congruent approach
I doubt that. Simply because gathering some magic OS values won't solve the problem that you need to be able to generate millions of random values per second. It is really about how to create a pseudo-random generator... Usually you only "desync" a cryptographic one every now and then with new entropy, it is just too costly.
Also, gathering random data is no guarantee for uniform distribution! You need to work a bit more...
what if no is very large, in that case it will become obvious to the caller that the randomNumber() is returning incremental values.
int Rand_Num_Equal_Pro(const int n){
static int Flag[n];
int r, temp;
time_t t;
struct tm *t;
t= localtime(&t);
r= t->tm_sec+ t->tm_min*10+ t->tm_hour*100;
srand(r);
r= rand();
r= r%n;
temp= r+1;
if(Flag[r]){
while(Flag[temp]&& (temp%n)!= r) temp++;
if((temp%n)== r){
for(int i= 0; i<n; i++)
Flag[i]= 0;
return r;
}
else{
Flag[temp%n]= 1;
return temp%n;
}
}
else{
Flag[r]= 1;
return r;
}
}
1) Create a dyanamic memory of type char ie, size will be 1.
2) Store the value of the memory to a integer variable.
3) Take the mod of the interger variable for n
we will get a random function in the range 0-n1
int rand(int num){
char * a=(char *)malloc(sizeof(1));
int b= a;
b=b%num;
return b;
}
the problem seems similar to shuffling a deck of cards.
now what you would do is, generate a random number between 0 - n-1 and choose that index to mark the entry/value (i.e. arr[random_i] as dead by swapping it with the start index which also keeps moving with each new number being generated).
i.e. swap (arr[startIndex], arr[random_i]).
and you generate number between startIndex and n-1 and keep doing this n times. Then the array contains the numbers generated with equal probability.
Let me try to give it a shot with an example.
Suppose this is the array (0 - n-1)
Array Index: 0 1 2 3 4
Array Value: 0 1 2 3 4
generate random number between 0 - 4
say we get random_i = 3
startIndex = 0
swap (arr[startIndex] , arr[random_i])
startIndex++
startIndex = 1 now
Array looks like below.
startIndex
+ |
0 + 1 2 3 4
3 + 1 2 0 4
+
generate between startIndex = 1 to 4
say we generate 2 now then swap
arr[2] and arr[startIndex =1 ]
startIndex++
startIndex = 2 now and keep doing this so that each number has equal probability of being selected.
startIndex
+ |
0 1+ 2 3 4
3 2+ 1 0 4
+
The Random.next()[1] function is implemented using a linear congruential pseudo random number generator[2]. This is a simple algorithm where you take the seed value and generate random numbers using the following formula:
- Ram August 21, 2012X(0) = seed >> 2^48.
X(n+1) = (25214903917* X(n) + 11) (mod 2^48)
This gives us a random number generator with a uniform distribution between 0 and 1. If you need a guassian distribution, Random.nextGuassian() [3] implements it using the Marsaglia's polar method. [4]
Refer to Java doc for [1] and [3].
Refer to wikipedia for [2] and [4]