Problem. You have a log of past queries with their counts. As a user types, return the k most frequent past queries that start with the typed prefix (ties broken alphabetically). New searches keep arriving, so counts grow over time.
counts = {"transformer": 50, "transformers tutorial": 30, "train test split": 45,
"tranformer": 3, "tree": 20, "trie": 8}
top_k("tra", k=3) → ["transformer", "train test split", "transformers tutorial"]
top_k("tri", k=3) → ["trie"]
Every keystroke is a new query, and suggestions must come back in a few milliseconds. The shape of the solution: walk to the prefix node in O(|p|), then answer from that node only, ideally from an answer already stored there.
ML context. This is the candidate-generation step of query suggestion in search engines, code completion and chat input boxes. Production systems generate a short list of prefix matches from a trie like this one, then re-rank it with a model that knows the user, the context and recency (Change D). The trie keeps the expensive model away from millions of candidates.