This interview question evaluates requirements, scale assumptions, API/data design, architecture, trade-offs, failure modes, and rollout in a realistic interview setting. A strong answer for Scale median under memory constraints states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Assume the two-heap streaming-median approach exceeds available memory for a very large or unbounded stream. Identify the bottlenecks and propose scalable designs to continue producing exact or approximate medians and the loose-median interval under memory constraints. Consider options such as external-memory algorithms, bucketization, quantile sketches, distributed aggregation, and windowed processing. Explain trade-offs in accuracy, latency, memory, and I/O, and outline failure handling and back-pressure strategies.
Quick Answer: This interview question evaluates requirements, scale assumptions, API/data design, architecture, trade-offs, failure modes, and rollout in a realistic interview setting. A strong answer for Scale median under memory constraints states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Design a Scalable Streaming Median Service Under Memory Constraints
Context
You are building a service that consumes a very large or unbounded stream of numeric values and must continuously report:
The median (exact if feasible, otherwise approximate), and
A "loose-median" interval: a value range [L, R] guaranteed to contain the true median.
The classic two-heap (max-heap for lower half, min-heap for upper half) approach requires storing all seen values and therefore exceeds memory when the stream is very large.
Tasks
Identify the bottlenecks of the in-memory two-heap approach for very large/unbounded streams.
Propose scalable designs that continue producing exact or approximate medians and the loose-median interval under memory constraints. Consider:
External-memory (disk-backed) algorithms
Bucketization/histograms
Quantile sketches (e.g., GK, KLL, t-digest)
Distributed aggregation
Windowed (e.g., sliding/tumbling) processing
Explain the trade-offs across accuracy, latency, memory, and I/O for each option.
Outline failure handling and back-pressure strategies suitable for a production service.
State any minimal assumptions you make (e.g., numeric domain, tolerance for approximation, latency SLOs).
Constraints & Assumptions
Preserve the scope, facts, inputs, and requested outputs from the prompt above.
If the prompt leaves a detail unspecified, state a reasonable assumption before relying on it.
Keep the answer interview-ready: concise enough to present, but concrete enough to implement or evaluate.
Clarifying Questions to Ask Guidance
Clarify users, core use cases, read/write patterns, scale, latency, availability, and data retention.
State explicit assumptions before making sizing or architecture decisions.
Prioritize the functional path first, then address reliability, security, observability, and rollout.
What a Strong Answer Covers Guidance
A scoped requirements summary with concrete non-goals and success metrics.
API, data model, architecture, consistency, capacity, and operations.
Reasoned trade-offs among simple and scalable designs, including bottlenecks and failure modes.
A validation, monitoring, migration, and launch plan appropriate for the risk level.
Follow-up Questions Guidance
What breaks first at 10x traffic or data volume?
How would you degrade gracefully during dependency failures?
What metrics and alerts would prove the design is healthy after launch?