Design a data structure to find streaming median
Quick Overview
This question evaluates proficiency in data structure and streaming algorithm design for maintaining the median of a dynamic integer stream, testing competency in algorithmic thinking and analysis of time- and space-complexity within the Coding & Algorithms domain; the level of abstraction is practical application with implementation and performance considerations. It is commonly asked to assess the ability to design efficient, scalable online aggregation methods for large or repetitive inputs and to reason about memory and run-time trade-offs, with the follow-up focusing on optimizing for extremely large streams with many duplicates.
Problem
Design a data structure that supports maintaining the median of a stream of integers.
Implement a class/ADT with the following operations:
-
addNum(x): Add an integerxto the data structure. -
findMedian(): Return the median of all numbers added so far.
Median definition
-
If the count
nis odd, the median is the middle element after sorting. -
If
nis even, the median is the average of the two middle elements (return a floating-point number if needed).
Constraints / expectations
- The stream can be very large.
- Values may include negatives and duplicates.
- Aim for efficient per-operation time (better than sorting on every query).
Follow-up
If the input stream is extremely large and contains many repeated values, how would you optimize the design (time and/or memory)?