Rank the K Most Common Words With Alphabetical Ties, Then Over a Stream
Company: Bloomberg
Role: Software Engineer
Category: Software Engineering Fundamentals
Difficulty: medium
Interview Round: Technical Screen
Rank words by how often they occur, then adapt the solution to words that arrive as a stream. The first part is a coding task; the follow-up asks how the approach changes when the input never ends.
### Clarifying Questions
- Are words compared exactly as given, or should case and punctuation be normalized first?
- Should the output contain only the words, or the words with their counts?
- In the stream version, is the ranking over every word seen so far, or over a recent window?
### Part 1 — The k most frequent words
Given a list of words and an integer `k`, return the `k` words that occur most often, ordered from the highest count to the lowest. Words with the same count are ordered alphabetically, and the same rule decides which words make the cut when several tie at the k-th place.
```python
def top_k_words(words: list[str], k: int) -> list[str]:
```
Assume the words are non-empty strings of lowercase English letters and that `k` is at least 1 and at most the number of distinct words. For example, for `["deal", "bond", "deal", "rate", "bond", "fund", "deal"]`, `k = 2` returns `["deal", "bond"]`, and `k = 3` returns `["deal", "bond", "fund"]`, because fund and rate both occur once and fund comes first alphabetically.
```hint How much ranking you need
Counting is the easy half. Ask how much of the full ranking you actually need when `k` is much smaller than the number of distinct words, and how the tie rule must shape whatever structure you keep.
```
#### What This Part Should Cover
- Counting with a hash map, and the cost of counting
- Selecting the top `k` under the two-key order, and the cost compared with sorting every distinct word
- Ties at the k-th place, and `k` equal to the number of distinct words
### Part 2 — Words arrive as a stream
Words now arrive one at a time from a stream that does not end, and the current top `k` can be requested at any moment. Describe and sketch a design that supports `add(word)` and `top_k()`, with the cost of each operation and the memory it uses.
```hint What one word can change
Ask what a single new occurrence of one word can change about the current top `k`, and what you would need to look at to apply that change.
```
#### Clarifying Questions for this Part
- Must the answer be exact, or is an approximate top `k` acceptable when there are too many distinct words to keep every count in memory?
- How often is `top_k()` called compared with `add(word)`?
#### What This Part Should Cover
- An exact design for all-time counts with cheap updates and cheap queries
- How ranking over a recent window changes the design, since counts then also fall
- Approximate counting with bounded memory, and the error it guarantees
### What a Strong Answer Covers
- The count-then-alphabetical order applied correctly in both parts, including inside heap comparisons
- Time and memory for counting, for selection and for each stream operation
- The trade-off between selecting at query time and maintaining the top `k` on every update
- Exact versus approximate counting, and windowed counts that decrease
- Splitting the stream across machines without losing exactness where it matters
### Follow-up Questions
- The stream is split across several machines. How do you compute the global top `k`, and when is merging each machine's local top `k` exact?
- How would you test the streaming version against the batch version from Part 1?
- If the stream processor restarts after a crash, how do you avoid losing or double-counting words?
Overview: A two-part question on word frequency: return the k most frequent words ordered by count with alphabetical tie-breaks, then support the same query over an endless stream of words. It tests hashing, heap-based selection, incremental top-k maintenance, windowed counts and approximate counting with bounded memory.