Choose a Median Algorithm for a Large Dataset
Company: SIG (Susquehanna)
Role: Quantitative Researcher
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
How would you calculate the median quickly when the dataset contains a very large number of values?
### Clarifying Questions
Determine whether the data is an in-memory batch, a stream, or a file larger than memory; whether an exact median is required; whether values have a small known domain; and whether the input may be rearranged. None of these details is fixed. For numeric data, state whether an even-sized dataset returns the mean of its two middle values. An empty dataset has no median.
### What a Strong Answer Covers
Choose an algorithm for each relevant access and memory model. Explain both runtime and storage, including why maintaining two heaps does not solve an unlimited stream's memory problem.
### Follow-up Questions
- What changes if the data is already sorted in several files?
- What tradeoff becomes available if an approximate quantile is acceptable?
Overview: Choose a median algorithm based on data size, access pattern, memory, and accuracy requirements. Compare selection, two heaps, external sorting, and domain-based counting without confusing streaming updates with bounded memory.
Read the full SIG (Susquehanna) Quantitative Researcher interview experience this question came from