Find Median from a Data Stream

Try to solve the Find Median from a Data Stream problem.

We'll cover the following

Statement
Examples
Understand the problem
Figure it out!
Try it yourself

Statement #

Create a data structure that can store a list of integers that can change in size over time and find the median from this dynamically growing list in constant time, $O(1)$ .

Implement a class, MedianOfStream, which should support the following operations:

Constructor(): This initializes the object of this class, which in turn creates the max and the min heap.
Insert Num(num): This adds an integer, num, to the data structure.
Find Median(): This finds the median of all elements seen so far. If there are an even number of elements, return the average of the two middle values.

Constraints:

$-10^5 \leq$ num $\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, $500$ calls will be made to the function that calculates the median.

Drag and drop the cards to rearrange them in the correct sequence.

Split up incoming numbers into two lists—small and large. Those that are smaller than the current middle element are small, and those that are larger than it are large.

Maintain these lists as heaps so that the root of the small heap is the largest element in it and the root of large heap is the smallest element in it.

If the size of the large heap is greater than the size of small heap or, if size of small heap is greater than the size of the large heap + 1, rebalance the heaps.

If the number of elements is even, the median is the mean of the root of the two heaps. Else, it’s the root of the small heap.

Python

median_of_stream.py

min_heap.py

max_heap.py

from min_heap import *
from max_heap import *
# Tip: You may use some of the code templates provided
# in the support files
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

Enter to Rename, Shift+Enter to Preview

Input #1

Input #2

Find Median from a Data Stream

Solution: Maximize Capital

Solution: Find Median from a Data Stream

Find Median from a Data Stream

Statement #

Examples#

Understand the problem#

Figure it out!#

Try it yourself#