Trie Coding Problems: 27 Questions with Solutions
27 trie coding problems — 1 easy · 16 medium · 10 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 7-day plan.
- Problems: 27
- By difficulty: 1 easy · 16 medium · 10 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
A trie, or prefix tree, stores a set of words one character per level, so words that share a prefix share the path that spells it. Asking whether any stored word starts with a given prefix, or which stored word is the shortest prefix of another, then costs the length of the word rather than the size of the dictionary. The same tree built over the bits of integers, highest bit first, answers maximum-XOR questions greedily. The problems here practise building the tree, marking where words end, and walking it alongside a second string.
New to trie? Read the Trie (Prefix Tree) tutorial first.
How trie works, step by step
insert "car", "cat", "cart", "dog"; find words starting with "ca"- A trie stores words letter by letter along paths from the root, so words with the same beginning share their first nodes. Each node also records whether a word ends there, because a word can be the prefix of a longer one.
- Insert "car": the trie is empty, so c, a and r become a chain of new nodes from the root, and r is marked as the end of a word.
- Insert "cat": the walk reuses c and a from "car", since they share the prefix "ca", then adds t and marks it as the end of a word.
- Insert "cart": c, a and r already exist, because "car" is a prefix of "cart", so only t is new, hung below r. r keeps its own end mark, so "car" and "cart" are both words.
- Insert "dog": no stored word starts with d, so d, o and g are all new, a separate branch from the root, and g is marked as an end. A trie only shares what words really have in common.
- To find the words starting with "ca", walk from the root: c, then a, 2 steps however many words are stored. That node has no end mark, so "ca" is not a word itself, but everything below it starts with "ca".
- Collecting every end mark below that node gives "car", "cart" and "cat", and the "d" branch is never touched. Inserting or walking a word of length L costs O(L); listing the matches costs the size of that one subtree.
Trie study plan
11 of the 27 Trie problems (1 easy, 7 medium and 3 hard) over 7 days, about 7 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 16 in the full list below are practice at your own pace. Then move on to Backtracking.
Day 1
Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.
- Maximum Strong Pair XOR I Easy
- Replace Words Medium
Day 2
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 3
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
- Word Break Medium
- Short Encoding of Words Medium
Day 4
More mediums. Before coding each one, write down what state the pattern keeps and when it changes.
Day 5
Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.
Day 6
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
Day 7
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
- Concatenated Words Hard
Trie: the essentials
When to reach for it
Many words and questions about their prefixes: does any stored word start with this, which root is the shortest prefix of this word, is every prefix of a word also a word. A whole-word lookup is a Hash Table job. Built over bits, highest first, a trie also finds the largest XOR of two numbers.
The pattern
Each node maps a character to a child and flags where a word ends. Insert walks the word, creating missing children, and flags the last node; search walks the same way and fails at the first missing child. Every node passed spells a prefix of the word, so the first flagged one is its shortest stored prefix.
def insert(trie, word):
node = trie
for ch in word:
node = node.setdefault(ch, {}) # the child, created if missing
node["$"] = True # a word ends here
def shortest_root(trie, word): # shortest stored prefix, or None
node = trie
for i, ch in enumerate(word):
node = node.get(ch, {}) # {} once the path runs out
if "$" in node: return word[:i + 1]
return None
Cost
O(L) per insert or search for a word of length L, however many words are stored, and at most one node per character inserted. A 26-slot array per node is faster than a dictionary and far larger.
Common mistakes
- Taking a path for a word: "app" lies on the path of "apple" but is stored only if its node is flagged.
- Checking the flag only at the end of the word, which misses every shorter root.
- 26-slot arrays for 10⁵ words of length 100: up to 2.6 × 10⁸ slots.
- Building a bit trie lowest bit first, when the highest differing bit decides an XOR.
Start with
- Replace Words: the shortest stored prefix of each word.
- Longest Word in Dictionary: a word whose every prefix is flagged.
- Maximum XOR of Two Numbers in an Array: a trie over bits, greedy from the top.
All trie problems
Easy (1)
- Maximum Strong Pair XOR I Bit Manipulation, Array
Medium (16)
- Map Sum Pairs Hash Table, String, Design
- Implement Magic Dictionary Hash Table, String, Depth-First Search
- Design Add and Search Words Data Structure String, Depth-First Search, Design
- Implement Trie (Prefix Tree) Hash Table, String, Design
- Partition String Hash Table, String, Simulation
- Find the Length of the Longest Common Prefix Array, Hash Table, String
- Shortest Uncommon Substring in an Array Array, Hash Table, String
- Remove Sub-Folders from the Filesystem Array, String, Depth-First Search
- Lexicographical Numbers Depth-First Search
- Extra Characters in a String String, Hash Table, Dynamic Programming
- K Divisible Elements Subarrays Array, Hash Table, Enumeration
- Short Encoding of Words String, Hash Table
- Replace Words String, Hash Table
- Longest Word in Dictionary String, Hash Table
- Maximum XOR of Two Numbers in an Array Array, Hash Table, Bit Manipulation
- Word Break String, Dynamic Programming, Hash Table
Hard (10)
- Prefix and Suffix Search Array, Hash Table, String
- Word Search II String, Backtracking, Matrix
- Count Prefix and Suffix Pairs II Array, String, Rolling Hash
- Maximum Strong Pair XOR II Array, Bit Manipulation, Sliding Window
- Maximum XOR With an Element From Array Array, Bit Manipulation, Sorting
- Count Pairs With XOR in a Range Array, Bit Manipulation
- Palindrome Pairs Array, Hash Table, String
- Concatenated Words String, Dynamic Programming, Depth-First Search
- Distinct Echo Substrings String, Rolling Hash, Hash Table
- Sum of Prefix Scores of Strings Array, String, Counting
Companies that ask trie problems
- Amazon 24 problems on trie
- Google 24 problems on trie
- Meta 5 problems on trie
- Adobe 4 problems on trie
- Microsoft 3 problems on trie
- Airbnb 2 problems on trie
- Yahoo 2 problems on trie
- Bloomberg 1 problem on trie
- Capital One 1 problem on trie
- Directi 1 problem on trie
- Hulu 1 problem on trie
- Intuit 1 problem on trie
Next topic: Backtracking