Median of a stream
How do you maintain the running median of a stream efficiently, and at what per-insert cost?
Show hints (2)+
- Split the data into a low half and a high half.
- The median lives at the boundary of the two halves.
Answer
Reveal answer →Final answer
Two balanced heaps (max-heap low half, min-heap high half) - per insert
Create a free account to see the full worked solution and track your progress.
Interview format: Hedge Fund Quant, Systematic & Data-Driven Trading