Learn and practice the Two Pointers, Fast and Slow Pointers, and Modified Binary Search patterns to solve coding interview problems.

Educative-99 in Python: Accelerate Your Coding Interview Prep

This module groups together three of the most common patterns that may be used to solve problems where the input data is linear: Two Pointers, Fast and Slow Pointers, and Modified Binary Search. Both the Two Pointers and the Modified Binary Search patterns derive their power from their ability to efficiently reduce the size of the search space, that is, both exemplify the divide-and-conquer approach to problem-solving. The Fast and Slow Pointers pattern may be considered a variant of the Two Pointers pattern, where the two pointers move at different speeds in order to traverse the input list in a way that solves the given problem. After completing this module, we will have learned how to use this set of related patterns to solve a diverse range of problems.

Two Pointers & Co.

# 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) = 9.2\%$ 

- **Index 1:** $84/(12 + 84 + 35) = 64.1\%$

- **Index 2:** $35/(12 + 84 + 35) = 26.7\%$  

**Constraints:**

* $1 \leq$ `weights.length` $\leq 10^4$

* $1 \leq$ `weights[i]` $\leq 10^5$

* **Pick Index()** will be called at most $10^4$ times.

> **Note:** Since we’re randomly choosing from the options, there is no guarantee that in any _specific_ run of the program, any of the elements will be selected with the exact expected frequency.

# Examples

Try to solve the Random Pick with Weight problem.