Random Pick with Weight
Medium · Prefix Sums · Array · Math · Binary Search · Prefix Sum · Randomized
Problem
You are given positive integer weights w. Build a picker whose pickIndex() returns a random index i with probability w[i] / sum(w). With w = [1, 3], index 1 should come back three times as often as index 0.
- Solution(w) builds the picker.
- pickIndex() returns one random index.
Tests replay a call sequence: the first entry constructs Solution with w, and each later entry is a pickIndex call. The picks are random, so a test has no single right output. Its expected value shows the weights and the number of picks. The grader checks that every pick is a valid index. Over long runs it also counts how often each index came up. Each count must be within 7 standard deviations of picks * w[i] / sum(w), and an index expected to come up at least 25 times must come up at least once. A correct picker fails these checks with probability below one in a billion.
Examples
Input: w = [1,3], then pickIndex() five times Output: for example 1, 1, 1, 1, 0
Each pick is 1 with probability 3/4 and 0 with probability 1/4. Other runs, such as 1, 0, 1, 1, 1, are just as correct.
Input: w = [1], then pickIndex() Output: 0
There is only one index, so every pick returns it.
Constraints
- 1 <= len(w) <= 10^4
- 1 <= w[i] <= 10^5
- pickIndex is called at most 10^4 times per test
Approaches
- Walk the weights on every pick — time O(n) per pick, space O(1) extra
Related problems
Start free on Cariara · Coding problems · System design studio
