Dynamic Weighted Sampling With Updates

Reported in interviews at Jane Street

Problem statement

You have an array of $n$ nonnegative weights $w_1, w_2, \ldots, w_n$. Design a data structure that supports the following two operations efficiently:

  1. Update($i$, $\delta$): Add $\delta$ to weight $w_i$ (the result must remain nonnegative).
  2. Sample(): Return an index $i$ with probability $w_i \,/\, W$, where $W = \sum_{j=1}^{n} w_j$ is the total weight.

Both operations should run in $O(\log n)$ time.

Constraints:

  • $1 \le n \le 10^6$
  • Weights are nonnegative real numbers.
  • $\delta$ can be positive or negative, but the resulting weight must stay $\ge 0$.
  • You may assume access to a uniform random number generator on $[0, 1)$.

Example 1:

Init: weights = [2, 3, 5]
Sample() -> returns 0 with prob 0.2, 1 with prob 0.3, 2 with prob 0.5
Update(0, 8)  // weights become [10, 3, 5]
Sample() -> returns 0 with prob 10/18, 1 with prob 3/18, 2 with prob 5/18

Example 2:

Init: weights = [1, 1, 1, 1]
Sample() -> returns each index with prob 0.25
Update(2, 3)  // weights become [1, 1, 4, 1]
Sample() -> returns 0,1,3 with prob 1/7 each, 2 with prob 4/7

Example

run_ops([2, 3, 5], [['sample', [0.0]], ['sample', [4.9]], ['sample', [9.9]]]) -> [0, 1, 2]

The cumulative ranges are index 0 = [0,2), index 1 = [2,5), index 2 = [5,10); targets 0.0, 4.9, 9.9 land in those ranges respectively, so the three sample ops return 0, 1, 2.

Show hint

If you lay all the weights end to end on a line, how does a single uniform draw pick an index?

Relevant roles: ML Engineer, Data Scientist, MLOps Engineer and Applied Scientist.

Related free problems