Weighted Random Selection | Dataford Interview Questions

LinkedIn may need to sample content candidates according to configured exposure weights. Given positive weights and uniformly distributed random values, return the selected index for each random value.

Formal Specification

Implement weighted_random_pick(weights, random_values).

weights is a list of positive integers, where weights[i] is the relative probability of selecting index i.
random_values is a list of real numbers, each satisfying 0 <= value < sum(weights). Each value represents an independent uniform draw from the total weight range.
Return a list of indices. For each random value r, return the smallest index i whose cumulative weight is greater than r.

The interval [prefix[i - 1], prefix[i]) maps to index i, with prefix[-1] treated as 0.

Constraints

1 <= len(weights) <= 10^5
1 <= weights[i] <= 10^9
1 <= len(random_values) <= 10^5
0 <= random_values[j] < sum(weights)
All weights are positive integers

Function Signature

def weighted_random_pick(weights, random_values):

Your question is Weighted Random Selection. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem