Implement Trie (Prefix Tree)
Problem
Design a data structure Trie supporting three operations: insert(word) adds a word, search(word) returns true if the exact word was previously inserted, and startsWith(prefix) returns true if any inserted word begins with prefix. All strings consist of lowercase English letters. The structure will receive up to 3·10^4 mixed operations.
- 1 ≤ word.length, prefix.length ≤ 2000
- total operations ≤ 3·10^4
- lowercase a–z only
What this tests
- Choosing a structure whose cost depends on key length, not the number of keys
- Distinguishing "is a word" from "is a prefix" with a terminal flag
- Node representation trade-offs (array of 26 vs hash map)
- Clear API design and complexity per operation
- Talking through memory usage honestly
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
delete(word)."a.c" where . matches any letter.