Design Search Autocomplete System
Understanding the Problem
We need to build something that behaves like a search bar. As the user types characters one by one, the system suggests the top 3 most-typed sentences that match what has been typed so far. When the user finishes typing (signaled by #), the system records that sentence.
Two concerns combine here: prefix matching and ranking. We need to find all sentences sharing a prefix, then pick the top 3 by frequency (with ties broken alphabetically), and we have to do this on every keystroke.
Prefix matching points to a Trie (prefix tree), which is built for exactly this kind of lookup. The ranking component adds the harder part, because a Trie on its own only records which strings exist, not which ones are most frequent. So the design question is how to combine prefix matching with efficient top-k retrieval.
Key Constraints:
n <= 100sentences, each up to 100 characters long. The initial data set is small, so even a brute-force construction is feasible.- Up to
5000calls toinput, and each call should be fast. A Trie reduces the per-call cost compared to scanning every sentence. - Characters are lowercase letters and spaces, so a Trie node needs 27 children (26 letters plus space), not 26.
Approach 1: Brute Force (HashMap + Sort on Every Query)
Intuition
Keep a HashMap mapping each sentence to its frequency count. Every time the user types a character, append it to the current prefix. Then scan through all sentences, filter those starting with the current prefix, sort them by frequency (descending) then alphabetically (ascending), and return the top 3.
This is simple but does redundant work. Every keystroke triggers a full scan and sort of all sentences. It stays within the given constraints but does not scale.
Algorithm
- Store all sentences and their counts in a HashMap.
- Maintain a
StringBuilderfor the current input prefix. - On each
input(c)call: - If
c == '#', add the current prefix to the HashMap (increment count), reset the prefix, return empty list. - Otherwise, append
cto the prefix. Filter all sentences that start with the current prefix. Sort by count descending, then alphabetically. Return the top 3.
Example Walkthrough
Code
- Time Complexity: O(n * l + n log n) per
inputcall, where n is the total number of sentences and l is the average sentence length. We scan all n sentences and check if each starts with the prefix, then sort the matching subset. - Space Complexity: O(n * l). We store all sentences and their counts in the HashMap.
On every keystroke we scan every sentence and re-sort. The candidate set only shrinks as the prefix grows, yet we re-filter from scratch each time. The next approach organizes the sentences so we can jump directly to the node for the current prefix and look at only the matching ones.
Approach 2: Trie with DFS Collection
Intuition
A Trie organizes strings by their characters, so all sentences sharing a prefix live in the same subtree. We insert every sentence into the Trie, storing the sentence's frequency at its terminal node. When the user types a character, we move to the node for the current prefix, run a DFS to collect all sentences in that subtree, sort them by frequency, and return the top 3.
Compared to the HashMap approach, we never look at sentences outside the current subtree. We also keep a pointer into the Trie that advances one level deeper per keystroke, so reaching the prefix node costs one edge traversal instead of a full string comparison against everything.
Algorithm
- Build a Trie from all initial sentences. Each node has children for 'a'-'z' and space (' '). Terminal nodes store the sentence string and its count.
- Maintain a current node pointer (starts at root) and a prefix string.
- On
input(c): - If
c == '#', insert the current prefix into the Trie (increment count at terminal node), reset prefix and pointer, return empty list. - Move the pointer to the child for character
c. If no such child exists, set pointer to null (no matches possible until reset). - If pointer is null, return empty list.
- DFS from the current pointer node to collect all sentences in the subtree.
- Sort by count descending, then alphabetically ascending. Return top 3.
Example Walkthrough
Code
- Time Complexity: O(total_chars) for construction. O(subtree_size + k log k) per
inputcall, where subtree_size is the number of nodes beneath the current prefix and k is the number of matching sentences. In the worst case (single-character prefix), this is similar to brute force. - Space Complexity: O(total_chars). The Trie stores one node per character across all sentences.
The DFS still visits the entire subtree on every keystroke, and we sort all matches only to return 3 of them. The next approach stores the top 3 sentences at each node ahead of time, so a query reads the answer directly without any DFS or sorting.
Approach 3: Trie with Pre-stored Top-3 Results (Optimal)
Intuition
Instead of collecting and sorting at query time, pre-compute the top 3 sentences at every node during insertion. Each Trie node maintains a sorted list of at most 3 sentences that share the prefix leading to that node.
When the user types a character, we move to the next node and return its stored list directly. There is no DFS, no sorting, and no collecting at query time.
The trade-off is more expensive insertion. Inserting or updating a sentence walks its entire Trie path and updates the top-3 list at every node on the way. Each update sorts at most 4 elements (the existing 3 plus the new candidate), and the path is at most the sentence length, so the insertion cost stays small.
A node's top-3 list must hold the three best sentences in its entire subtree, not only the sentences whose path passes through it directly. Every sentence that lives in a subtree shares the prefix of that subtree's root, so its full insertion path includes that root. Because insertion updates the list at every node along the path, each ancestor of a sentence sees that sentence as a candidate. The per-node list therefore considers exactly the sentences below it, and keeping the best 3 at each step is safe: a sentence dropped from a node's list ranks below 3 others that are also in the subtree, so it can never belong in that node's answer.
Algorithm
- Build a Trie where each node stores a list of at most 3 sentences (the top 3 by frequency, then alphabetically).
- During insertion, walk the path for the sentence. At each node, add the sentence to the top-3 list, re-sort, and trim to 3.
- Maintain a current node pointer and prefix string.
- On
input(c): - If
c == '#', insert the current prefix into the Trie, reset, return empty list. - Move to the child for
c. If it does not exist, set pointer to null, return empty list. - Return the top-3 list stored at the current node.
Example Walkthrough
Code
- Time Complexity: O(total_chars) for construction. O(1) per
input(c)when c is not '#'. O(sentence_length) perinput('#')for inserting and updating top-3 along the path. Since k=3 is constant, sorting at each node is O(1). - Space Complexity: O(total_chars). Each Trie node stores up to 3 sentence string references. The Trie itself has one node per character across all sentences.