Dynamic Order Statistics (Online Percentile)
Problem statement
Design a data structure that maintains a dynamic multiset of numbers and supports the following three operations, each in $O(\log n)$ time and $O(n)$ total space:
- Insert(x) -- add the value $x$ to the multiset.
- Erase(x) -- remove one occurrence of $x$ from the multiset (guaranteed to exist).
- Kth(k) -- return the $k$-th smallest element in the current multiset ($1$-indexed).
Constraints:
- $1 \le n \le 10^6$ total operations
- Values $x$ can be arbitrary real numbers (not necessarily integers)
- All three operations must run in $O(\log n)$ worst-case or amortized time
- Total space usage must be $O(n)$
Example 1:
Insert(5), Insert(3), Insert(8), Insert(3)
Kth(1) -> 3
Kth(3) -> 5
Erase(3)
Kth(2) -> 5
Example 2:
Insert(10), Insert(20), Insert(10), Insert(30)
Kth(4) -> 30
Erase(10)
Kth(1) -> 10
Kth(3) -> 30
Describe your data structure, explain how each operation works, provide a working implementation, and discuss how you would handle numerical robustness for real-valued (floating-point) inputs.
---
Function signature: implement run_ops(ops), where ops is a list of operations on a dynamic multiset. Each op is a list: ['insert', x] adds x; ['erase', x] removes one occurrence of x (guaranteed to exist); ['kth', k] records the k-th smallest current element (1-indexed). Return the list of results, one per kth op, in order.
Example
run_ops([['insert',5],['insert',3],['insert',8],['insert',3],['kth',1],['kth',3],['erase',3],['kth',2]]) -> [3, 5, 5]
After the four inserts the multiset is {3, 3, 5, 8}: the 1st smallest is 3 and the 3rd smallest is 5. Erasing one 3 leaves {3, 5, 8}, whose 2nd smallest is 5, so only the three kth ops produce output.
Show hint
What could you augment a search structure with so that a rank question can be answered by walking down it instead of listing everything?
Relevant roles: ML Engineer, Data Scientist, MLOps Engineer and Applied Scientist.