Streaming median with add and remove, two heaps
Asked at HRT, Optiver
Design a structure over a live stream of numbers supporting:
add(x), insert a value.remove(x), delete one occurrence of a value already present.median(), the current median (mean of the middle two if the count is even).
s.add(1); s.add(2); s.add(3)
s.median() -> 2
s.remove(1)
s.median() -> 2.5 # {2, 3}
Every operation should be amortized.
Show a hint
Split the values into a lower half and an upper half. If the largest of the lower half and the smallest of the upper half are both instantly available, the median is one or the other. Two heaps give you exactly those two tops. The catch is remove: you cannot delete from the middle of a heap.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.