Autocomplete with a trie
On the roadmap:Staff Engineer · step 1: Search and relevance
Store words in a tree of letters so every word with a given prefix sits under one branch, then suggest the most popular ones.
In plain words
Imagine a family tree of letters: c has children a and o, ca has children r and t, and so on. To suggest words for 'ca' you walk down c then a, collect everything below, and show the most popular few.
Why it matters
Looking up a prefix in a plain list means scanning every word. In a trie the prefix takes you straight to the right branch in as many steps as the prefix is long, which is what makes suggestions feel instant as you type.
Where you meet it
- Search boxes and address bars that suggest as you type
- Phone keyboards and code editors completing words
- Routing tables and dictionaries where prefixes matter
You will be able to
- Find every word under a prefix without scanning the rest
- Rank suggestions by popularity
- Say how real systems keep lookups fast when a prefix has millions of words below it
In interviews
The core of 'design search autocomplete' and 'type-ahead'. Expect questions on ranking and on keeping it fast.
Practise on the Interview Ready roadmap1Learn the idea first
2See it work before you read the code
3Build it and run the check
What you build
- A tree where each step down is one letter
- insert() that records a word and adds to its weight
- suggest() that walks down the prefix and gathers the words below it
- Ranking by popularity, then alphabetically
type TrieNode = { kids: Map<string, TrieNode>; weight: number; word: string | null };
const node = (): TrieNode => ({ kids: new Map(), weight: 0, word: null });
export class Trie {
root = node();
/** How many nodes the last suggest() looked at, to show what a lookup costs. */
visited = 0;
/** weight: how popular the word is (for example how often people search it). Adding it again adds to its weight. */
insert(word: string, weight = 1): void {
let n = this.root;
for (const ch of word.toLowerCase()) {
let next = n.kids.get(ch);
if (!next) { next = node(); n.kids.set(ch, next); }
n = next;
}
n.word = word.toLowerCase();
n.weight += weight;
}
/** The k most popular words that start with `prefix`. */
suggest(prefix: string, k = 5): { word: string; weight: number }[] {
this.visited = 0;
let n = this.root;
for (const ch of prefix.toLowerCase()) {
const next = n.kids.get(ch);
this.visited++;
if (!next) return [];
n = next;
}
const found: { word: string; weight: number }[] = [];
const walk = (x: TrieNode) => {
this.visited++;
if (x.word !== null) found.push({ word: x.word, weight: x.weight });
for (const kid of x.kids.values()) walk(kid);
};
walk(n);
return found.sort((a, b) => b.weight - a.weight || a.word.localeCompare(b.word)).slice(0, k);
}
}
Rather run it on your own computer?
Save the code as index.ts and the check as check.ts in one folder. The check exits with an error if anything is wrong and prints trie-autocomplete ok when everything passes. You need Node.js installed.
mkdir trie-autocomplete && cd trie-autocomplete
# save index.ts and check.ts in this folder
npx tsx check.tsHow real systems do it
This lab is the core idea in a small form. Here is what production versions add or do differently.
- Real systems precompute the top suggestions at each node, or in a separate cache, so a lookup reads a few entries instead of walking the whole branch.
- The trie is rebuilt from search logs on a schedule and fresh trends are mixed in, because popularity changes through the day.
- Large tries are split across machines by prefix, and the most common prefixes are cached.
- Production adds typo tolerance, personalisation and the removal of unsafe suggestions before anything is shown.
Ways to find words by prefix
| How it works | Lookup cost | Memory | Pick it when | |
|---|---|---|---|---|
| Trie | A tree of letters | The prefix length, plus the words found | One node per letter step | You need prefix lookups with ranking |
| Sorted list with binary search | Find the first word at or after the prefix | Log of the word count, plus the matches | Just the words | Memory is tight and the list rarely changes |
| Hash map | Exact word lookup only | Constant, but no prefix search | The words | You only need exact matches |
| Database LIKE 'prefix%' | An index range scan | Depends on the index | Inside the database | The data is already in a database |
| Search engine with n-grams | Index pieces of words | Fast, and supports typos | Larger | You also need typo tolerance and full text |
What it cannot do
It can use a lot of memory
Each letter step is a node, so millions of words with little shared prefix make millions of nodes.
A popular prefix is slow to scan
A prefix like 'a' has most words below it. Keeping the top few at each node avoids walking them all.
Popularity goes stale
Weights come from past searches. Without refreshing them, suggestions lag behind what people search now.
It needs exact letters
A typo sends the walk down the wrong branch, so no suggestions appear.
4Now extend it
Each one makes your version closer to what real systems do. Pick one and make the check cover it.
- Keep the top five words at every node so a lookup does not scan the whole branch
- Tolerate a typo by also exploring neighbouring letters
- Store the trie compactly by merging chains of single-child nodes