$ ./guess_the_languageProblem Solving — fill the blank
Problem Solving — fill the blank · hard · #332

What goes in the blank?

import random
# reservoir sampling: keep k items from a stream
for i, x in enumerate(stream):
    if i < k:
        res.append(x)
    else:
        j = random.randint(0, i)
        if j < ____:
            res[j] = x

Answer: k (also accepted: k)

Item i is kept with probability k / (i + 1), replacing a random slot, which leaves every item seen so far equally likely to be in the sample.
Play Problem Solving ▸