Tries

1. When to reach for a trie

The question asks about prefixes over a fixed set of strings. Autocomplete, “does any word start with this,” “how many words share this stem.”

A dict can’t do it. Dict keys are opaque: {"car": 1} gives you no way to ask about “ca” without checking every key. The trie makes the prefix structure explicit by storing one character per level.

The alternative worth naming: keep the words in a sorted list and binary search for the prefix bounds. bisect_left(words, prefix) gives the first candidate and everything matching is contiguous after it. Simpler, and it’s O(log n + k) rather than O(len(prefix) + k). Fine unless the word set changes a lot.

2. It’s nested dicts

There’s no trie in the standard library, and you don’t need a class. Keys are edges, values are subtrees:

{
  'c': {
    'a': {
      'r': {'#': True,
            't': {'#': True}},
      't': {'#': True}
    }
  }
}

That’s car, cart, cat. In Java you’d write a Node class with a children map and a boolean; Python’s dict already is that, which is why the whole thing comes out in a dozen lines.

The '#' marker earns its place. Without it there’s no way to tell that car is a word rather than a waypoint on the path to cart. Any sentinel works as long as it can’t be a real character.

3. Insert

One path down, creating levels as you go. A loop, because insert never has to come back up.

def ingest(self, word):
    curr = self.root
    for char in word:
        if char not in curr:
            curr[char] = {}
        curr = curr[char]
    curr["#"] = True

curr is a moving pointer. It starts at the root and descends one level per character. self.root never gets reassigned; you’re mutating nested dicts through it.

The three-line create-or-descend can be one line with setdefault, which returns the existing value or inserts the default and returns that:

curr = curr.setdefault(char, {})

Shorter, and the name describes what it does to the dict rather than what it returns, which is the confusing part. Either version is fine.

4. Search

Two phases, and they need different tools.

Walk to the prefix node. A loop, one branch, and it has to handle the prefix not being there:

curr = self.root
for char in prefix:
    if char not in curr:
        return []
    curr = curr[char]

Collect everything below it. Recursion, because you don’t know the depth and you have to visit every branch and come back for the next one.

def collect(self, node):
    out = []
    if "#" in node:
        out.append("")
    for char in node:
        if char == "#":
            continue
        for suffix in self.collect(node[char]):
            out.append(char + suffix)
    return out

Each call returns the suffixes reachable from that node. "" is the empty suffix, meaning a word ends right here. Then suggest glues the prefix back on:

return [prefix + suffix for suffix in self.collect(curr)]

Why insert is a loop and collect is recursion: insert follows one path down with nothing to do on the way back, so there’s no stack. Collect visits every branch and has to resume where it left off, which is what a call stack is for. Same distinction as binary search vs tree traversal.

5. The whole thing

class Autocomplete:
    def __init__(self, words):
        self.root = {}
        for word in words:
            self.ingest(word)

    def ingest(self, word):
        curr = self.root
        for char in word:
            if char not in curr:
                curr[char] = {}
            curr = curr[char]
        curr["#"] = True

    def suggest(self, prefix):
        curr = self.root
        for char in prefix:
            if char not in curr:
                return []
            curr = curr[char]
        return [prefix + suffix for suffix in self.collect(curr)]

    def collect(self, node):
        out = []
        if "#" in node:
            out.append("")
        for char in node:
            if char == "#":
                continue
            for suffix in self.collect(node[char]):
                out.append(char + suffix)
        return out

Test cases that catch the real bugs:

a = Autocomplete(["car", "cart", "cat", "dog"])
a.suggest("ca")      # car, cart, cat   — a word that is also a prefix must appear
a.suggest("z")       # []               — missing prefix
a.suggest("cars")    # []               — prefix runs past the trie
a.suggest("")        # all four
Autocomplete([]).suggest("a")   # []

6. Splitting on segments instead of characters

Nothing says a level has to be one character. When the keys are structured paths — db.host, /docs/2026/report.txt — the natural unit is the segment, and the trie stores one node per section instead of one per letter.

The change is a single call: key.split(".") where the character version had for char in word. Everything else is identical.

It changes behaviour, not just efficiency. Under character-split, keys_with_prefix("d") matches db.host and database.url, because "d" is a character-prefix of both. Under segment-split it matches nothing, because no segment equals "d". Only whole segments count, which is what “everything under the db section” actually means.

The tree also comes out the right shape. db is one node with children host and port, so a section is a single node and any later operation on it — list it, delete it, sum its sizes — is one lookup. A character trie spreads db.host over seven nodes and represents the section boundary nowhere.

Say the assumption out loud when you pick it. Whether a prefix means a whole segment or any character run is exactly the kind of thing an interviewer either confirms or turns into the next part.

Storing a value at the terminal

The # marker doesn’t have to be a boolean. Put the payload there and the trie becomes a map rather than a set:

class Config:
    def __init__(self):
        self.paths = {}

    def set(self, key, value):
        node = self.paths
        for part in key.split("."):
            if part not in node:
                node[part] = {}
            node = node[part]
        node["#"] = value

    def get(self, key):
        node = self.paths
        for part in key.split("."):
            if part not in node:
                return None
            node = node[part]
        return node.get("#")

    def keys_with_prefix(self, prefix):
        node = self.paths
        if prefix != "":
            for part in prefix.split("."):
                if part not in node:
                    return []
                node = node[part]
        return self.collect(node, prefix)

    def collect(self, node, prefix):
        keys = []
        for part in node:
            if part == "#":
                keys.append(prefix)
            else:
                child = part if prefix == "" else prefix + "." + part
                keys.extend(self.collect(node[part], child))
        return keys

get returns node.get("#"), which is None both when the path was never set and when it exists only as a waypoint to a longer key. Those two cases are genuinely the same answer here, so one lookup covers both.

The collector builds the key on the way down

Note the difference from §4. There, collect returned suffixes and the caller glued the prefix back on. Here it carries the full key down as a parameter and returns finished keys, so the caller returns the result untouched.

The second version is worth preferring, and the reason is the bug the first one invites: the key gets assembled in two places, with two separator rules that have to agree. Change the collector to skip the leading separator and the caller’s concatenation silently produces a.b + c = a.bc. Each half reads as correct on its own, which is what makes it expensive to find.

One rule for the separator, applied in one place: no separator when there is nothing to its left.

7. Cost

• Insert: O(length of word)
• Walk to the prefix: O(length of prefix), independent of how many words exist
• Collect: proportional to the size of the output

The walk being independent of the word count is the whole reason the structure exists.

8. Mistakes

• Putting the terminal check in the caller instead of in collect. Then a word which is also a prefix gets found when you search for it exactly and missed when it sits under a shorter prefix. suggest("ca") drops car.
• Recursing into '#'. Its value is True, not a dict, so the loop crashes. Skip that key explicitly.
• curr = curr[char] with no guard, which raises KeyError instead of returning [] for a prefix that isn’t in the trie.
• Appending the whole list instead of one element inside the collect loop: out.append(char + suffixes) instead of char + suffix.
• Assembling the key in two places. If the collector builds part of it and the caller concatenates the rest, the two separator rules have to stay in agreement forever. Pass the prefix down and let the collector own the whole key.
• collect(node.left, node.right) — passing the second child where the second parameter goes. Two children means two separate calls.