Here is the interview question prompt, presented for reference.
You are given an array of positive integers
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.
randomPick()will be called
nis 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
1/4 = 0.25 (25%), and the probability of picking index
3/4 = 0.75 (75%).
randomPick()will be called at most 104 times.
You can see the full challenge with visuals at this link.
Challenges • Asked 3 months ago by Jake from AlgoDaily
This is the main discussion thread generated for Pick a Random Weighted Element (Main Thread).