Reservoir Sampling K Seeded

Problem

Return a uniform random sample of k elements from nums using reservoir sampling with a deterministic seeded generator.

Fill the reservoir with the first k elements, then for each later element choose an index from 0 through i and replace that slot when it is below k. When k is at least the length, return all elements in their original order.

Hint

Each new element enters the reservoir with probability k divided by its index plus one.

Test cases

case 1

in: [[1,2,3,4,5],2,42]

expected: [4,2]

case 2

in: [[1],1,0]

expected: [1]

case 3

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

expected: [7,1,9]

case 4

in: [[],3,1]

expected: []

case 5

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

expected: [1,2,3]

Starter codePython

def reservoir_sample_k(nums, k, seed):
    # Your code here
    pass

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