Solution: Random Pick with Weight
Discover how to perform weighted random selection from an array using running sums combined with modified binary search. This lesson guides you through creating a probability line from weights, generating random targets, and using binary search to efficiently pick an index. Understand both naive and optimized solutions, and evaluate their time and space complexities for coding interviews.
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: ...