Solution: Random Pick with Weight
Explore how to perform weighted random selection from an array using running sums and modified binary search. Understand the construction of running sums, generation of a random target, and applying binary search to select indices proportionally to their weights. This lesson teaches an efficient way to implement Pick Index() that optimizes time complexity using these concepts.
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: ...