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