Crack the Backend

Problem Statement

Design a structure that supports adding numbers from a stream and finding the median of all numbers added so far. addNum(num) adds a number; findMedian() returns the median (the middle value when sorted, or the average of the two middle values if the count is even).

Key Observations

Two heaps: Maintain a max-heap for the lower half of the numbers and a min-heap for the upper half. Keep the sizes balanced so |lower.size() - upper.size()| <= 1. When adding: insert into one heap then move the max of lower (or min of upper) to the other to rebalance. Median: if lower has more elements, return lower.peek(); else if equal, return (lower.peek() + upper.peek()) / 2.0.

Approach

High-level: Max-heap lo, min-heap hi. addNum: offer to lo, then offer(lo.poll()) to hi; if hi.size() > lo.size() offer(hi.poll()) to lo. findMedian: if lo.size() > hi.size() return lo.peek(); return (lo.peek()+hi.peek())/2.0.

Steps: PriorityQueue<Integer> lo = new PriorityQueue<>((a,b)->b-a), hi = new PriorityQueue<>(); addNum: lo.offer(num); hi.offer(lo.poll()); if (hi.size()>lo.size()) lo.offer(hi.poll()). findMedian: return lo.size()>hi.size() ? lo.peek() : (lo.peek()+hi.peek())/2.0;

Implementation

Java

PriorityQueue<Integer> lo = new PriorityQueue<>((a,b)->b-a);
PriorityQueue<Integer> hi = new PriorityQueue<>();

public void addNum(int num) {
    lo.offer(num);
    hi.offer(lo.poll());

    if (lo.size() < hi.size()) {
        lo.offer(hi.poll());
    }
}

public double findMedian() {
    return lo.size() > hi.size() ? lo.peek() : (lo.peek() + hi.peek()) / 2.0;
}

Test Cases

Example

Input

addNum(1), addNum(2), findMedian() -> 1.5, addNum(3), findMedian() -> 2

Expected

2

Explanation

Median of 1,2,3 is 2.

Complexity Analysis

Time: typically O(n log k) or O(n log n).
Space: O(k) or O(n).

Follow-ups

Stream: process one element at a time.