Rank the K Most Common Words With Alphabetical Ties, Then Over a Stream

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

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.

Bloomberg logo
Bloomberg
Nov 12, 2026
mediumSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals
1
0

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 Guidance

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

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.

What This Part Should Cover Guidance

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

Clarifying Questions for this Part Guidance

  • 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 Guidance

  • 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 Guidance

  • 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 Guidance

  • 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?