</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

Trie Design

What is this?

A trie is a filing cabinet where the drawers are letters. To file card you open drawer c, then a, then r, then d, and mark that last drawer "a word ends here". Everything beginning car shares the first three drawers, which is why the structure is compact and why asking "is there anything filed under car?" takes three steps regardless of how many words exist.

This chapter builds that, then stretches it twice: once by allowing a wildcard in the query, and once by noticing that the drawers do not have to be letters.

Trie node anatomy: children and is_end enabling search, wildcards, filesystems

Fun fact: Design In-Memory File System is a trie in disguise, and seeing that collapses it from a fiddly design problem into about twenty lines. A path is a list of components, a directory is a node whose children are its entries, and a file is a node carrying content instead of children. ls then becomes "return this node's children, sorted". The problem states the sorting requirement, so sorting on read (or keeping an ordered map) is a deliberate choice worth mentioning.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.


The idea: a node holds a map from label to child plus a flag saying whether a key ends here. Exact lookup follows one label per step; a wildcard follows all of them; and the labels can be any unit you like.


1. The structure

class Node:
    def __init__(self):
        self.children = {}      # label -> Node
        self.is_end = False     # a complete key finishes here

def insert(root, word):
    node = root
    for ch in word:
        node = node.children.setdefault(ch, Node())
    node.is_end = True

is_end is not optional. Without it a trie containing card would report car as present, because the path exists. The flag is what separates "a key ends here" from "a key passes through here".

2. Wildcards mean branching

def search(node, word, i):
    if i == len(word):
        return node.is_end
    ch = word[i]
    if ch == '.':
        return any(search(child, word, i + 1) for child in node.children.values())
    return ch in node.children and search(node.children[ch], word, i + 1)

A concrete character narrows to one child; a . must try them all. That is why the cost is O(26^d · L) for d wildcards, since each dot multiplies the branching. A query of all dots explores every path of the right length, which is worth stating when the interviewer asks about complexity. With no dots the search is a single O(L) walk.

3. The labels need not be characters

For a filesystem, split the path and use the components:

def resolve(root, path):
    node = root
    for part in path.split('/'):
        if part:                                   # skip the empty leading segment
            node = node.children.setdefault(part, Node())
    return node

mkdir is resolve and stop. addContentToFile is resolve then append to that node's content. ls is: resolve, and if the node is a file return its own name, otherwise return its children's names sorted. The whole API is three lines of trie walking plus that one branch.


4. A 30-second worked example

Insert cat, car, card; then query c.r:

Worked example: search 'c.r' over a trie of cat, car, card

Three words, five nodes below the root: the shared prefix ca is stored once. And note search("ca") returns False despite that path existing, because no key ends there.


5. Where you'll actually meet this

  • Autocomplete. Each keystroke descends one node; the subtree below is the candidate set.
  • Pattern lookups with blanks. Crossword and word-game helpers match patterns like .a.e, which is the . branch.
  • Filesystems and object stores. Path hierarchies, and prefix-based listing APIs.

6. Problems in this chapter

Add and Search Word

Support adding words and searching with . matching any single character. Exact characters descend; wildcards branch to every child.
Pattern: trie with DFS on wildcards. Target: O(L) add, O(26^d · L) search.

Design In-Memory File System

Implement ls, mkdir, addContentToFile and readContentFromFile. A trie over path components, where files carry content and directories carry children.
Pattern: trie with non-character labels. Target: O(D) per operation for a path of D components, plus O(c log c) to sort the c children in ls.

Longest Word in Dictionary

Find the longest word in a list whose every prefix is also in the list, smallest alphabetically on ties. Insert everything, then walk the trie only through nodes marked as complete words.
Pattern: trie walk restricted to is_end nodes. Target: O(L) for L total characters.


7. Common pitfalls

  • Omitting is_end. Every prefix of a stored word would report as present.
  • Treating a wildcard as a single wrong guess. It must try every child, which means recursion rather than iteration.
  • Not handling the empty path segment. Splitting "/a/b" yields a leading empty string that must be skipped.
  • Returning unsorted ls output. The problem requires lexicographic order; decide whether to sort on write or on read.
  • Confusing a file with a directory. ls on a file returns the file's own name, not its (nonexistent) children.
  • A 26-slot array for path components. Fine for lowercase letters, useless for arbitrary names, so use a dictionary.
  • Recursing per character on a very long word. Deep tries can exhaust the stack; iterate for exact search and recurse only for wildcards.
  • Descending through non-words. In Longest Word in Dictionary, only nodes with is_end set may be walked through; skipping that check accepts words with a missing prefix.

8. Key takeaways

  1. A node is children plus an end-flag. The flag is what makes membership different from prefix existence.
  2. Exact search narrows; wildcards branch. That difference is the whole cost model.
  3. Labels can be anything: characters, path components, bits.
  4. A filesystem is a trie, and recognising that turns a design question into a walk.
  5. Sorted listing is a stated requirement, so choose where to pay for it.
  6. Dictionaries beat fixed arrays for anything but a small known alphabet.
  7. Why interviewers like it: the structure takes five minutes, leaving the whole interview for the extensions: wildcards, deletion, sorted listing, memory trade-offs.

Order: Add and Search Word (Wildcard) → Design In-Memory File System → Longest Word in Dictionary.

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.