Katkat
Back

Maintain the Median of an Integer Stream

StackAdaptMachine Learning Engineer · Technical Screen
EasyMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to maintain dynamic statistics in a data stream using efficient heap-based data structures.

Problem Statement

Design a data structure MedianFinder that accepts integers from a stream and provides the current median at any time. If the total number of integers in the stream is even, the median is the average of the two middle elements.

Implement the MedianFinder class:

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

Constraints

  • add_num will be called at most 5 * 10^4 times.
  • find_median will be called at most 5 * 10^4 times.
  • The values in the stream will be between -10^5 and 10^5.

Example

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

  • Stream with only one number.
  • Stream with all identical numbers.
  • Stream with an odd number of elements vs. an even number of elements.

Hints

Hint 1

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

Hint 2

A max-heap can store the smaller half, while a min-heap stores the larger half, ensuring the root of each heap provides quick access to the middle elements.

Hint 3

Always rebalance the heaps after every insertion so that the difference in the number of elements between the two heaps is no more than one.

Follow-up questions

  • What is the space complexity of your solution, and can you optimize it if we only care about the median of the last 1,000,000 elements?
  • How would you modify your design if you needed to support a 'remove_num' operation in addition to 'add_num'?
  • If the stream is distributed across multiple machines, how would you approach calculating a global median?