## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
3
of 3 vote

The Random.next() function is implemented using a linear congruential pseudo random number generator. This is a simple algorithm where you take the seed value and generate random numbers using the following formula:

X(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()  implements it using the Marsaglia's polar method. 

Refer to Java doc for  and .
Refer to wikipedia for  and 

Comment hidden because of low score. Click to expand.
0

Hmmm, you appear to be right. I'm really surprised that Java would use something like a LCG...I thought they used Mersenne Twister.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0
of 8 vote

int randomNumber(int no)
{
return System.getCurrentTimeInMillis()%no;
}

Comment hidden because of low score. Click to expand.
0

what if no is very large, in that case it will become obvious to the caller that the randomNumber() is returning incremental values.

Comment hidden because of low score. Click to expand.
0

agree with Anonymous. It is not random.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

check en.wikipedia.org/wiki/Mersenne_twister

Comment hidden because of low score. Click to expand.
0
of 0 vote

check Mersenne twister on wikipedia

Comment hidden because of low score. Click to expand.
0
of 0 vote

search Mersenne twister

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

What if the value of the address itself is used?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

This comment has been deleted.

Comment hidden because of low score. Click to expand.
0

I'm a bit horrified to see the addresses returned by malloc used for random number generation.

Comment hidden because of low score. Click to expand.
-2
of 4 vote

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.

Comment hidden because of low score. Click to expand.
0

can you explain with an example

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Hi,
How do you generate a random integer between 0-4?

Comment hidden because of low score. Click to expand.
0

-1 for just not reading question at all. I says - GENERATE random number, and you're trying to mess here with (wrongly implemented) reservoir sampling.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.