← All patterns
Trie (Prefix Tree)
A tree where each path from root represents a string prefix, enabling fast prefix search/autocomplete.
When to use it
- Autocomplete, prefix matching, word search dictionaries, IP routing (longest prefix match).
Signals in the problem statement
- Repeated prefix queries on a large set of strings.
Common pitfalls
- Using a hash set/list for prefix queries — technically works but is far slower than a trie for large prefix-heavy workloads (a common 'why not just use a HashSet' probe).
Practice Problems
Implement Trie (Prefix Tree)
MediumAsked at: Amazon, Google, Microsoft, Meta
Implement a trie with insert, search, and startsWith methods.
Time: O(L) per op, L=word length · Space: O(total chars inserted)
Word Search II
HardAsked at: Amazon, Google, Meta, Uber
Given a 2D board and a list of words, find all words in the board (same rules as Word Search: sequential adjacency).
Time: O(m*n * 4^L), pruning helps significantly · Space: O(total chars in words)