Multiset with O(1) Push and Random Pop

Reported in interviews at D. E. Shaw Tower Research Capital

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 of x. Produces no output.
  • ['remove', x]: remove ONE occurrence of x (guaranteed present). Append the integer count of x remaining 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.

Related free problems