Maintain a Stream Median
Company: Ixl
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Design a data structure for a stream of integers. It must support the following operations efficiently:
- `add_num(x)`: insert an integer `x` into the stream.
- `get_median()`: return the median of all numbers seen so far.
The median is defined as:
- the middle value when the count of numbers is odd,
- the average of the two middle values when the count is even.
Implement this data structure so that it can handle many insertions and median queries efficiently.
Quick Answer: This question evaluates the ability to design and implement efficient online data structures and algorithms for maintaining dynamic order statistics and computing the median of a stream of integers.