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 pickIndex(), 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 pickIndex() 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.