## Facebook Interview Question for Software Engineer / Developers

• 1
of 1 vote

Country: United States
Interview Type: In-Person

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

``````public static int getRan(Node m)
{
int range=1;
Random random=new Random();
int ret=(Integer)m.getValue();
while(m.next!=null)
{
m=m.next;
range++;
if(random.nextInt(range)==0)
{
ret=(Integer)m.getValue();
}
}
return ret;
}``````

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

Yeah, it's right.
Suppose there are a stream of bytes "abc",
when you read "a", ret = "a" with probility = 1,
when you read "b", ret = "b" with probility = 1/2, so the probility of ret = "a" is 1/2 now,
when you read "c", ret = "c" with probility = 1/3, so the probility of ret = "b" is (1 - 1/3) * 1/2 = 1/3, and the probility of ret = "a" is (1 - 1/3 - 1/3) * 1 = 1/3.
and so on.

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

Yep, this is correct.

The question says you only have one byte of storage space, so if you followed that strictly, you wouldn't be able to keep a variable like "range". Since it's impossible to solve the problem without having a counter like that, however, it's perfectly appropriate to ignore that requirement.

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

reservoir sampling

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

I feel it is wrong. If we repeat running the algorim twards the same stream, statistitcally we should see "a" in 50% of the attempts.

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

Nice solution!

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

That's also what I thought, just it said "only storage for one byte" ;). But we need a counter...

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

It cannot have probability of 'a' selection as fancysimon said 1 because nextInt(2) would return 0 or 1 which means probability of 'a' is 1/2. Also, if we move the increment range++; after the check then we will always select the first byte which also wrong.
On the other hand, if we have only one byte "a" it should return that byte for sure. So, I think this solution is doing some assumptions.

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

Reservoir Sampling.

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

You need to be able to store how many elements you've seen so far (which presumably can't fit into a byte) for this problem to be possible.

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

Yes.

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

Lol

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

I think, firstly, you should know how many bytes of this stream.
For example, if there are 5 bytes in this stream.
Then, for the first byte:
You can use:
if ( (int)(Math.Random()*5)==0 ){
Store this byte;
return this byte;
}
for the second byte:
if ( (int) (Math.Random()*4) ==0 ){
Store this byte;
return this byte;
}
.........
for the kth byte of n byte:
if ( (int) (Math.Random()*(n-k+1)) ==0 ){
Store this byte;
return this byte;
}
.....
every byte have the same probability

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

It's a stream, so you don't know that.

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

It does say after processing those bytes which means you can count the number of bytes.

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

tag

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.

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

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