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()[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:

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() [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]

- Ram August 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi August 31, 2012 | Flag
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

- yemrus_ankara August 07, 2012 | Flag Reply
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...

- FBNerd February 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 8 vote

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

- Anonymous August 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

agree with Anonymous. It is not random.

- jiangok2006 August 15, 2012 | Flag
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;
}
}

- Abhijeet Rokade August 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

check en.wikipedia.org/wiki/Mersenne_twister

- jiangok2006 August 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

check Mersenne twister on wikipedia

- jiangok2006 August 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

search Mersenne twister

- jiangok2006 August 15, 2012 | Flag Reply
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;
}

- Anand August 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if the value of the address itself is used?

- dc360 August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

This comment has been deleted.

- Administrator August 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi August 31, 2012 | Flag
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.

- mr August 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain with an example

- devendar August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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
+

- mr August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Summer August 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gevorgk August 08, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More