Solution: Random Pick with Weight
Explore how to solve the weighted random pick problem by transforming weights into running sums. Understand how to generate a random target and efficiently locate its index using binary search, optimizing both time and space complexity in Go.
Statement
You’re given an array of positive integers, weights, where weights[i] is the weight of the index.
Write a function, Pick Index(), which performs weighted random selection to return an index from the weights array. The larger the value of weights[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: ...