Multiset with O(1) Push and Random Pop
Problem statement
Design a data structure that stores a multiset of elements and supports two operations:
push(x): Insert element $x$ into the multiset.popRandom(): Remove and return an element chosen uniformly at random from the current multiset.
Both operations should run in expected $O(1)$ time, and the data structure should use $O(n)$ space where $n$ is the number of stored elements. Your solution must handle duplicate elements correctly.
Constraints:
- Elements can be any hashable type.
- The multiset can contain duplicates (e.g., pushing $x$ three times means $x$ appears three times and has triple the probability of being popped).
popRandom()on an empty structure is undefined.
Extension: Now suppose each stored element has an associated weight $w_x > 0$. Duplicates may have distinct weights. Add an operation:
popWeighted(): Remove and return an element with probability proportional to its weight.updateWeight(x, w'): Change the weight of a stored element $x$ to $w'$.
What time complexity can you achieve for push, popWeighted, and updateWeight? Justify any lower bounds you rely on.
Function signature
Implement run_ops(ops), where ops is a list of operations. Each op is a list:
['push', x]: insert one copy ofx. Produces no output.['remove', x]: remove ONE occurrence ofx(guaranteed present). Append the integer count ofxremaining AFTER the removal.
After replaying all ops, append one final element: the sorted list of every element currently in the multiset (with multiplicity). Return that result list.
Use the swap-to-end + index-bookkeeping trick so both push and remove run in O(1).
Example
run_ops([['push',5],['push',5],['push',7],['remove',5]]) -> [1, [5, 7]]
The single remove of 5 leaves one 5 behind, so it appends 1; the final element is the sorted multiset [5, 7].
Show hint
Which container gives constant-time uniform access by position, and what makes deleting from its middle expensive?
Relevant roles: ML Engineer, MLOps Engineer, Forward Deployed Engineer and AI Engineer.