Random Index Picker Based on Weights

Problem Statement

You are given an array weights of positive integers where each weights[i] represents the weight of index i. Implement a function chooseIndex that randomly selects an index from the array such that the probability of picking each index is proportional to its weight.

Constraints

• 1 ≤ weights.length ≤ 8000
• 1 ≤ weights[i] ≤ 5 × 104
• chooseIndex may be invoked up to 8000 times.

Examples

Example 1:
Input:
["Picker","chooseIndex"]
[[[2]],[]]
Output:
[null,0]

Example 2:
Input:
["Picker","chooseIndex","chooseIndex","chooseIndex","chooseIndex","chooseIndex"]
[[[2,5]],[],[],[],[],[]]
Output:
[null,1,1,0,1,1]