Design a data structure that supports adding integers from a stream and finding the median of all elements added so far.
For example, after adding [2, 3, 4], the median is 3. After adding 5, the stream is [2, 3, 4, 5] and the median is 3.5.
Explain your approach and state the time complexity of each operation.
How to approach it
- Hint 1
Think about splitting the numbers into two halves: the smaller half and the larger half.
- Hint 2
Use two heaps: a max-heap for the lower half and a min-heap for the upper half. The median is at the tops of these heaps.
- Hint 3
Keep the heaps balanced in size (differ by at most 1). The median is either the top of the larger heap or the average of both tops.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.