Weighted Random Selection Seeded

Problem

Pick an index at random from a list of non-negative integer weights using a deterministic linear congruential generator seeded by the given seed.

The probability of index i is its weight divided by the total weight; walk the cumulative weights and return the first index whose cumulative total exceeds the drawn value. Return -1 when the total weight is 0.

Hint

The cumulative walk is the inverse of the weighted cumulative distribution.

Test cases

case 1

in: [[1],42]

expected: 0

case 2

in: [[1,0,0],7]

expected: 0

case 3

in: [[0,0,5],3]

expected: 2

case 4

in: [[1,1,1],0]

expected: 0

case 5

in: [[5,1],42]

expected: 0

Starter codePython

def weighted_random_seeded(weights, seed):
    # Your code here
    pass

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