Weighted Random Key Selection
Roblox● MediumNEW GRADONSITE INTERVIEWProblem statement
You are given parallel arrays keys and weights. Every key is distinct and its positive integer weight determines its probability of selection.
For this exercise, assume a random draw is supplied as a zero-based integer ticket from 0 through sum(weights) - 1. Assign consecutive ticket ranges to keys in input order, giving each key a range whose length equals its weight. A uniform ticket therefore selects a key with probability proportional to its weight.
You are also given tickets, a finite batch of independent draws. Return the selected key for each ticket in the same order. Each draw uses the original weights, so the same key may be selected repeatedly.
Function
selectWeightedKeys(keys: String[], weights: int[], tickets: int[]) → String[]Examples
Example 1
keys = ["cat","dog","human","baby"]weights = [5,2,2,1]tickets = [0,4,5,6,7,8,9]return = ["cat","cat","dog","dog","human","human","baby"]The source weights give ten tickets: cat owns 0..4, dog owns 5..6, human owns 7..8, and baby owns 9.
Example 2
keys = ["red","blue"]weights = [1,3]tickets = [3,0,1,1]return = ["blue","red","blue","blue"]The last three tickets belong to blue. Repeating ticket 1 repeats the selected key.
Example 3
keys = ["solo"]weights = [7]tickets = []return = []An empty batch contains no draws and returns an empty result.
Constraints
1 <= keys.length = weights.length <= 20000.- Keys are distinct strings containing
1to20characters. Each character is an English letter, a digit, an underscore, a hyphen, or a period. - The total number of characters across all keys is at most
100000. 1 <= weights[i]andsum(weights) <= 2 * 10^9.0 <= tickets.length <= 500.0 <= tickets[i] < sum(weights).