Trie: how to spot it
We'll cover the following
A trie stores words letter by letter in a tree, so words with the same beginning share the same path. Looking up a prefix costs one step per letter, no matter how many words are stored.
How the question sounds
- Words that share prefixes: starts with, autocomplete, spell check
- Many prefix lookups over a big dictionary
- Find all words with a given prefix
- Longest common prefix of many strings
- Word search on a board with a word list
The two shapes
Where it shows up in GenAI work
Tokenizers match the longest known token at each position, and a trie is a natural way to do it. Autocomplete and constrained decoding use prefixes. Serving systems cache the attention state of shared prompt prefixes in a radix tree, which is a compressed trie (for example SGLang's RadixAttention).
Is it trie?
Decide yes or no before you open each answer.
Check yourselfSuggest all words that start with what the user typed.
Yes. Prefix lookup is the trie's main job.
Check yourselfFind the longest common prefix of a list of words.
Yes. Walk the trie while there is a single branch.
Check yourselfMatch the longest known token at a position in text.
Yes. Tokenizer vocabularies are searched like a trie.
Check yourselfCount how many times each word appears.
No. A hash map of counts is simpler.
Check yourselfFind the shortest route between two cities.
No. A graph shortest-path problem.
Check yourselfMerge overlapping time ranges.
No. Intervals.
Problems in this pattern
- Build a trie · Medium · Insert words
- Search and prefix check · Medium · Walk the path
- Autocomplete · Medium · Prefix then collect
- Longest common prefix · Easy · Single-branch walk
Summary: say it in the interview
- Insert and search: Follow one branch per letter. A flag on the last node says whether a real word ends there.
- Prefix queries: Walk to the prefix node once, then everything below it is a match.