How Would You Build Autocomplete Using a Trie?
Learn how to design autocomplete with a trie, ranked caching, and O(m) prefix lookups for this interview question.
Expected Interview Answer
You build autocomplete by inserting every candidate string into a trie character by character, then for a typed prefix you walk the trie to the node matching the last character of that prefix and perform a DFS over its subtree to collect every complete word stored beneath it, typically ranking the results by frequency or recency.
The walk to locate the prefix node costs O(m) where m is the prefix length, independent of how many total strings are stored, because each character step follows exactly one child pointer. Once at that node, gathering the k best suggestions means traversing the subtree and either collecting all end-of-word nodes or, for large datasets, caching a small ranked list of top completions at each node so lookup avoids re-scanning the whole subtree on every keystroke. Real systems augment the plain trie with frequency counters, a max-heap or sorted cache per node, and sometimes compression (a radix tree) to reduce the node count for sparse alphabets. The tradeoff versus a hash-set-based approach is memory for child pointers in exchange for prefix locality that a hash structure cannot offer without scanning.
- O(m) prefix walk regardless of dataset size
- Suggestions ranked without rescanning all strings
- Shared storage for common prefixes saves memory
- Extends naturally to fuzzy or ranked completion
AI Mentor Explanation
A coaching library indexes drill names letter by letter so that typing "cov" walks three shared shelves and lands directly on every drill starting with "cover", such as "cover drive" and "cover fielding footwork". Each shelf node also keeps a small card listing the two or three most-requested drills beneath it, so the librarian never re-reads every drill title on that branch to answer "what do coaches ask for most". Retrieving suggestions for a typed prefix means walking to that shelf then reading the pre-ranked card, not searching the whole catalog. This mirrors how a trie separates the cheap prefix walk from the ranked-suggestion lookup.
Step-by-Step Explanation
Step 1
Insert every candidate string
Walk or create a child node per character; mark end-of-word and optionally store a frequency counter.
Step 2
Walk to the prefix node
Follow child pointers for the typed prefix; O(m) where m is the prefix length.
Step 3
Collect and rank completions
DFS the subtree for end-of-word nodes, or read a pre-cached ranked list stored at that node.
Step 4
Update caches incrementally
When frequency changes, update the ranked cache along the path instead of recomputing from scratch each query.
What Interviewer Expects
- Explain the insert-then-prefix-walk mechanism clearly
- State O(m) prefix lookup independent of dataset size
- Mention ranking strategy: per-node cached top-k, not full rescans
- Acknowledge memory tradeoffs and mention compression (radix tree) as a refinement
Common Mistakes
- Re-scanning the entire subtree on every keystroke instead of caching top-k per node
- Forgetting the end-of-word marker, causing prefixes to be misreported as complete words
- Ignoring ranking entirely and returning suggestions in arbitrary insertion order
- Not considering memory overhead of many child pointers on sparse alphabets
Best Answer (HR Friendly)
“I would store every candidate word in a trie, letter by letter, so that all words sharing a prefix share the same path. When someone types, I walk down that shared path and just look at what is below it — and if I also keep a small cached list of the most popular items at each node, the suggestions come back instantly without rescanning anything.”
Code Example
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
self.top_k = [] # cached list of (word, freq), sorted desc
class AutocompleteTrie:
def __init__(self, k=3):
self.root = TrieNode()
self.k = k
def insert(self, word, freq=1):
node = self.root
for ch in word:
node = node.children.setdefault(ch, TrieNode())
self._update_cache(node, word, freq)
node.is_word = True
def _update_cache(self, node, word, freq):
entries = dict(node.top_k)
entries[word] = entries.get(word, 0) + freq
node.top_k = sorted(entries.items(), key=lambda kv: -kv[1])[: 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_k]Follow-up Questions
- How would you handle fuzzy matching for a typo in the prefix?
- How would you keep the cached top-k list fresh as popularity shifts over time?
- How would a radix tree reduce memory versus a plain trie here?
- How would you shard this trie across multiple servers for a huge dataset?
MCQ Practice
1. What is the time complexity of walking to a prefix node of length m in a trie?
Walking the prefix follows one child pointer per character, giving O(m), independent of total stored strings.
2. Why do production autocomplete tries cache a ranked top-k list at each node?
Caching top-k per node avoids repeated subtree traversal and ranking work on every keystroke.
3. What is the main memory tradeoff of a trie-based autocomplete versus a hash set?
Tries trade extra pointer memory for O(m) prefix locality that hash sets cannot provide without scanning.
Flash Cards
What does walking a trie to a prefix node cost? — O(m), where m is the length of the typed prefix, regardless of dataset size.
How do production autocomplete systems avoid rescanning subtrees per keystroke? — They cache a ranked top-k list of completions at each node, updated incrementally.
What marks a complete stored word in a trie node? — An end-of-word flag, distinguishing full words from mere prefix nodes.
What structure reduces trie memory for sparse alphabets? — A radix tree (compressed trie), which merges single-child chains into one edge.