Random Pick With Weight

I had this on a Lyft simulation team interview, framed as "weighted A/B variant selection." The brute force is O(W) per pick where W is the sum of weights, way too slow when pickIndex is called 10^4 times against a 10^4-length array. The standard answer builds a prefix-sum array once in the constructor and then binary-searches a uniform random target into it; that gets you O(log n) per pick.

Random Pick With Weight

You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i-th index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

• For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25, and the probability of picking index 1 is 3 / (1 + 3) = 0.75.

Examples

Example 1:

Solution s = new Solution([1]);
s.pickIndex();   // always returns 0 (only index)

Example 2:

Solution s = new Solution([1, 3]);
repeated calls   // ~25% return 0, ~75% return 1

Constraints

• 1 <= w.length <= 10^4.
• 1 <= w[i] <= 10^5.
• pickIndex will be called at most 10^4 times.

Follow-up

Why a prefix-sum + binary search instead of expanding w into a flat list? Because sum(w) can be up to 10^9, but the array length is 10^4. The prefix-sum trick is O(n) build, O(log n) per pick, vs the flat list which is O(W) build and would not even fit in memory at the upper bound.