Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns in Python

Find Median from Data Stream

Understand how to implement a data structure that supports dynamic integer insertion and returns the median in constant time. Learn to use heaps for efficient median finding in streaming data and practice coding this approach ready for technical interviews.

We'll cover the following...

Statement

Design a data structure that stores a dynamically changing list of integers and can find the median in constant time, O(1)O(1), as the list grows. To do that, implement a class named MedianOfStream with the following functionality:

  • Constructor(): Initializes an instance of the class.

  • insertNum(int num): Adds a new integer num to the data structure.

  • findMedian(): Returns the median of all integers added so far.

Note: The median is the middle value in a sorted list of integers.

  • For an odd-sized list (e.g., [4,5,6][4, 5, 6]), the median is the middle element: 55.

  • For an even-sized list (e.g., [2,4,6,8][2, 4, 6, 8]), the median is the average of the two middle elements: (4+6)/2=5(4 + 6) / 2 = 5.

Constraints:

  • −105≤-10^5 \leq num ≤105\leq 10^5, where num is an integer received from the data stream.

  • There will be at least one element in the data structure before the median is computed.

  • At most, 500500 calls will be made to the function that calculates the median.

Examples

canvasAnimation-image
1 / 3

Understand the problem

Take a moment to make sure you’ve correctly understood the problem. The quiz below will help you check if you’re solving the correct problem:

Find Median from a Data Stream

1.

What is the median of the stream [12,14,36,54][12, 14, 36, 54] after inserting all elements?

A.

25.0

B.

29.0

C.

36.0

D.

14.0

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4

Try it yourself

Implement your solution in the following coding playground.

Python
usercode > median_of_stream.py
from heapq import *
class MedianOfStream:
  def __init__(self):
    # Write your code here
    pass
  # This function should take a number and store it
  def insert_num(self, num):
    # Write your code here
    pass
  # This function should return the median of the stored numbers
  def find_median(self):
    # Replace this placeholder return statement with your code
    return 0.0
Find Median from Data Stream