Implement Smartphone-Keyboard-Style Word Autocompletion from Sample Text

Implement a program that performs simple autocompletion, similar to the kind used on a smartphone keyboard: as the user types the beginning of a word, the program suggests whole words that start with the typed letters. This is a laptop coding round, so the goal is working, tested code, not only a description. The report gives only that one-line prompt. This version assumes the program learns its words from a body of sample text and ranks suggestions by how often each word appeared there; confirm that, and the details in the clarifying questions, with the interviewer before coding. A possible interface: ```python class Autocomplete: def __init__(self, text: str) -> None: ... # learn words from sample text def suggest(self, prefix: str, k: int) -> list[str]: ... # up to k suggested words ``` ```hint Where the time goes Ask how often `suggest` runs compared with how often the vocabulary changes, and which work you could do once up front instead of on every keystroke. ``` ```hint Same input, same answer Decide what happens when two candidate words have the same count, so that a prefix always returns the same list. ``` ### Clarifying Questions - Where do the words and their frequencies come from: a sample text, a dictionary with counts, or the user's own typing? - How are suggestions ranked, how many are returned, and how are ties broken? - Is matching case-sensitive, and how are punctuation, digits and apostrophes (as in "don't") handled when the text is split into words? - Should the program learn while the user types, so that words they use often rise in the ranking? - If the typed prefix is itself a complete word, may it appear among the suggestions? Is an empty prefix valid? ### What a Strong Answer Covers - Agrees on the input format, the ranking and the tie-break before coding - A data structure that finds the words with a given prefix without scanning the whole vocabulary - Returns the top k words efficiently, with the time and memory cost per query and per update stated - One tokenization and normalization rule applied identically to the sample text and to the prefix - Edge cases: empty prefix, no match, fewer than k matches, a prefix that is itself a word - Code that runs and is tested during the interview ### Follow-up Questions - The user types one letter at a time. How do you avoid restarting the lookup from scratch on every keystroke? - Make the program learn from what the user types, so their frequent words rise. What changes, and what does an update cost? - How would you suggest the next word after the user finishes a word, as phone keyboards do? - How would you still find good suggestions when the typed prefix contains one wrong letter?