Random Pick with Weight
Explore how to implement a weighted random selection function that picks an index based on given weights. Understand the problem constraints, probability calculations, and practice coding this solution in Go, leveraging modified binary search for efficient selection.
We'll cover the following...
Statement
You’re given an array of positive integers, w, where w[i] is the weight of the 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 . In this case, the probabilities of picking the indexes will be as follows:
-
Index 0:
-
Index 1:
-
Index 2:
Constraints:
-
w.length -
w[i] -
PickIndex()will be called at most 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.
Examples
Understanding the problem
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:
Random Pick with Weight
Given this list of weights, which index has the highest probability of being picked? Note that indexes start at 0.
weights = [5, 6, 10, 8, 9, 7]
0
3
4
2
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground.
package maintype Solution struct {}func Constructor(w []int) Solution {return Solution{}}func (s *Solution) PickIndex() int {return -1}