Skip to content
Tech Interview Prep
Technical interview guide

Tries

A tree specialized for prefix operations over strings: each edge is a character, each path from the root is a prefix.

Read
40 min
Practice MCQs
25
Interview Q&A
25
Edition
v7
Editorial status
Reviewed

Scope: Language-neutral, with container comparisons cited from CPython 3.14 and java.util as of Java 21.

Curated: · Written: · Reviewed:

25 questions

MCQ-3A trie stores the keys 'app' and 'apple'. Each node carries a boolean flag that is set when an inserted key ends at that node; search walks the trie one character per step and returns True only if it consumes the whole query and the node it lands on has that flag set. A test calls search on 'app', 'ap', 'apple', and 'apps'. Which set of results does the test produce?
MCQ-4A trie is built by inserting exactly these keys: `"car"`, `"cart"`, `"cat"`. The `search` method is: ```python def search(self, word): node = self.root for ch in word: node = node.children.get(ch) if node is None: return False return True # line Y ``` A test asserts `search("ca") == False`, but it returns `True`. `search("car")` returns `True`, and `starts_with("ca")` returns `True`. Which change makes `search("ca")` return `False` while leaving `starts_with` unchanged?
MCQ-9A radix tree is built by inserting three keys in this order: "test", then "team", then "toast". The root counts as a node. How many nodes does the tree contain after all three insertions?
MCQ-16A trie holds the keys {"app", "apple", "ap"}. Deleting "app" must leave "ap" and "apple" findable and must not leave unreachable nodes behind. Which note about trie deletion is the one to keep?
MCQ-15A trie holds the keys 'she', 'shell' and 'shore'. A recursive delete removes 'she' by clearing the value at its terminal node, then frees nodes on the post-order unwind. Which condition on a node being unwound keeps the remaining keys reachable?
MCQ-24A trie backs an autocomplete service. Each node holds a `children` map and a `terminal` flag; `delete(key)` clears the flag on the key's last node, then walks back toward the root removing every node that has no children. The suite inserts 2,000 eight-letter words, asserts `search` for each, deletes 1,000 of them, and asserts `search` is False for the deleted words and True for the rest: all green. In production, a user removes the saved word `cart` and autocomplete stops offering `car`, which is still saved. Which added test case reproduces the production failure?
MCQ-6A ranked-autocomplete trie stores at every node the maximum score in its subtree. It currently holds four entries: car=60, cart=80, cat=30, dog=100. The entry cave=90 is inserted. Which nodes that already existed before the insertion have their stored maximum changed?
MCQ-22A router keeps its IPv4 forwarding table in a bit trie: each node may store a next hop for the prefix ending at that node. The table holds these entries: | Prefix | Next hop | |---|---| | 0.0.0.0/0 | Z | | 10.0.0.0/8 | A | | 10.1.0.0/16 | B | | 10.1.2.0/24 | C | | 10.1.2.128/25 | D | A packet arrives for 10.1.2.5. Which next hop does the lookup return?
MCQ-13A service answers max-XOR queries over 32-bit unsigned integers with a binary trie that walks bits 31 down to 0. To keep node indices non-negative, an engineer changes it to mask every key with 0x7FFFFFFF before insertion and walk bits 30 down to 0. The trie holds {0x80000000, 0x40000000}. A query for 0x7FFFFFFF returns which value?
MCQ-12An Aho–Corasick automaton is built over the dictionary {ab, bab, bc}. Its trie has edges root→a→ab, root→b, b→ba→bab and b→bc, and failure links have been computed for every node. The scanner is at the node for 'bab' and the next input character is 'c'. Which node does the automaton move to?
MCQ-14A team must answer 'does pattern P occur in text T' queries against a 1,000,000-character text, and the index has to fit in a 64 MB memory budget. Which index meets the budget?
MCQ-11A dictionary service matches words in a trie (26 lowercase children per node, 500,000 words) against patterns where '.' matches any single character. Exact and prefix lookups run at p99 = 1.2 ms; a pattern with one '.' runs at 4 ms; a pattern with three '.' runs at 2.6 s. Which explanation fits these numbers?
MCQ-18A trie over lowercase keys (a–z) stores each node as a fixed array of 26 child pointers. Exact search of a 10-character key takes about 200 ns. A wildcard query with two '.' positions over the same key set takes about 140 µs: far above the few hundred nanoseconds the team expected. Which explanation accounts for the gap?
MCQ-8When profiling an in-memory dictionary storing millions of strings, an engineer notices a standard R-way trie consumes several times more RAM than a flat string array or hash set. What structural mechanism primarily accounts for this memory overhead?
MCQ-10A gateway rejects request paths that begin with any of 50,000 prohibited prefixes. In a benchmark on this workload, paths average 140 bytes and the longest prohibited prefix is 12 bytes; trie lookups for non-matching paths are measurably faster than a chained hash table holding the same prefixes. Which mechanism accounts for the gap?
MCQ-2A gateway looks up 12-character session tokens in an in-memory trie at 240 ns per lookup; the same tokens in a hash map take 60 ns. The design doc notes the trie is O(k) and the map is O(1), so the 4x gap should widen as tokens get longer. The tokens are lengthened to 24 characters. What happens to the two lookup times?
MCQ-25A session store holds 5 million keys, each a 36-character UUID (hex digits and dashes). Every read is an exact lookup of the full key; no query asks for keys sharing a prefix, and keys are never iterated in sorted order. A teammate proposes replacing the hash map with a trie to speed up lookups. What does the analysis show?
MCQ-5An autocomplete box queries a trie holding 500,000 words of 8 characters on average. Profiling shows every keystroke performs about 500,000 key comparisons (identical for 'zyg' (3 completions) and 'th' (12,000)) with p99 at 180 ms. The UI renders at most 10 suggestions, and the service has a 200 MB memory budget with the trie already using 150 MB. Which change removes the prefix-independent cost?
MCQ-17A service indexes 10M keys of average length 40 bytes and answers 'how many stored keys start with prefix P' at 5k QPS, with exact counts. Keys are added and removed continuously, and each mutation must stay O(k) in key length. Which design do you document?
MCQ-1A search team indexes 2,000,000 product names (average 12 characters, lowercase a–z) in a trie to serve prefix suggestions. Each node holds a fixed 26-element array of child pointers (8 bytes each) plus a 1-byte end-of-key flag. The trie has 21,000,000 nodes and occupies about 4.4 GB, far more than the team budgeted. Prefix queries must stay O(prefix length). Which change addresses the dominant cause of the memory use?
MCQ-7A trie indexes 2,000,000 nodes over lowercase ASCII keys (26 symbols). Each node carries 16 bytes of non-child fields. The trie must fit a 200 MB budget, and a node's children must be enumerable in lexicographic order without sorting at query time, because the trie backs an autocomplete prefix listing. The average node has 1.4 children. Which child representation should the team use?
MCQ-21A service keeps a 2-million-key trie (average key length 12) as a read-mostly index. It serves 400,000 lookups/s from 32 reader threads and 3,000 inserts/s from 4 writer threads. Every operation takes one mutex on the root; each insert holds it for about 200 µs, and profiling shows readers spend 60% of their wall time waiting on that mutex, with p99 lookup latency at 9 ms. 70% of lookups hit keys that begin with 's'. Which change removes the reader wait?
MCQ-19An index service builds a trie over 12 million merchant-supplied product names. The insert path keys each name with `unicodedata.normalize('NFC', name).casefold()`; the lookup path keys the query with `query.lower()`. Searching for the exact name shown on the product page, `Straße`, returns 0 results, while `STRASSE` returns the product. What is the cause, and what fixes it?
MCQ-20An autocomplete service serves from an in-memory trie that it rebuilds at process start from 20 million query strings, average length 22 characters, which share prefixes down to about 260 million nodes. A deploy must be serving within 30 s of process start. On one thread the build measures 2 us per key (22 node steps at roughly 90 ns each, cache misses included) and shards cleanly across 8 worker threads. Today the service also writes a snapshot of its in-memory node records, 24 bytes each, and memory-maps it; the file is 6.2 GB, and this month's node-struct change made every existing snapshot unreadable. Which restart plan should they ship?
MCQ-23A suffix-matching service holds 2,000,000 domain suffixes (average 12 characters, about 8,000,000 trie nodes after prefix sharing) and answers 200,000 longest-suffix queries per second from four replicas behind a load balancer. The trie is built from node objects at roughly 64 bytes per node. Each pod is capped at 512 MB, and query parsing and caches already use about 350 MB of that. The bulk list is replaced wholesale every 6 hours; separately, about 20 tenant-specific suffixes per second must become matchable within 1 second. Which design fits the pod's memory budget and update pattern?