mediumCodingDesignMidSeniorStaff
Numbers arrive one at a time and after each one I want the running median. How would you keep it?
5 min readUpdated 2026-08-15Target archetype: Big Tech, Enterprise Captive, Product Startup
Answer
Short answer
Split the values across a max-heap of the lower half and a min-heap of the upper half, so the median is read off one or both tops. Balancing by size alone is what breaks it: a new value has to enter through the heap it belongs to by value and be transferred across, never pushed into whichever heap is currently smaller.
Was this answer helpful?
Likely follow-ups
- Now give me the median of the last k values only. What breaks, and what do you replace the heaps with?
- I want the 95th percentile rather than the median. Do two heaps still work?
- Values can be removed as well as added, by value not by position. What now?
- Memory is bounded and the stream is unbounded. What accuracy would you trade away, and for what?
Related questions
- You are handed k sorted lists and asked for one sorted list. What is wrong with concatenating and sorting?mediumAlso on heaps and priority-queue6 min
- Numbers arrive one at a time and after each one you must answer what the Kth largest so far is. What do you keep, and what do you deliberately throw away?mediumAlso on heaps and priority-queue6 min
- Return the k most frequent elements from a large stream of values. Why not just sort by frequency?mediumAlso on heaps and priority-queue4 min
- You may use an AI coding assistant in the machine-coding round. What do you still write yourself, and what do you ask it for?mediumAlso on invariants5 min