How the interviewer opens it
“Design a system that sorts a dataset much larger than one machine's memory or disk, potentially petabytes of records. The system can use many machines.”
The prompt is vague on purpose. The first few minutes are yours: narrow it to the core features and agree on the numbers before you draw anything.
What to clarify first
- dataset and job frequency
- records and keys
- meaning of sorted output
- read:write mix
- worker resources
- shared storage capacity
- latency
- key distribution
- correctness, durability, and availability
- scope boundary
The answers stay with the interviewer. In a SysRound round, Alex answers them as an interviewer would.
Scope of a strong answer
Core requirements
- Sort an immutable dataset by a specified key
- Produce globally ordered output without fitting the dataset on any one machine
- Preserve every input record, including duplicates
- Complete correctly despite worker failures and retries
Usually out of scope
- Continuous streaming or incremental sorting
- Interactive queries over the sorted result
- User-defined comparator code
- Cross-region disaster recovery
What interviewers probe
- Global ordering under skew and duplicate keys
- Sorting each worker's data is not enough to make their concatenation sorted. Range boundaries must balance bytes, and a huge equal-key group cannot be balanced using primary-key boundaries alone.
- External sorting and the physical I/O budget
- Every stage exceeds memory, and careless spills, shuffle fan-out, or merge passes can exceed both local disk capacity and the eight-hour storage budget.
- Retry correctness and atomic result publication
- A task can finish writing data and then lose its acknowledgment. Retrying or speculatively executing it must not duplicate records, mix partition plans, or expose an incomplete result.
Common mistakes
- Describing local external merge sort but never explaining how records are distributed to achieve global order.
- Using hash partitioning for the final output.
- Assuming sampled ranges solve giant duplicate-key groups.
- Ignoring intermediate I/O, temporary disk usage, or the shared storage throughput limit.
- Sending all records or per-record metadata through a coordinator.
- Retrying tasks without selecting one output attempt, causing duplicate records or partial publication.
The bar by level
- Senior (L5/E5)
- Quantifies the I/O and space budget, handles unknown skew and huge equal-key groups, bounds shuffle buffers and merge fan-in, and explains attempt selection plus atomic manifest publication. Uses an existing execution framework without treating it as a substitute for explaining the algorithm.
- Staff (L6+/E6+)
- Connects the deadline to shared storage, network, CPU, and temporary-space constraints; identifies when the stated capacity cannot meet the target. Designs safe plan changes and recovery boundaries, compares durable versus reconstructable shuffle, and addresses stragglers, resource admission, and correctness validation without introducing per-record coordination.