Solution: Random Pick with Weight
Explore how to perform weighted random selection by using running sums and a modified binary search algorithm. Understand how to transform weights into cumulative sums, generate random targets, and efficiently locate the correct index. This lesson equips you with a method to improve selection time complexity from linear to logarithmic, ideal for coding interview problems.
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: ...