โ† Adobe questions

Mean and median of dynamic stream

Filed under Adobe

Free read 2 of 3

Confirm requirements for mean and median, expected stream size, and performance expectations for inserts versus queries.

The question

Design a data structure that supports adding numbers from a dynamic stream and efficiently computing the current mean and median of all numbers added so far.

Constraints

  • Numbers can be added continuously at runtime.
  • Mean calculation should be O(1) time.
  • Median calculation should be O(log n) time per insertion.

Examples

Input
add(1), add(2), getMean(), getMedian()
Output
mean: 1.5, median: 1.5
Why
After adding 1 and 2, the sum is 3 (mean 1.5) and the middle elements are 1 and 2 (median 1.5).

Approach

  1. Confirm requirements for mean and median, expected stream size, and performance expectations for inserts versus queries.

Solution

O(log n) time per add, O(1) time for mean/median, O(n) space

Python
import heapq

class MedianFinder:
    def __init__(self):
        self.small = []
        self.large = []
        self.total_sum = 0
        self.count = 0

    def addNum(self, num: int) -> None:
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))
        self.total_sum += num
        self.count += 1

    def findMean(self) -> float:
        return self.total_sum / self.count if self.count else 0.0

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return -self.small[0]
        return (-self.small[0] + self.large[0]) / 2.0

Tips

  • What they are testing: Test with empty streams, duplicate elements, negative numbers, and odd/even total counts.
  • Common mistake: Using a single sorted array which results in O(n) insertions, or failing to balance the two heaps properly.

Related Adobe questions

Collected from public candidate posts and coding forums. Updated Nov 2026.