Top K Frequent Words Stream | Dataford Interview Questions

Scribd processes document text as an iterable of complete text chunks. Implement a function that returns the k most frequent words without concatenating the entire stream into one string.

Words are case-insensitive and consist of alphanumeric characters, with an optional internal apostrophe, such as don't. Ignore punctuation and other separators. If two words have the same frequency, sort the lexicographically smaller word first. Return fewer than k words when the stream contains fewer unique words.

Formal Specification

Input: documents, an iterable of strings where each string is an independent document or text chunk, and integer k.
Output: A list of at most k strings ordered by descending frequency, then ascending lexicographic order.
Word matching is performed independently within each document, so a word cannot span two input strings.

Constraints

1 <= k
documents is an iterable of strings
The total input text may contain millions of characters
The total number of unique normalized words is at most 10^6
Words contain ASCII letters or digits, with an optional internal apostrophe
Return fewer than k words when fewer than k unique words exist

Function Signature

def top_k_words(documents, k):

Your question is Top K Frequent Words Stream. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem