Vibe Engines Learn
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
  1. A node is just a map from a character to a child node. The root is an empty node.
  2. 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).
  3. search and startsWith both walk the characters; if a character is missing, the answer is False.
  4. The only difference: search additionally requires the final node to be an end-of-word; startsWith does not.
CPython · WebAssembly

Explore the topic

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

Algorithms & DSA