Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Pick a Random Weighted Element (Main Thread)

Here is the interview question prompt, presented for reference.

You are given an array of positive integers w where w[i] describes the weight of the ith index.

Implement the function randomPick(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an element is w[i] / sum(w), where i is the index of the element.

![image](https://storage.googleapis.com/algodailyrandomassets/curriculum/medium-arrays/pick-random-weighted-element/problem.png)

The function randomPick() will be called n times (where n is an integer), with all the results stored in an array and then evaluated. This is to ensure that the function works correctly as the output may be different for different runs due to the randomness factor.

For example, if w = [1, 3], then the total weight of the array is 4. The probability of picking index 0 is 1/4 = 0.25 (25%), and the probability of picking index 1 is 3/4 = 0.75 (75%).

Constraints

  • 1 <= w.length <= 104
  • 1 <= w[i] <= 105
  • randomPick() will be called at most 104 times.

You can see the full challenge with visuals at this link.

Challenges • Asked almost 2 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Dec 16, 2022:

This is the main discussion thread generated for Pick a Random Weighted Element (Main Thread).