Topic 12 of 20
Tries
Prefix trees for autocomplete, dictionary search and bitwise XOR tricks.
The concept
A trie (prefix tree) stores strings character by character, so all words that share a prefix share a path from the root. Inserting or searching a word of length L costs O(L), no matter how many words are stored, and "does any word start with this prefix?" is answered by simply walking down the tree. That makes tries the natural structure for autocomplete, spell-checking and dictionary problems.
Each node typically holds a map (or a fixed array of 26) of children plus an isEnd flag. Beyond basic insert and search, the interview patterns are: wildcard search (DFS over all children when you see a '.'), trie + backtracking (search a whole board for many words at once, pruning as soon as a prefix is missing), and the bitwise trie, which stores numbers bit by bit to find the maximum XOR pair in O(n · 32).
This is a short topic, but tries show up regularly at Google, Amazon and Microsoft, often as the optimisation that turns a timed-out brute force into an accepted solution.
Patterns you will learn
Problems, in order
- 1
Build the data structure from scratch; asked verbatim in interviews.
Prefix TreeReported at: AmazonGoogleMicrosoft+6 - 2
Wildcard search with DFS over children.
- 3
- 4
Building words one letter at a time through the trie.
Trie + DFSReported at: Google - 5Map Sum PairsMedium
Storing aggregate values on trie nodes.
Prefix Tree with AggregatesReported at: Google - 6
DFS that allows exactly one mismatch.
Trie + DFS (One Mismatch)Reported at: MetaGoogle - 7
Autocomplete, the textbook trie application.
Prefix Tree / Sort + Binary SearchReported at: AmazonGoogleMeta+3 - 8
The bitwise trie for greedy XOR maximisation.
Bitwise TrieReported at: BloombergAdobe - 9Word Search IIHard
Trie-pruned grid backtracking; a top Hard at Google and Amazon.
Trie + BacktrackingReported at: AmazonMicrosoftGoogle+6 - 10Palindrome PairsHard
Prefix and suffix reasoning across a word list.
Trie / Hash Map of Reversed WordsReported at: GoogleAppleMeta+2