Amazon·Software Engineer·Technical Phone Screen·Senior

Senior

May 2026

Summary

Amazon SWE interview that went deep into data structure design, specifically around streaming medians. The question had multiple layers and they wanted the full picture: API design, invariants, complexity proofs, and working code.

Questions Asked (1)

Design a data structure for a number stream that supports adding a number in O(log n) time and retrieving the median in O(1) or O(log n) time. It needs to handle up to a million operations, duplicate values, and both even and odd element counts. Walk through the API, internal invariants, time and space complexity proofs, and implement the core methods.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

Two heaps was the obvious move and I got there fast, but then they pushed on the invariants and I fumbled a bit.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the API and constraints, then propose a two-heap solution (max-heap for lower half, min-heap for upper half) that maintains balance and ordering. Walk through the invariants, complexity proofs, and implement the core methods, discussing trade-offs and edge cases.

Pro tip: Emphasize that the two-heap approach naturally handles duplicates and even/odd counts, and mention that you can optimize by using a single array with binary search for O(log n) insertion and O(1) median retrieval if memory is not a concern.

1. Clarify Requirements and API

Define the API: addNum(int num) and findMedian(). Clarify constraints: up to 1M operations, duplicates allowed, even/odd counts. Discuss expected time complexities.

2. Propose Data Structure and Invariants

Propose two heaps: a max-heap for the lower half and a min-heap for the upper half. State invariants: max-heap size equals min-heap size or differs by 1; all elements in max-heap ≤ all elements in min-heap.

3. Analyze Complexity and Prove Correctness

Show that addNum is O(log n) due to heap insertions and rebalancing, and findMedian is O(1) by peeking at heap tops. Prove that invariants guarantee the median is at the top(s).

4. Implement Core Methods

Write code for addNum and findMedian, handling rebalancing and edge cases (empty stream, duplicates). Use a max-heap implemented via negative values in a min-heap if needed.

5. Discuss Trade-offs and Alternatives

Mention alternative approaches like a balanced BST or a sorted array with binary search, comparing time/space trade-offs. Highlight why two heaps is optimal for this scenario.

Key Points to Mention

Two-heap approach: max-heap for lower half, min-heap for upper half.
Invariants: size balance (difference ≤ 1) and ordering (max-heap top ≤ min-heap top).
Time complexity: O(log n) for addNum, O(1) for findMedian.
Space complexity: O(n) for storing all elements.
Handling duplicates: heaps naturally allow duplicates; no special handling needed.
Edge cases: empty stream, even/odd counts, and rebalancing after insertion.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.