Preparing your design workspace

Loading the problem and your saved attempt…

Design and Implement a Streaming Median API

Design a stateful in-memory API that accepts numbers over time and returns the exact median on demand.

Design and implement an in-memory API that accepts signed 32-bit integers one at a time and returns the exact median of every value accepted so far. For this exercise, assume an odd-sized stream returns its middle value and an even-sized stream returns the arithmetic mean of its two middle values.

One instance owns one append-only stream in one process. Removal, sliding windows, persistence, networking, and distributed coordination are outside the baseline scope. Define and document the behavior of a median request made before any value has been added. The baseline may assume calls are single-threaded.

Aim for O(log n) insertion, O(1) median lookup, and O(n) memory without sorting the complete stream after every update. After completing the baseline design and core implementation, explain how the same API could safely support concurrent callers.