Scale median under memory constraints

Quick Overview

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.

Scale median under memory constraints

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).

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?

Scale median under memory constraints

Quick Overview

Scale median under memory constraints

Scale median under memory constraints

Design a Scalable Streaming Median Service Under Memory Constraints

Context

Tasks

Clarifying Questions to Ask Guidance

What a Strong Answer Covers Guidance

Follow-up Questions Guidance

Submit Your Answer to Earn 20XP