Autocomplete Design

Store sentences in a trie. At each node, maintain a sorted list of top sentences passing through.

class TrieNode:
    children: map
    suggestions: list of (sentence, count) sorted by (-count, sentence)

When inserting a sentence:

$1.$ Update the count in the trie

$2.$ For each node along the path, update its suggestions list When querying prefix:

$1.$ move through to prefix node

$2.$ Return top 3 from node's suggestions list Trade-off: storing suggestions at each node uses more space but makes queries $O(L)$ instead of traversing subtrees. Alternative: only store at end nodes, then collect and sort during query. Better space, worse query time. Time: $O(L)$. Space: $O(L)$.