Katkat
Back

Compute the Median After Each Stream Insertion

AmazonSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to maintain dynamic statistics in a data stream using efficient data structures to achieve logarithmic insertion and constant-time retrieval.

Problem Statement

Design a class MedianFinder that maintains a stream of integers and provides the current median after each insertion. If the number of elements in the stream is even, the median is defined as the average of the two middle elements.

Requirements

  • void addNum(int num): Adds an integer to the data structure.
  • double findMedian(): Returns the median of all elements added so far.

Constraints

  • The total number of operations will not exceed 100,000.
  • Integers in the input stream will range from -10^6 to 10^6.
  • findMedian will only be called after at least one element has been added.

Examples

Example 1:

finder = MedianFinder()
finder.addNum(1)
finder.addNum(2)
finder.findMedian() # returns 1.5
finder.addNum(3)
finder.findMedian() # returns 2.0

Example 2:

finder = MedianFinder()
finder.addNum(-1)
finder.findMedian() # returns -1.0
finder.addNum(-2)
finder.findMedian() # returns -1.5

Edge Cases

  • Stream with a single element.
  • Stream with all identical elements.
  • Large numbers of negative values and zero.

Hints

Hint 1

Consider splitting the stream into two halves: a 'lower' half and an 'upper' half.

Hint 2

Think about using two priority queues (heaps) to keep the halves balanced.

Hint 3

The max-heap stores the smaller half of numbers, and the min-heap stores the larger half, ensuring the difference in sizes is at most 1.

Follow-up questions

  • What if 99% of the numbers in the stream fall within the range [0, 100]? How would you optimize for this?
  • How would you modify your implementation to return the 'sliding window median' of the last K elements?
  • If the data is distributed across multiple servers, how would you calculate the global median?