DIY: Random Pick with Weight

Solve the interview question "Random Pick with Weight" in this lesson.

Problem statement

You are given an array of positive integers, w, where w[i] describes the weight of the ithi{th} index.

We need to call the function pick_index(), which randomly returns an index from the weights array. The heavier the weight is, the higher the chances of getting that index randomly.

Suppose the weights array contains the values [10, 90]. In this case, index 0 will be returned with probability 10 / (10 + 90) = 10%. Similarly, index 1 will be returned with 90% probability.

Input

The input will be a list of integers. The following is an example input:

w = [1, 2, 3]

Output

The output will be an integer value representing the index with the highest probability. The following is an example output for the above input:

2

Index 2 has the highest weight, so its probability of occurrence is higher.

Note: As we are randomly choosing the highest probable option, there is no guarantee that the element with the highest weight will always be selected.

Coding exercise

Implement the pick_index() function, where the integer’s weight array is passed to the constructor. The function will return a single integer value representing the index with the highest probability.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.