Weighted Random Number Generator

MediumPython

Problem

Supermicro Computer evaluates several server configurations with different selection weights. Implement weighted sampling so that a configuration with weight w is selected with probability w / sum(weights).

To make the function deterministic and testable, the caller provides uniform random values instead of requiring the function to access a random-number library. For each random value, return the selected configuration index.

Formal Specification

Implement weighted_random(weights, random_values):

weights is a list of positive integers, where weights[i] is the relative probability of selecting configuration i.
random_values is a list of floating-point values, each in the interval [0, 1).
Return a list of indices, one for each random value.
A random value u corresponds to the target u * sum(weights) on the cumulative weight scale.
Use half-open intervals, so a target exactly equal to a cumulative boundary belongs to the interval beginning at that boundary.

Build the cumulative distribution once, then use binary search for every sample.

Constraints

1 <= len(weights) <= 10^5
1 <= weights[i] <= 10^9
1 <= len(random_values) <= 10^5
Every random value satisfies 0 <= random_values[i] < 1

Function Signature

def weighted_random(weights, random_values):

Formal Specification

Implement weighted_random(weights, random_values):

weights is a list of positive integers, where weights[i] is the relative probability of selecting configuration i.
random_values is a list of floating-point values, each in the interval [0, 1).
Return a list of indices, one for each random value.
A random value u corresponds to the target u * sum(weights) on the cumulative weight scale.
Use half-open intervals, so a target exactly equal to a cumulative boundary belongs to the interval beginning at that boundary.

Build the cumulative distribution once, then use binary search for every sample.