Medium
Quiz
#528 Random Pick with Weight
APPROACH
You are given a 0-indexed array of positive integers w where w[i] is the weight of index i. Implement pickIndex(), which returns a random index from [0, w.length - 1] where each index i is selected with probability proportional to w[i] / sum(w).
- Example: with w = [1, 3], index 0 is picked with probability 0.25 and index 1 with probability 0.75.
Example 1:
Input
["Solution","pickIndex"]
[[[1]],[]]
Output
[null,0]
Example 2:
Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.
Example 3:
Input
["Solution","pickIndex","pickIndex","pickIndex","pickIndex","pickIndex"]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]
Example 4:
Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.
Example 5:
Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
......
and so on.
1 of 4
1:00
What is the optimal approach for this problem?