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.
The function
randomPick()
will be calledn
times (wheren
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%).
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
This is the main discussion thread generated for Pick a Random Weighted Element (Main Thread).