Random Pick with Weight

Explore how to perform weighted random selection in an array by implementing a function that picks indices based on their weight proportions. Understand the problem constraints and use techniques involving prefix sums and modified binary search to efficiently choose indices. This lesson helps you develop a method to handle weighted probabilities and apply randomized algorithms in an interview scenario.

We'll cover the following...

Statement
Examples
Understanding the problem
Figure it out!
Try it yourself

Statement

You’re given an array of positive integers, weights, where weights[i] is the weight of the $i^{th}$ 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 $[12, 84, 35]$ . In this case, the probabilities of picking the indexes will be as follows:

Index 0: $12 / (12 + 84 + 35$ ...