Feed ranking needs to sample a candidate in proportion to its weight. Build WeightedPicker(weights) (positive whole numbers) with a method pick(r), where r is a random number with 0 <= r < 1, passed in so the result can be checked. Lay the weights end to end over the range [0, 1): index 0 owns the first weights[0] / total of it, index 1 the next weights[1] / total, and so on. pick(r) returns the index that owns r; a value exactly on a boundary belongs to the next index. pick is called many times, so it should be quicker than scanning every weight.
Example
picker = WeightedPicker([1, 3])picker.pick(0.1) # 0picker.pick(0.25) # 1picker.pick(0.99) # 1
What this question tests
Modelled on the weighted random pick question reported from Meta loops: sample an index in proportion to its weight. It combines a probability idea (lay the weights end to end on [0, 1)) with an algorithm idea (find your spot by binary search), and the boundary rule is where answers split.
More Python interview questions