Digital Ocean Interview Question
IC3sTeam: Compute
Country: United States
Interview Type: Phone Interview
select the first with P(first) = 1 and keep that as selected number
if the 2nd arrives select that with P(2nd) = 0.5, run the experiment (e.g. if(random(2) == 0)) and take that as selected number accordingly, otherwise keep the other
if the 3rd arrives, select that with P(3rd) = 0.333, e.g. if(random(3)==0) ...
etc...
you need to prove uniformity, given your random(int max) is uniform:
P(selected = first) = 1/1 - (1/2 + 1/3 + ... + 1/n) = 1/n
P(selected = 2nd) = 1/2 - (1/3 + 1/4 + ... + 1/n) = 1/n
P(selected = k) = 1/k - (1/(k+1) + 1/(k+2) + ... + 1/n) = 1/n
void selectFromStream(intstream s) {
size_t read_so_far = 0;
int selected = numeric_limits<int>::min(); // suppose min never occures in the stream
while(!s.is_eof()) {
read_so_far++;
if(random(read_so_far) == 0) { // suppose random is uniform, returns [0, max)
selected = s.get_current();
}
s.next();
}
return selected;
}
This seems like a "Reservoir sampling" problem. Select K sample from a stream of samples.
+ Fill a buffer of size K with first K samples from stream.
+ Continue processing stream, and create a random number from 0 to current index for stream.
+ If number is in range [0,K] then overwrite current sample at this random index with current item from stream.
- mr.robot.fun.society November 07, 2017