Random Pick with Weight

Problem Given an array w of positive weights, implement pickIndex() that returns index i with probability proportional to w[i].

Input / Output

• Input: constructor takes w; pickIndex() takes no arguments.
• Output: an index in [0, w.length), returned with probability w[i] / sum(w).

Constraints

• 1 <= w.length <= 10^4; pickIndex may be called many times, so precompute in the constructor.

Example

• w = [1,3] → index 0 about 25% of the time, index 1 about 75%.