Trie Data Structure
Prefix tree for strings — O(key length) lookup powers autocomplete, IP routing, and typeahead.
Interview tip Lead with a 30-second definition, then one real system example and name 2–3 designs where Trie Data Structure is non-negotiable.
① What it is (30 seconds)
Prefix tree for strings — O(key length) lookup powers autocomplete, IP routing, and typeahead.
② How it works in system design
Each node is a character or edge label. Path from root spells prefix. Terminal node marks complete word. Compressed trie (DAWG) saves memory for static dictionaries.
Typical placement
Client→Edge / Gateway→Trie→Services→Data stores
③ Concrete system design example
Scenario: Google search typeahead: trie of popular queries per locale. User types "sys" → traverse to node → collect top completions by weight.
④ Important interview Q&A
| Question | Answer |
|---|---|
| Trie vs hash table? | Trie excels at prefix search; hash only exact key match. |
| Memory at scale? | DAWG compression, shard trie by first character, or backend Elasticsearch completion suggester. |
| Weighted trie? | Store frequency at terminal nodes; heap of top-K at prefix node for fast autocomplete. |
⑤ Seen in these system designs
- Typeahead — prefix completion
- Gmail Search — contact suggest
- Google Trends — query suggestions
In interviews, after explaining the concept, say: "This shows up directly in …" and link two designs.
⑥ Revision checklist
- Prefix traversal
- Top-K at node
- Memory compression
- vs inverted index prefix