Reservoir in Stream

Problem

Sample k items uniformly from a stream using reservoir sampling.

Process the stream in order; the first k items fill the reservoir, and item i (0-based, i >= k) replaces a random slot with probability k/(i+1) using random.Random(seed). The result is deterministic for a given seed.

Return the reservoir list in slot order.

Hint

Draw randrange(i + 1) for item i and swap it in when the draw falls under k.

Test cases

case 1

in: [[1,2,3,4,5,6,7,8,9,10],3,42]

expected: [5,2,10]

case 2

in: [[1,2],5,0]

expected: [1,2]

case 3

in: [[],3,1]

expected: []

case 4

in: [[1,2,3,4],2,7]

expected: [1,4]

Starter codePython

def reservoir_sample(stream, k, seed):
    # Your code here
    pass

4 test cases · run your code against them in the editor