How would you design a typeahead/autocomplete system?

class Node:
    def __init__(self):
        self.children = {}
        self.top = []                 # cached (weight, word), best first

class Trie:
    def __init__(self, k=5):
        self.root = Node()
        self.k = k
    def insert(self, word, weight):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, Node())
            node.top = sorted(set(node.top + [(weight, word)]), reverse=True)[: self.k]
    def suggest(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return []
            node = node.children[ch]
        return [w for _, w in node.top]

t = Trie()
for word, freq in [("cat", 9), ("car", 7), ("cards", 3), ("dog", 5)]:
    t.insert(word, freq)
print("ca ->", t.suggest("ca"))   # ['cat', 'car', 'cards'] (by popularity)