How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Design a streaming median structure | Amazon Coding Question

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Design a streaming median structure states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Design a streaming median structure

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Design a data structure for a number stream that supports: add(num: int) in O(log n) time and median() -> float in O( 1) or O(log n) time. It must handle up to 10^6 operations, duplicates, and both even/odd counts. Describe the APIs, internal invariants, and prove the time/space complexity. Implement the core methods.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Design a streaming median structure states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Implement a data structure for a number stream that supports two operations and runs each operation efficiently enough to handle up to 10^6 operations with duplicates and both even/odd counts: - add(num): insert an integer into the stream in O(log n) time. - median(): return the median of all numbers added so far in O(1) time. If the count is even, the median is the average of the two middle values; if odd, it is the single middle value. The median of an empty stream is undefined (return None / null). Driver format: you are given a list of operations to replay in order. Each operation is a list: - ["add", num] -> insert num, contributes None to the output. - ["median"] -> append the current median (a float, or None if the stream is empty). Return a list with exactly one entry per operation. Internal invariants (two-heap design): keep a max-heap `lo` for the smaller half and a min-heap `hi` for the larger half, maintaining len(lo) == len(hi) or len(lo) == len(hi) + 1. The median is the top of `lo` when sizes differ, or the average of both tops when sizes are equal. add() pushes onto the correct heap then rebalances by at most one move (O(log n)); median() reads heap tops (O(1)). Space is O(n).

Constraints

1 <= number of operations <= 10^6
-10^9 <= num <= 10^9
median() may be called on an empty stream (return None / null)
Duplicates are allowed; both even and odd total counts must be handled

Examples

Input: ([['add', 1], ['add', 2], ['median'], ['add', 3], ['median']],)

Expected Output: [None, None, 1.5, None, 2.0]

Explanation: After 1,2 the median is (1+2)/2 = 1.5 (even count). After adding 3, the median of {1,2,3} is 2.0 (odd count).

Input: ([['median']],)

Expected Output: [None]

Explanation: Median of an empty stream is undefined, so None is returned.

Input: ([['add', 5], ['median']],)

Expected Output: [None, 5.0]

Explanation: Single element: the median is the element itself, 5.0.

Input: ([['add', 2], ['add', 2], ['add', 2], ['median']],)

Expected Output: [None, None, None, 2.0]

Explanation: Duplicates are handled; the median of {2,2,2} is 2.0.

Input: ([['add', -1], ['add', -2], ['add', -3], ['median'], ['add', -4], ['median']],)

Expected Output: [None, None, None, -2.0, None, -2.5]

Explanation: Negatives and out-of-order inserts: {-1,-2,-3} median -2.0; after adding -4, {-4,-3,-2,-1} median is (-3 + -2)/2 = -2.5.

Input: ([['add', 6], ['add', 10], ['add', 2], ['add', 6], ['add', 5], ['median']],)

Expected Output: [None, None, None, None, None, 6.0]

Explanation: Unordered stream with a duplicate; sorted {2,5,6,6,10} has middle element 6.0.

Hints

Maintain two heaps: a max-heap for the smaller half and a min-heap for the larger half, keeping their sizes balanced to within one element.
On add(), push to the correct half based on the current max-heap top, then move one element across if the size invariant breaks — this keeps the operation O(log n).
On median(), if the heaps are equal size average the two tops; otherwise the larger heap's top is the median. This reads in O(1).

Quick Overview