Mean and median of dynamic stream
Filed under Adobe
Free read 2 of 3Confirm 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
Confirm requirements for mean and median, expected stream size, and performance expectations for inserts versus queries.
Maintain a dynamically resized list of all elements. Compute sum and size for mean in O(1), sort for median in O(n log n).
Use two heaps: a max-heap for the lower half and a min-heap for the upper half. Keep heaps balanced in size. Mean uses running sum and count; median is derived from heap roots.
Stream with 0 or 1 element, or handling integer overflow for the running sum.
Solution
O(log n) time per add, O(1) time for mean/median, O(n) space
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.