Random pick with weight and vertical order traversal of a binary tree
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.
1 ≤ weights.length ≤ 8000
1 ≤ weights[i] ≤ 5 × 104
chooseIndex
may be invoked up to 8000
times.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]