Search⌘ K
AI Features

Solution: Random Pick with Weight

Solution: Random Pick with Weight provides positive weights for an array and asks you to return an index at random, with each index selected in proportion to its weight.

Statement

You’re given an array of positive integers, w, where w[i] is the weight of the ithi^{th} index.

Implement the function PickIndex(), which performs weighted random selection to return an index from the w array. The larger the value of w[i], the heavier the weight is, and the higher the chances of its index being picked.

Suppose that the array consists of the weights [12,84,35][12, 84, 35]. In this case, the probabilities of picking the indexes will be as follows:

  • Index 0: 12/(12+84+35)=9.2%12/(12 + 84 + 35) = 9.2\%

  • Index 1: 84/(12+84 ...