weighted Random pick

'''
You have to choose an index random where the probability of getting it chosen depends on the number for eg. [2,5,3] so probability of getting chosen 2 should be 2/10, 5 should be 5/10, and 3 should be 3/10.

How it is possible, One approach is make that array as: [0,0,1,1,1,1,1,2,2,2] and take a random guess from 1 to 10 and take that index number that is actually the index of the actual array and this will be weighted random pick but this is inefficient.

M-2:
you take the prefix sum so prefix_sum=[2,7,10] and now take a random guess from 1 to total sum ie. 10 and use the bisect_left so bisect left will look for the first position which can get populated by that random number so if you see;
-2 will get chosen for 1 and 2, 2 times out of 10 times
-7 will get chosen for 3,4,5,6,7, 5 times out of 10 times
-10 will get chosen for 8,9,10, 3 times out of 10 times
once an index is chosen, just return that index and that index is gonna be the weighted random index or the element of that index from the actual array as per the problem asked.
'''

import random
import bisect
class WeightedRandomPicker:
    def __init__(self, weights):
        self.prefix = []
        total = 0

        for w in weights:
            total += w
            self.prefix.append(total)

        self.total = total

    def pick(self):
        r = random.randint(1, self.total)
        idx = bisect.bisect_left(self.prefix, r)
        return idx

weights = [2, 5, 3]
picker = WeightedRandomPicker(weights)

print(picker.pick())  # returns index (0, 1, or 2)