L3 · FAANGData-structure design~18 min · 4 tests

Implement a Trie (Prefix Tree)

Build a Trie with insert, search and starts_with in O(L) per operation using nested dicts, the data structure behind autocomplete. FAANG design question.

The problem

Implement Trie:

insert(word)
search(word) → True if the exact word was inserted
starts_with(prefix) → True if any inserted word starts with prefix

Examples

Example 1

Input

run_ops(Trie, [], [["insert", "apple"], ["search", "apple"], ["search", "app"], ["starts_with", "app"], ["insert", "app"], ["search", "app"]])

Expected output

[None, True, False, True, None, True]

+ 3 hidden tests on Submit — empty trie, the end marker must not collide with letters.

Edge cases to ask about

Prefix that is also a word
Empty prefix
Special characters

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · Trie

class Trie:
    def __init__(self):
        pass

    def insert(self, word):
        pass

    def search(self, word):
        pass

    def starts_with(self, prefix):
        pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and read why.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
Set of words	O(L) search, O(N·L) prefix	O(N·L)	Prefix queries scan every word.
bestTrie of nested dicts	O(L) every operation	O(total characters)	Shared prefixes are stored once.

Walkthrough of the optimal approach (try it yourself first)

Each node is a dict from character to child. insert walks and creates nodes; an end marker records that a complete word stops here. search needs the walk to succeed and the end marker; starts_with only needs the walk.

The end marker must be a key that no character can be. The hidden test inserts "a$b": a "$" marker would make search("a") wrongly return True. None (or an is_end flag on a small Node class) cannot collide.

Tries win when you need prefix queries: autocomplete, spell-check, IP routing tables.

Complexity: O(L) time, O(total characters) space. Each operation walks one node per character of its argument; storage is one node per distinct prefix.

Reveal the reference solution

class Trie:
    END = None        # a key no character can ever be

    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node[self.END] = True

    def _walk(self, text):
        node = self.root
        for ch in text:
            if ch not in node:
                return None
            node = node[ch]
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and self.END in node

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

The brute force, for comparison

class Trie:
    def __init__(self):
        self.words = set()

    def insert(self, word):
        self.words.add(word)

    def search(self, word):
        return word in self.words

    def starts_with(self, prefix):
        return any(w.startswith(prefix) for w in self.words)     # O(N · L)

Follow-ups interviewers ask

Return the top 3 autocomplete suggestions for a prefix.
Delete a word.

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Implement a Trie (Prefix Tree) in Python?

The optimal solution runs in O(L) time and O(total characters) auxiliary space. Each operation walks one node per character of its argument; storage is one node per distinct prefix.

What is the brute-force approach, and how do you optimise it?

Set of words: O(L) search, O(N·L) prefix time, O(N·L) space. Prefix queries scan every word. Trie of nested dicts: O(L) every operation time, O(total characters) space. Shared prefixes are stored once.

What follow-up questions do interviewers ask about Implement a Trie (Prefix Tree)?

Return the top 3 autocomplete suggestions for a prefix. Delete a word.