CODING CHALLENGE · N°35

Implement a Trie

Medium TrieStringsDesign

The prefix tree behind autocomplete, spell-check and IP routing: a tree keyed by characters that answers "is this a word?" and "is this a prefix?" in time proportional to the word length. Replay insert/search/startsWith operations. Solve it in Python or TypeScript, with hidden tests.

The problem

Implement a trie (prefix tree) supporting insert(word), search(word) (is the exact word stored?), and startsWith(prefix) (is any stored word prefixed by this?). You are given a list of ops like ["insert","apple"], ["search","app"], ["startsWith","app"]. Return the list of boolean outputs from every search and startsWith, in order.

EXAMPLE 1

Input ops = [["insert","apple"],["search","apple"],["search","app"],["startsWith","app"],["insert","app"],["search","app"]]

Output [True, False, True, True]

"app" is a prefix before it is inserted as a word; searching it becomes True only after insertion

CONSTRAINTS

Words and prefixes are lowercase letters.
Each operation should run in O(length of the string), independent of how many words are stored.
search requires the full word to be marked as an end-of-word; startsWith only requires the path to exist.

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement trie_ops(ops): build a trie of nested nodes (one child per character) with an end-of-word marker. Collect the boolean result of each search/startsWith.

HINTS — 4 IDEAS

A node is just a map from a character to a child node. The root is an empty node.
To insert, walk/create a child per character, then mark the final node as end-of-word (e.g. a boolean flag or a sentinel key).
search and startsWith both walk the characters; if a character is missing, the answer is False.
The only difference: search additionally requires the final node to be an end-of-word; startsWith does not.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Each node holds a map from a character to a child node, plus an end-of-word flag. insert walks the string, creating child nodes as needed, and marks the final node as a word end. search walks the path and returns true only if it exists and the last node has the end flag. startsWith walks the same path but only checks that it exists.

Complexity

Time O(L) per operation in the key length L; space O(total characters across all inserted keys).

Common mistakes

Not distinguishing “is a complete word” from “is a prefix” — that is exactly what the end-of-word flag is for.
Conflating search (needs the end flag) with startsWith (path existence only).
Assuming a fixed 26-letter array when the alphabet is larger — a hash map of children is more general.

Where this shows up

Tries power autocomplete and typeahead, spell-checkers, IP routing (longest-prefix match), and dictionary lookups — anywhere you query by prefix, which a hash map fundamentally cannot do because it scatters keys with no shared structure.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA