You’re given an array of positive integers, w, where w[i] is the weight of the $i^{th}$ index.

Implement the function pickIndex(), which performs weighted random selection to return an index from the w array. The larger the value of w[i], the heavier the weight is, and the higher the chances of its index being picked.

Suppose that the array consists of the weights $[12, 84, 35]$. In this case, the probabilities of picking the indexes will be as follows:

• Index 0: $12/(12 + 84 + 35) = 9.2\%$

• Index 1: $84/(12 + 84 + 35) = 64.1\%$

• Index 2: $35/(12 + 84 + 35) = 26.7\%$

Constraints:

• $1 \leq$ w.length $\leq 10^4$

• $1 \leq$ w[i] $\leq 10^5$

• pickIndex() will be called at most $10^4$ times.

Note: Since we’re randomly choosing from the options, there is no guarantee that in any specific run of the program, any of the elements will be selected with the exact expected frequency.

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.