Interview Prepchallenge-problemshardAmazonFacebookGoogleMicrosoft

Find Median from Data Stream

Choose your preparation mode4 modes available

Try It Solution Trace

📋

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. Given the following code snippet and inputs, what is the final returned value of W after executing findMaxCapital(2, 0, [1, 2, 3], [0, 1, 1])?

easy

A. 3

B. 4

C. 5

D. 2

3. Consider the following buggy code for finding employee free time. Which line contains the subtle bug that causes incorrect free time intervals?

def employeeFreeTime(schedule):
    intervals = [iv for employee in schedule for iv in employee]
    intervals.sort(key=lambda x: x[0])
    free_times = []
    prev_end = intervals[0][1]
    for i in range(1, len(intervals)):
        start, end = intervals[i]
        if start >= prev_end:
            free_times.append([prev_end, start])
        prev_end = max(prev_end, end)
    return free_times

medium

A. Line with intervals.sort(key=lambda x: x[0])

B. Line with prev_end = max(prev_end, end)

C. Line with if start >= prev_end:

D. Line with prev_end = intervals[0][1]

4. Consider the following buggy code snippet for minimizing deviation. Which line contains the subtle bug that can cause incorrect results?

import heapq

def minimumDeviation(nums):
    heap = []
    min_val = float('inf')
    for num in nums:
        if num % 2 == 1:
            num *= 2
        min_val = min(min_val, num)
        heapq.heappush(heap, num)  # BUG: pushing positive num instead of negative

    min_dev = float('inf')
    while True:
        max_val = -heapq.heappop(heap)
        min_dev = min(min_dev, max_val - min_val)
        if max_val % 2 == 0:
            max_val //= 2
            min_val = min(min_val, max_val)
            heapq.heappush(heap, -max_val)
        else:
            break
    return min_dev

medium

A. Line updating min_val after halving max_val

B. Line pushing elements into heap (heapq.heappush(heap, num))

C. Line popping max_val from heap

D. Line breaking loop when max_val is odd

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Find Median from Data Stream

Practice

Solution

Step 1: Trace first iteration with W=0

Step 2: Trace second iteration with W=1

Final Answer:

Quick Check:

Solution

Step 1: Understand problem constraints and operations

Step 2: Identify approach that efficiently tracks max and min values

Final Answer:

Quick Check:

Solution

Step 1: Identify condition for free time

Step 2: Analyze buggy condition

Final Answer:

Quick Check:

Solution

Step 1: Identify heap usage

Step 2: Locate bug in heap push

Final Answer:

Quick Check:

Solution

Step 1: Identify decrement of count

Step 2: Locate missing decrement

Final Answer:

Quick Check:

Ready to prove it?