Implement Trie

Interview Problem Advanced Medium Hash Map Trie

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Trie with insert(word), search(word), and startsWith(prefix) for lowercase strings.

Starter code

class Trie:
    def __init__(self):
        pass

Test cases

word-versus-prefix

{
  "operations": [
    "Trie",
    "insert",
    "search",
    "search",
    "startsWith",
    "insert",
    "search"
  ],
  "arguments": [
    [],
    [
      "apple"
    ],
    [
      "apple"
    ],
    [
      "app"
    ],
    [
      "app"
    ],
    [
      "app"
    ],
    [
      "app"
    ]
  ]
}

Expected: [null,null,true,false,true,null,true]

Wizard outline

Step 1: Initialize Trie
Replace the empty starter with the first real state owned by Trie. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Assemble the primary transition
Extend the initialized state with the next contiguous part of the popular solution. The transition explains how one input element or operation changes the state; boundaries are easier to reason about after this invariant is visible.
Step 3: Pass the Wizard Stateful Trie Prefix case
Complete the readable core algorithm for one representative Interview case. Prefix existence depends only on reaching the final edge, not on a complete-word marker.
Step 4: Harden the Wizard Stateful Trie Word Versus Prefix boundary
Repair the reviewed boundary and pass the complete submission contract. The marker separates a complete inserted word from the same path used only as a prefix.

Footguns and prerequisites

A path existing for a prefix does not prove that prefix was inserted as a complete word.
strings
dictionaries and sets

Reviewed references

LeetCode 208 — Implement Trie

Practice prerequisites

Follow Trie Edges(opens in a new tab)
Follow Trie Edges isolates after matching k characters, node is the trie node reached by exactly query[:k]; the first missing edge ends the match. That focused state discipline is required when implementing implement trie as a complete Interview Problem.

Recommended approach and implementation

Represent each node as a dictionary and reserve a terminal key. Insert creates paths, search requires terminal at path end, and startsWith requires only the path.

Why it works: Every inserted word creates exactly its character path and terminal marker. Traversal succeeds exactly for stored prefixes, while the terminal check distinguishes complete inserted words.

class Trie:
    """
    Checkpoint 1: initialize the state owned by this Interview contract.
    Checkpoint 2: assemble the primary transition without hiding the boundary.
    """
    def __init__(self):
        self.root = {}
        self.end = '$'
    def insert(self, word):
        node = self.root
        for character in word:
            node = node.setdefault(character, {})
        node[self.end] = True
    def _find(self, text):
        node = self.root
        for character in text:
            if character not in node:
                return None
            node = node[character]
        return node
    def search(self, word):
        node = self._find(word)
        return node is not None and self.end in node
    def startsWith(self, prefix):
        return self._find(prefix) is not None

Similar exercises

Wildcard Word Dictionary(opens in a new tab)