The problem
Design autocomplete: as the user types, suggest the top 3 past sentences that start with what’s typed, ranked by how often they were used (ties alphabetically).
Input: cat:5, car:3, cart:2, care:4, dog:1; typed "car" Output: ["care", "car", "cart"]
Picture it
Picture a phone keyboard storing past words in a letter tree. As you type, it follows the branch for your letters. Every word below that point is a candidate, and the 3 most frequently typed ones are suggested.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Trie + collect words under the prefix node, sorted by (−count, word).
Python solution
class Autocomplete:
def __init__(self, words, times):
self.root = {}
for w, t in zip(words, times):
node = self.root
for ch in w:
node = node.setdefault(ch, {})
node["#"] = t # how often it was typed
def suggest(self, prefix):
node = self.root
for ch in prefix:
if ch not in node:
return []
node = node[ch]
found = all_words_below(node)
return sorted(found, key=lambda w: (-times[w], w))[:3]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.