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

Solution: Find Median from Data Stream

Explore how to implement a MedianOfStream class in C++ that maintains two heaps to store dynamically changing integers. Learn to insert numbers and find the median in constant time. This lesson covers the use of max-heaps and min-heaps to balance data, enabling efficient calculation of the median as new elements stream in.

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 ...