Articles

Trie Interview Questions: Prefix Search, Wildcards, and Memory Trade-Offs

Prepare for trie interviews with prefix search, wildcard DFS, deletion, Unicode units, complexity proofs, memory layouts, and trade-offs.

Trie interview questions expose whether you distinguish a stored key from a path that merely exists. After inserting car and care, the node for car is terminal and also has a child; after inserting only care, car is a prefix but not a key. That one bit drives exact search, prefix queries, deletion, and autocomplete.

Princeton's TrieST technical documentation includes key insertion, lookup, keys with a prefix, keys matching a pattern, and longest-prefix queries. Its cost claims are expressed in characters examined under its alphabet model. Those facts describe the data structure, while the particular Python representation and memory choices here are editorial inference for interview use.

Trie Interview: Quick Answer

Each node stores a child mapping and a terminal flag or value. Insert and exact lookup follow one edge per symbol, so expected time is O(L) with hash-map children. Prefix search first reaches the prefix node, then enumerates its subtree; include output work rather than claiming only O(L). A single-character wildcard branches over every child at that depth, so worst-case work can approach the number of reachable trie states.

Deletion unsets the terminal marker and removes a node only when it is nonterminal and has no children. Choose the symbol unit—bytes, Unicode code points, or normalized user-visible text—before coding. Dense child arrays give fast direct indexing for a small fixed alphabet but waste space; maps, sorted vectors, compressed radix edges, and finite-state representations trade lookup cost, overhead, and mutability.

Define Three Different Queries

contains("car") asks whether the terminal marker is set. starts_with("car") asks only whether the path exists. complete("car") enumerates terminal descendants, perhaps with a limit and ranking. Do not implement all three by testing the same node condition.

State the empty-string contract. A trie can store an empty key by marking the root terminal, but an autocomplete product may reject it. Prefix "" can mean enumerate all keys, which may be unbounded. Add limit, pagination, or ranking to the API. If results must be lexicographic, an unordered child map requires sorting edges during enumeration or maintaining an ordered representation.

Implement Literal and Wildcard Search

END = "#"

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

def matches(root, pattern):
    def dfs(node, i):
        if i == len(pattern):
            return END in node
        ch = pattern[i]
        if ch == ".":
            return any(dfs(child, i + 1)
                       for edge, child in node.items()
                       if edge != END)
        return ch in node and dfs(node[ch], i + 1)
    return dfs(root, 0)

The DFS state is (node, pattern index). A literal advances through one named edge; . explores child nodes but never the terminal sentinel. Base success requires the pattern to be consumed and the current node to be terminal. Without that final test, ca. may incorrectly match the prefix of a longer key under a different contract.

Trace Wildcard Branching Honestly

Insert car, cat, care, and dog. Pattern c.t follows c, branches at the second position over only a, then branches at the third over r and t; both terminal children succeed. Pattern c.. also reaches car and cat, while c... reaches care. Pattern .. fails because the two-symbol nodes are not terminal.

A common complexity mistake says wildcard lookup is O(L). If every position is ., the search may visit many nodes. Bound it by the reachable subtree, often O(S) where S is visited states, plus output if returning all matches. Memoization helps only if the search graph can revisit the same (node,i) state; a plain trie with forward edges normally reaches each node at one depth once.

Delete without Damaging Shared Prefixes

To delete car while keeping care, unset car's terminal marker but preserve its child e. To delete care afterward, remove e when it becomes nonterminal and childless, then stop pruning at car if car is still stored. A recursive helper can return whether the current node is now safe to prune.

Duplicate insertion needs a contract. A set trie keeps one terminal bit; a multiset trie keeps terminal counts and perhaps subtree counts. Autocomplete ranking may keep frequency or top suggestions at each node, making inserts and deletes update every node on the path. Those caches improve query latency but increase write work and introduce another invariant: cached suggestions must be drawn from terminal descendants and respect the current rank version.

Account for Memory, Not Just Big-O Nodes

A map child field per character can dominate stored text when prefixes are not shared. A 26-pointer array avoids hashing but allocates 26 slots at every node, most of them empty. A sorted vector of (edge, child) pairs is compact for low degree and supports binary search; insertion may move elements. A ternary search tree stores three links per node and changes lookup comparisons.

Path compression merges single-child chains into labeled edges, producing a radix tree. It saves nodes but requires matching part of an edge and splitting it on insertion. Static dictionaries can use more compact automata that merge equivalent suffix states, while a mutable product may prefer simpler nodes. Give a measurement plan: node count, degree distribution, bytes per key, prefix query latency, update latency, and cache locality on representative keys.

Specify Unicode and Normalization

Python iteration sees Unicode code points, UTF-8 iteration sees bytes, and users perceive grapheme clusters. Case folding and normalization can change length and equality. Decide whether é in composed and decomposed forms is the same key, whether search is case-sensitive, and whether returned offsets refer to original or normalized input.

Normalize once at the API boundary and store either the canonical key plus display form or a mapping back to originals. Locale-sensitive case behavior may require product-specific rules. Do not claim a trie “supports Unicode” merely because the language string type does. The alphabet and equality relation affect memory, ordering, and what one wildcard matches.

Choose the Index from the Query Shape

Use a hash set for exact membership when prefix queries do not exist. Use a sorted array plus binary search to find a prefix range in a mostly static dictionary; it may be more compact and cache-friendly. Use a trie when many keys share prefixes, updates matter, or longest-prefix routing is central. Use a radix tree when node overhead is the issue.

Wildcards at arbitrary positions may suit an automaton, glob matcher, or regex engine more than naive trie DFS. Edit-distance autocomplete adds another dimension and often traverses trie nodes with a dynamic-programming row. Ranking by popularity requires a score index or cached top results, not only lexicographic edges. Name the required output and mutation pattern before choosing.

For URL routing, parameters and wildcards have precedence rules. A literal route should normally outrank :id, which outranks *rest; this is not ordinary dictionary autocomplete. Store edge types separately and reject ambiguous registrations or define deterministic priority. The trie is the traversal skeleton, while the router contract supplies semantics.

Make the Answer Reviewable

Turn the trie design into a small deterministic review before adding more scale. Write the initial state, five to ten timestamped inputs, every expected state transition, and the exact read result at two watermarks. Replay one input, deliver another out of order, pause one consumer, and rebuild the serving view from its durable boundary. The replay should not create an extra effect, the stale input should follow the declared version rule, and the rebuilt read should match the authoritative result through the same watermark.

Keep expected results independent of the implementation. If the same code produces both the output and the assertion, a shared assumption can hide the defect. Add one invariant check that scans all state, even if production serves a faster index. For a distributed design, say which part this fixture does not prove: it does not measure production latency, network partitions, or capacity. Load and fault tests come next, using the traffic and error budgets already stated.

Finish with an operational table: signal, healthy range, action, and user-visible consequence. Include ingestion or queue age, rejected or duplicate work, authoritative-versus-serving divergence, and tail read latency. This makes the proposal inspectable. An interviewer can now change one requirement and see exactly which state, test, and alert must change with it.

Separate what the review establishes from what it leaves open. A passing deterministic fixture proves the declared state transitions for those inputs. It does not establish performance at scale, fairness across real users, or behavior during every network failure. Add a capacity test for the estimated peak, a skew test concentrated on one key or partition, and a fault test at the acknowledgment boundary. Record versions and random seeds so failures can be replayed. When a result differs from expectation, reduce it to the smallest trace, name the violated invariant, and repair that transition before retuning capacity. This evidence-first sequence keeps correctness questions from being hidden inside infrastructure changes.

Keep the review artifact beside the implementation and date the environment that produced it. If a later optimization changes ordering, batching, numeric width, or retry behavior, rerun the same trace before accepting the new result. The invariant is the stable comparison point; the component diagram is not.

A 45-Minute Interview Structure

Spend four minutes on exact, prefix, wildcard, output-order, and mutation requirements. Use six for the node invariant and alphabet. Code insert and exact lookup in eight, wildcard search in ten, and deletion in six. Spend seven minutes on complexity including output and branching. Use five for memory alternatives and Unicode. Keep car, care, and cat visible; they expose terminal, shared-prefix, wildcard, and deletion behavior in one trace.

Final Takeaway

A trie answer is complete when paths, stored keys, and outputs are distinct. Follow one edge per literal symbol, branch explicitly for wildcards, prune only dead nonterminal nodes, and include visited states plus output in complexity. Then choose a child representation and normalization rule that match the alphabet, update rate, and memory budget rather than assuming one node layout is universally efficient.

Sources and Further Reading

Documentation supports the stated system or algorithm behavior; individual question records support only their own practice contracts. Architecture recommendations and interview sequencing are editorial inference.