Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
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.
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.
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.
That's also what I thought, just it said "only storage for one byte" ;). But we need a counter...
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.
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.
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
- Vincent August 05, 2012public 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; }