Trie
Track: Data structures. 6 stages. Languages: Go, Python, JavaScript, Rust.
Build a tree that stores whole words one letter at a time, one letter per step down. People use this shape for autocomplete and dictionary lookup, because looking up a word only costs as many steps as the word has letters, not how many words you stored. Implement New() (starts empty), Insert(word), Search(word) -> bool (true only if that exact word was inserted), and StartsWith(prefix) -> bool (true if any inserted word starts with this prefix), using your language's names. The tricky part is keeping two things separate: "this exact word was stored" and "some stored word starts with this". Inserting "car" must not make "ca" count as a stored word. Inserting "card" later must not make "car" stop being one. Words are lowercase letters a to z only, 1 to 12 letters long. You will never see an empty word. Use only the standard library. Build the tree yourself. Your tree receives one call at a time. For help with the ideas, read the notes.
Where it is used
- The Linux kernel finds the route for an IPv4 address with a compressed trie (
fib_trie), looking for the longest matching prefix. - httprouter, a Go web router, matches URL paths with a compressed trie, because many paths start the same way, like
/api/users/. - Redis Streams are stored in a radix tree, a trie that merges chains of single letters into one node.
- Search boxes use a trie to suggest words that start with what you have typed so far.
Stages
tr1: hello: add one word, find it (very easy)
Insert one word, then search for it. Example: Insert("apple"), then Search("apple") -> true.
The tester will verify: a word you inserted is found by Search.
tr2: words that exist and words that don't (easy)
Search must say yes only for a word you inserted in full. If a word is only the start of something you inserted, that doesn't make it inserted on its own, so Search for it must say no.
insert "apple"
insert "app"
a - p - p - l - e ("app" ends here too, two steps in)Example: Insert("apple"), Insert("app"), then Search("apple") -> true, Search("ap") -> false, Search("app") -> true.
The tester will verify: Search is true only for full words you inserted, never for something that is merely the start of one.
tr3: StartsWith matches real prefixes (medium)
StartsWith must say yes for the start of any inserted word, even when that start was never inserted as a word on its own. Example: Insert("apple"), Insert("application"), then StartsWith("appl") -> true, StartsWith("app") -> true, StartsWith("b") -> false.
The tester will verify: StartsWith is true for every prefix of every inserted word, including the full word itself, and false for anything else.
tr4: mixed words, no wrong answers (medium)
Insert words that share letters along the same path, such as "cat", "car", and "card", then check both Search and StartsWith on them. Each word's own ending must be marked on its own, without losing the other words that share the same letters.
insert "cat", "car", "card"
c - a - t
\
r - d ("car" ends at r, "card" continues one more step)Example: after inserting "cat", "car", "card": Search("car") -> true, StartsWith("ca") -> true, StartsWith("care") -> false, Search("ca") -> false.
The tester will verify: every Search and StartsWith answer is right on a set of words that share letters, with no wrong yes and no wrong no.
tr5: many words and many checks (hard)
Insert a batch of words, then run hundreds of Search and StartsWith calls mixed together, drawn from a small set of letters on purpose, so words and prefixes overlap a lot.
The tester will verify: every answer across the whole run matches our solution, with zero wrong answers.
tr6: search speed (L2, hard)
Keep Search and StartsWith fast even when your tree holds many thousands of words. Keep every answer correct too. Example: if our solution takes 100 ms, the limit is 150 ms. Your solution takes 140 ms, so it passes.
The tester will verify: your code takes at most 1.5 times as long as our solution in the same language, and every answer stays correct. How many memory allocations you use is also shown, but it never decides a pass or a fail.
Rules
- Standard library only. Build the tree yourself.
- Your answers must be the same every time for the same sequence of calls.