Find the Top Ten Words When a Book Exceeds Memory
Company: Robinhood
Role: Software Engineer
Category: System Design
Difficulty: easy
Interview Round: Technical Screen
How would you find the ten most frequent words in a book that is too large to load into memory? Explain what changes when even the distinct-word frequency table does not fit in memory, and when processing needs to run on multiple machines.
### Requirements and Constraints
For this exercise, "top" means highest occurrence count, with lexical order breaking ties. Define one consistent tokenization and normalization policy before processing. Exact counts are the default goal; an approximate answer is an option only if its error and acceptance criteria are explicitly agreed.
### Clarifying Questions
- Does the raw text exceed memory, the number of distinct words exceed memory, or both?
- Can the input be read more than once, and is temporary disk storage available?
- What rules define a word, including punctuation, case, and tokens split across input chunks?
- Is the result required to be exact, and what makes processing time acceptable?
```hint A small final answer does not imply a small counting state
Keeping ten current candidates is different from knowing the exact frequencies of every contender. Consider a word that appears moderately often in many chunks.
```
### What a Strong Answer Covers
- Streaming tokenization with correct handling of chunk boundaries and consistent normalization.
- A solution when counts fit in memory and a spill or external-aggregation strategy when they do not.
- Correct global aggregation before final top-ten selection.
- Recovery, deterministic partitioning, and duplicate-processing controls for distributed execution.
- A precise explanation of why taking only each chunk's local top ten can lose a globally important word.
- Explicit approximation trade-offs if an approximate method is proposed.
### Follow-up Questions
1. Why might a word absent from every chunk's local top ten still belong to the global top ten?
2. How would you handle one extremely frequent word that creates an imbalanced aggregation workload?
3. How would a retried processing task avoid counting its chunk twice?
Overview: Count top words in a large book using streaming tokenization, external aggregation, distributed recovery, and correct global top-ten selection.