Random Removal from a Set
Bloomberg LP● MediumNEW GRADONSITE INTERVIEWProblem statement
Initialize a dense set with the distinct integers in values. For each value in choices, treat it as a zero-based random index into the set's current dense array. Append the selected value to the result, then remove it in O(1) time by moving the current last value into its slot.
Return the selected values in order.
Function
randomRemovalSequence(values: int[], choices: int[]) → int[]Examples
Example 1
values = [1,4,7,9]choices = [2,0]return = [7,1]Removing index 2 selects 7 and swaps 9 into its slot; removing index 0 then selects 1.
Constraints
- Values are distinct.
choices.length <= values.length.- Each choice is valid for the current size.