Katkat
Back

Maintain a Stream Median

IXL LearningSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question tests the ability to maintain dynamic order statistics in a streaming context, requiring an efficient way to insert elements and compute the median in logarithmic time.

Problem Statement

Design a data structure that supports receiving a stream of integers one by one and allows for querying the current median of all integers seen so far.

If the number of elements is odd, the median is the middle element in the sorted list. If the number of elements is even, the median is the average of the two middle elements.

Implement the MedianFinder class with the following methods:

  • __init__: Initializes the data structure.
  • add_num(num: int): Adds an integer to the data structure.
  • find_median() -> float: Returns the median of all elements added so far.

Constraints

  • add_num and find_median must perform better than O(N) time complexity, where N is the number of elements added.
  • You may assume all integers are within the range [-10^6, 10^6].

Example

# Initialize
finder = MedianFinder()

finder.add_num(1)
finder.add_num(2)
finder.find_median()  # Returns 1.5

finder.add_num(3)
finder.find_median()  # Returns 2.0

Edge Cases

  • The stream starts with an empty structure.
  • The stream contains duplicate integers.
  • The total count of elements is 1.

Hints

Hint 1

Consider maintaining two separate data structures: one to store the smaller half of the numbers and one to store the larger half.

Hint 2

Think about how using heaps (priority queues) could allow you to quickly access the largest element of the smaller half and the smallest element of the larger half.

Hint 3

Ensure the sizes of your two heaps are always balanced, differing by no more than 1, to keep the median logic simple.

Follow-up questions

  • How would your implementation change if you needed to support a 'remove' operation for an arbitrary element?
  • What if the stream was distributed across multiple servers? How would you design a system to maintain a global median?
  • How would you handle the data if the input stream was too large to fit in memory?