Random Pick with Weight
On this page
Problem statement
You are given an array of positive integer weights
w. ImplementpickIndex(), which returns a random indexiwith probabilityw[i] / sum(w).pickIndexwill be called many times, so it must be fast after a one-time setup.
This looks like a probability question, but it is really prefix sums plus binary search, with a boundary that has to be exactly right. In practice it's weighted load balancing, A/B traffic splits and ad selection. Original problem: LeetCode 528.
Example

Solution([2, 5, 3])
pickIndex() -> 1 # probability 5/10
pickIndex() -> 2 # probability 3/10
pickIndex() -> 1
pickIndex() -> 0 # probability 2/10
# any sequence is valid; over many calls the counts approach 20% / 50% / 30%
Solution([4])
pickIndex() -> 0 # always
Constraints (assumed)
- 1 ≤ n ≤ 10⁴; 1 ≤ w[i] ≤ 10⁵, so the total fits in 32 bits (just under 10⁹).
- Up to 10⁴ calls to
pickIndex.
What this question tests
- Turning weights into ranges on a number line (prefix sums).
- Binary search for the range that contains a random point, with the correct strict or non-strict comparison.
- Thinking about follow-ups: changing weights, O(1) picks, and how to test randomness.
Questions to ask first
- Are all weights positive? A zero weight should never be picked; a negative one makes no sense. (Here: positive.)
- Will the weights change between picks? That changes the data structure. (Here: no; it's a follow-up.)
- Can I use the language's random number generator, and is it uniform? (Here: yes.)
- How many picks compared with the array size? Decides whether O(log n) per pick is enough.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.