Interview Prepchallenge-problemshardAmazonFacebookGoogleMicrosoft

Find Median from Data Stream

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

📋

Problem

Imagine you are monitoring live sensor data or stock prices and need to report the median value at any moment as new data arrives continuously.

Design a data structure that supports adding numbers from a data stream and finding the median of all elements so far. Implement two methods: addNum(int num) - adds a number to the data structure; findMedian() - returns the median of all elements added so far. The median is the middle value in an ordered integer list. If the size of the list is even, the median is the average of the two middle numbers.

1 ≤ number of addNum calls ≤ 10^5-10^5 ≤ num ≤ 10^5At least one element will be present before calling findMedian

Edge cases: Only one element added → median is that elementAll elements are the same → median is that elementLarge number of elements with duplicates → median calculation remains correct

</>

IDE

class MedianFinder:
    def __init__(self):
        pass
    def addNum(self, num: int) -> None:
        pass
    def findMedian(self) -> float:
        pass

class MedianFinder:
    def __init__(self):
        # Write your solution here
        pass
    def addNum(self, num: int) -> None:
        pass
    def findMedian(self) -> float:
        pass

public class MedianFinder {
    public MedianFinder() {
        // Write your solution here
    }
    public void addNum(int num) {
    }
    public double findMedian() {
        return 0;
    }
}

#include <vector>
using namespace std;

class MedianFinder {
public:
    MedianFinder() {
        // Write your solution here
    }
    void addNum(int num) {
    }
    double findMedian() {
        return 0;
    }
};

class MedianFinder {
    constructor() {
        // Write your solution here
    }
    addNum(num) {
    }
    findMedian() {
        return 0;
    }
}

0/9

Common Bugs to Avoid

Wrong: Median values off by one or incorrect averagesNot balancing the two heaps properly after insertion✅ After each addNum, rebalance heaps so their sizes differ by at most one

Wrong: Median is always the last inserted element or first elementUsing a greedy approach that does not maintain order or balance✅ Use two heaps to maintain lower and upper halves and compute median from heap tops

Wrong: Median incorrect when duplicates are presentIgnoring duplicates or treating them as single elements✅ Insert all duplicates into heaps and balance normally

Wrong: TLE on large inputsSorting entire list on every addNum call✅ Implement two heaps approach for O(log n) insertion and O(1) median retrieval

Wrong: Median calculation causes integer overflow or wrong averagingUsing integer division or not using float/double for median✅ Use float/double type and compute average as (a + b) / 2.0

✓

Test Cases

t1_01basic

Input["addNum(1)","addNum(2)","findMedian()","addNum(3)","findMedian()"]

Expected[1.5,2]

After adding 1 and 2, the sorted list is [1,2], median is (1+2)/2=1.5. After adding 3, list is [1,2,3], median is 2.

t1_02basic

Input["addNum(5)","addNum(15)","addNum(1)","findMedian()","addNum(3)","findMedian()"]

Expected[5,4]

After adding 5,15,1 the sorted list is [1,5,15], median is 5. After adding 3, list is [1,3,5,15], median is (3+5)/2=4.

Practice

(1/5)

1. You need to design a cache that evicts the least frequently used item when full, and among items with the same frequency, evicts the least recently used one. Which approach guarantees O(1) average time complexity for both get and put operations?

easy

A. Using a simple hash map with frequency counts and sorting keys on each eviction

B. Maintaining a frequency map of doubly linked lists to track keys by frequency and recency

C. Using a min-heap keyed by frequency and timestamp to evict the least frequently used item

D. Using a single doubly linked list ordered by frequency and recency

2. Given the following addRange method snippet from the optimal RangeModule implementation, what is the value of self.starts after calling addRange(2, 6) on an initially empty RangeModule?

def addRange(self, left: int, right: int) -> None:
    i = bisect_left(self.starts, left)
    j = bisect_right(self.starts, right)

    if i != 0 and self.intervals[self.starts[i-1]] >= left:
        i -= 1
        left = min(left, self.starts[i])
    if j != 0:
        right = max(right, self.intervals[self.starts[j-1]])

    for k in self.starts[i:j]:
        del self.intervals[k]
    self.starts[i:j] = [left]
    self.intervals[left] = right

easy

A. [2, 6, 7]

B. [2, 6]

C. [2]

D. [6]

4. Consider the following buggy implementation of SnapshotArray. Which line contains the subtle bug that can cause incorrect get results when multiple sets occur before a snap on the same index?

import bisect

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0
        self.data = [[(-1, 0)] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        # Bug here
        self.data[index].append((self.snap_id, val))

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        arr = self.data[index]
        i = bisect.bisect_right(arr, (snap_id, float('inf'))) - 1
        return arr[i][1]

medium

A. Line in snap(): incrementing snap_id before returning

B. Line in __init__(): initializing with (-1, 0) instead of (0, 0)

C. Line in set(): always appending without checking if last snap_id matches

D. Line in get(): using bisect_right instead of bisect_left

Find Median from Data Stream

Start learning this pattern below

Practice

Solution

Step 1: Understand the eviction criteria

Step 2: Identify data structures supporting O(1) operations

Final Answer:

Quick Check:

Solution

Step 1: Trace bisect indices on empty starts list

Step 2: Update intervals and starts

Final Answer:

Quick Check:

Solution

Step 1: Identify auxiliary data structures

Step 2: Analyze space usage

Final Answer:

Quick Check:

Solution

Step 1: Analyze set() method

Step 2: Consequence on get()

Final Answer:

Quick Check:

Solution

Step 1: Consider negative coordinates impact

Step 2: Consider interval reuse

Final Answer:

Quick Check: