Random Pick with Weight
Explore the concept of weighted random selection where indices are chosen based on their assigned weights. Understand how to use modified binary search to efficiently implement the Pick Index function, ensuring the probability of selection reflects each weight. This lesson helps you develop a reliable approach to randomized picks with weighted probabilities for coding interviews.
We'll cover the following...
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: ...