Build the engine behind a search box's suggestions. A trie (prefix tree) stores words character by character, so finding everything that starts with a prefix only touches that branch.
Implement a class Autocomplete:
add(word, weight=1): add a word with a popularity weight. Adding the same word again adds to its weight.suggest(prefix, k=3): return up to k words starting with prefix, highest weight first, with ties in alphabetical order. An empty prefix matches every word, and an unknown prefix returns [].Don't scan every stored word for each query. Walk the trie down to the prefix first.
Example
ac = Autocomplete()
ac.add("pandas", 5); ac.add("panda", 3); ac.add("python", 9)
ac.suggest("pan") # ["pandas", "panda"]