Reservoir Sampling Update Probability

Problem

Return the probability that the item at 1-based position index ends up in the final reservoir of size k.

The first k items always enter the reservoir, and each later item i is kept with probability k / i and survives all subsequent replacements with the same probability. Return 0.0 when index or k is non-positive and 1.0 when index is at most k.

Hint

Item i is included with probability 1 for i <= k and k / i afterwards.

Test cases

case 1

in: [10,3]

expected: 0.3

case 2

in: [7,1]

expected: 0.14285714285714285

case 3

in: [3,5]

expected: 1

case 4

in: [0,3]

expected: 0

case 5

in: [100,25]

expected: 0.25

Starter codePython

def reservoir_update_probability(index, k):
    # Your code here
    pass

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