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 Python code snippet implementing the AllOne data structure, what is the output of getMaxKey() after these operations?

all_one = AllOne()
all_one.inc('apple')
all_one.inc('banana')
all_one.inc('apple')
all_one.dec('banana')
print(all_one.getMaxKey())

easy

A. "" (empty string)

B. "apple"

C. "banana"

D. Raises an exception

2. Given the following code snippet for the optimal Twitter design, what is the output of getNewsFeed(1) after these operations?

twitter = Twitter()
twitter.postTweet(1, 5)
twitter.postTweet(2, 6)
twitter.followees[1] = {2}
print(twitter.getNewsFeed(1))

Assume getNewsFeed returns a list of tweetIds sorted from most recent to oldest.

easy

A. [6]

B. [5, 6]

C. [5]

D. [6, 5]

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 increments and decrements

Step 2: Check getMaxKey()

Final Answer:

Quick Check:

Solution

Step 1: Trace postTweet calls

Step 2: Trace getNewsFeed(1)

Final Answer:

Quick Check:

Solution

Step 1: Understand the eviction criteria

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

Final Answer:

Quick Check:

Solution

Step 1: Identify difference from correct code

Step 2: Understand impact of redundant points

Final Answer:

Quick Check:

Solution

Step 1: Understand impact of negative heights

Step 2: Modify merge logic accordingly

Step 3: Evaluate other options

Final Answer:

Quick Check:

Ready to prove it?