| Insert word (length m) | O(m) time; O(m) space worst case — new nodes only on the diverging suffix |
| Search exact word | O(m) time, O(1) extra space — walk m nodes, check isEndOfWord |
| startsWith(prefix) | O(p) time where p = prefix length, independent of dictionary size |
| List/count words under a prefix | O(p + k) — walk to prefix node, then DFS collect k matches |
| Space (n words, avg length m) | O(n×m) nodes worst case; shared prefixes reduce this in practice |
| Array-based children (fixed alphabet) | O(1) child access; O(k) memory per node regardless of how many are filled |
| HashMap-based children (sparse) | O(1) average access; memory scales with actual children present, plus per-entry overhead |
| Word Search II (trie + backtracking) | O(r×c×4ᶜ) bounded by trie pruning, L = longest word length |
isEndOfWord = true — "cat", "car", "card" share the prefix "ca"; "dog" branches from the root on its own pathTrie Data Structure Interview Questions & Answers
Q1. What is a trie (prefix tree)?
A: A trie is a tree-based data structure that stores a set of strings by breaking each string into individual characters, one per edge/level, so that strings sharing a common prefix also share the same path from the root. It is not a binary tree — each node can branch into as many children as there are distinct characters in the alphabet. Tries are optimized for prefix-based operations: insert, exact search, and "does any word start with X" all run proportional to the string length rather than the number of stored strings.
Q2. What does a typical TrieNode contain in Java?
A: A minimal TrieNode holds an array or map of child references (one per possible next character) and a boolean flag marking whether a complete word ends at that node. Many practical implementations add extra bookkeeping fields, such as a count of words passing through the node (for prefix counting) or a count of words ending exactly there (to support duplicates). No node needs to store its own character explicitly if array-based children encode it by index position.
class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean isEndOfWord;
int prefixCount; // words passing through this node
int wordCount; // words ending exactly at this node
}Q3. Why is a trie called a "prefix tree"?
A: Every node in a trie represents a prefix of one or more stored strings — the path from the root to any node spells out that prefix. Two words that share a common beginning (like "car" and "card") literally reuse the same chain of nodes for that shared portion before diverging. This structural sharing is what makes prefix queries so efficient: the answer for a prefix depends only on reaching its single corresponding node.
Q4. What is the branching factor of a trie and how is it determined?
A: The branching factor is the maximum number of children a node can have, which equals the size of the alphabet being indexed — 26 for lowercase English letters, 36 for alphanumeric, or up to 128/256 for extended ASCII. A larger alphabet increases per-node memory (if using fixed-size arrays) but does not change the asymptotic time complexity of insert/search, which remains O(word length) regardless of alphabet size.
Q5. How does a trie differ from a binary search tree for storing strings?
A: A BST compares entire strings lexicographically at each node and has O(log n) depth for n balanced entries, but each comparison can cost O(m) to compare full strings, giving O(m log n) search. A trie instead branches per character, giving O(m) search regardless of how many strings are stored, and naturally supports prefix queries that a BST cannot answer without a full subtree scan. The trade-off is that tries typically use more memory per stored character due to per-node overhead.
Q6. What is the role of the isEndOfWord flag?
A: Because tries share prefixes, reaching a node does not by itself mean a complete word was inserted there — the node might only represent a prefix of a longer word, or it might mark the end of one word while also being mid-path for another. The isEndOfWord boolean distinguishes "this exact path is a stored word" from "this path is merely a prefix of stored words," which is essential for correctly implementing search() versus startsWith().
Q7. Why doesn't a trie need to store the character in each node explicitly?
A: When children are stored in a fixed-size array, the array index itself encodes the character (index 0 = 'a', index 1 = 'b', and so on), so the character is implicit in the parent's children array position rather than needing a dedicated field on the node. HashMap-based implementations are the exception — there, the character is the explicit map key, which is one reason array-based nodes can be slightly more compact for small alphabets.
Q8. What is the height of a trie and what determines it?
A: The height of a trie equals the length of its longest stored word, since each character adds exactly one level of depth. This is different from balanced trees where height relates to the count of elements — in a trie, height is entirely a function of the longest string, so 10 words of length 5 produce the same height as 10,000 words of length 5.
Q9. Can a trie store duplicate words, and how should insert handle them?
A: A basic trie's isEndOfWord flag is idempotent — inserting the same word twice just sets the same flag to true again with no visible effect, so duplicates are effectively deduplicated by default. If duplicate counts matter (e.g., word-frequency use cases), the end node should track a counter that increments on each insert rather than relying on the boolean alone.
void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) node.children[idx] = new TrieNode();
node = node.children[idx];
}
if (node.isEndOfWord) {
node.duplicateCount++; // word already existed
} else {
node.isEndOfWord = true;
}
}Q10. How do you represent the root node of a trie in Java?
A: The root is just an ordinary TrieNode instance that represents the empty string prefix — it typically has isEndOfWord = false (unless the empty string itself is a valid stored word) and its children array/map holds the first character of every stored word. The Trie wrapper class holds a single reference to this root, created once when the trie is constructed.
class Trie {
private final TrieNode root = new TrieNode();
}Q11. How do you implement the insert operation?
A: Starting at the root, walk the word character by character; at each step, if the corresponding child doesn't exist yet, create it, then move into it. After processing the last character, mark that final node's isEndOfWord flag true. This costs O(m) time where m is the word length, and creates at most m new nodes (fewer if a prefix already exists).
void insert(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
}
node = node.children[idx];
node.prefixCount++;
}
node.isEndOfWord = true;
node.wordCount++;
}Q12. How do you implement the search (exact match) operation?
A: Walk the trie following the word's characters; if any character's child link is missing along the way, the word is absent and you can return false immediately. If you successfully reach the node for the last character, the word exists only if that node's isEndOfWord flag is true — reaching the node alone just means the string is a prefix of something stored.
boolean search(String word) {
TrieNode node = findNode(word);
return node != null && node.isEndOfWord;
}
private TrieNode findNode(String s) {
TrieNode node = root;
for (char c : s.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) return null;
node = node.children[idx];
}
return node;
}Q13. How do you implement startsWith (prefix search)?
A: startsWith reuses the same node-walking logic as search but skips the isEndOfWord check entirely — simply reaching the final node for the prefix's last character is sufficient proof that some stored word begins with that prefix. This is why tries answer "does any word start with X" in O(p) time, something a hash set cannot do without scanning every key.
boolean startsWith(String prefix) {
return findNode(prefix) != null;
}Q14. What is the time complexity of insert, search, and startsWith?
A: All three are O(m), where m is the length of the word or prefix being processed — completely independent of how many other words are already stored in the trie. This is the core selling point of a trie over a hash set or sorted list: lookup cost scales with the query's length, not with the dictionary's size.
Q15. What is the space complexity of a trie?
A: Worst case, storing n words of average length m with no shared prefixes at all uses O(n×m) nodes, each potentially holding up to k child pointers for an alphabet of size k. In practice, real dictionaries share many prefixes (common roots, suffixes like "-ing" or "-ed"), so actual memory usage is often significantly better than the worst-case bound, especially for natural-language vocabularies.
Q16. How do you implement delete from a trie?
A: Recursively descend to the node for the target word, clear its isEndOfWord flag, then unwind back up the call stack — at each level, remove (null out) the child link only if that child node has become both non-terminal (isEndOfWord false) and childless, so you don't disturb nodes still needed by other words. This keeps the trie compact by pruning dead-end chains after deletion, in O(m) time.
boolean delete(TrieNode node, String word, int depth) {
if (node == null) return false;
if (depth == word.length()) {
if (!node.isEndOfWord) return false;
node.isEndOfWord = false;
return isEmpty(node); // safe to prune if no children remain
}
int idx = word.charAt(depth) - 'a';
boolean shouldPruneChild = delete(node.children[idx], word, depth + 1);
if (shouldPruneChild) {
node.children[idx] = null;
return !node.isEndOfWord && isEmpty(node);
}
return false;
}
private boolean isEmpty(TrieNode node) {
for (TrieNode child : node.children) if (child != null) return false;
return true;
}Q17. What edge cases must a trie delete implementation handle?
A: Deleting a word that doesn't exist should be a no-op (search fails partway, nothing changes). Deleting a word that is also a prefix of another stored word (like deleting "car" when "card" also exists) must clear isEndOfWord on "car"'s node but must not remove any nodes, since "card" still needs that entire path. Deleting the last word in an otherwise-empty trie should correctly unwind pruning all the way back to (but not including) the root.
Q18. How do you count the total number of words stored in a trie?
A: A full DFS traversal counts every node whose isEndOfWord flag is true, summing across the whole tree in O(total nodes) time. If this query is needed frequently, it's cheaper to maintain a running counter on the Trie wrapper itself, incremented on insert and decremented on successful delete, turning the query into O(1).
int countWords(TrieNode node) {
int count = node.isEndOfWord ? 1 : 0;
for (TrieNode child : node.children) {
if (child != null) count += countWords(child);
}
return count;
}Q19. How do you count words that share a given prefix efficiently?
A: Maintain a prefixCount field on every node, incremented each time insert passes through it. To answer "how many words start with X," just walk to X's node in O(p) time and return its prefixCount directly — no DFS collection needed. Without this field, you'd have to walk to the prefix node and then DFS the entire subtree counting terminal nodes, which is slower when only the count (not the actual words) is needed.
int countWordsWithPrefix(String prefix) {
TrieNode node = findNode(prefix);
return node == null ? 0 : node.prefixCount;
}Q20. How do you retrieve all words stored in a trie?
A: Perform a depth-first traversal from the root, appending each traversed character to a running path buffer, and record the buffer's current contents whenever you pass a node with isEndOfWord true. Backtrack (remove the last character) as recursion unwinds so the buffer correctly represents the current path at every point. This runs in O(total characters across all stored words) time.
List<String> getAllWords() {
List<String> results = new ArrayList<>();
collect(root, new StringBuilder(), results);
return results;
}
private void collect(TrieNode node, StringBuilder path, List<String> results) {
if (node.isEndOfWord) results.add(path.toString());
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
path.append((char) ('a' + i));
collect(node.children[i], path, results);
path.deleteCharAt(path.length() - 1);
}
}
}Q21. How do you implement autocomplete (typeahead) using a trie?
A: First walk to the node representing the typed prefix in O(p) time; if that node doesn't exist, there are no suggestions. Otherwise, run the same DFS-collect routine used to list all words, starting from that prefix node instead of the root, and prepend the already-typed prefix to each collected suffix. This is the textbook reason tries back real-world search-box suggestions.
List<String> autocomplete(String prefix) {
TrieNode node = findNode(prefix);
List<String> results = new ArrayList<>();
if (node == null) return results;
collect(node, new StringBuilder(prefix), results);
return results;
}Q22. How do you limit autocomplete results to the top-k most relevant suggestions?
A: Rather than returning every completion (which could be thousands), collect candidates and maintain a bounded min-heap of size k keyed by a relevance score (frequency, recency, or popularity), pushing new candidates and evicting the lowest-scoring one whenever the heap exceeds k. This keeps the response small and fast regardless of how many total completions exist under a popular prefix like "a".
Q23. How would you rank autocomplete suggestions by search frequency or popularity?
A: Store a popularity/frequency score on each terminal node, updated whenever that word is searched or selected by a user. When generating suggestions for a prefix, collect matching words with their scores into a min-heap capped at size k, discarding the lowest-scored entry whenever the heap overflows, then reverse-sort the heap's contents for the final ranked output.
class Suggestion {
String word;
int frequency;
Suggestion(String w, int f) { word = w; frequency = f; }
}
List<String> topKSuggestions(TrieNode prefixNode, String prefix, int k) {
PriorityQueue<Suggestion> minHeap =
new PriorityQueue<>((a, b) -> a.frequency - b.frequency);
collectWithFrequency(prefixNode, new StringBuilder(prefix), minHeap, k);
List<String> result = new ArrayList<>();
while (!minHeap.isEmpty()) result.add(0, minHeap.poll().word);
return result;
}Q24. What is the complexity of returning all completions for a given prefix?
A: It is O(p + k), where p is the prefix length walked to reach the starting node and k is the total number of characters across all matching completions returned. The prefix walk is independent of dictionary size, so the dominant cost scales with how many results actually exist under that prefix, not with the trie's overall size.
Q25. How do you handle case-insensitive autocomplete?
A: The simplest approach normalizes all inserted words and all queries to a single case (typically lowercase) before touching the trie, storing the original casing separately (e.g., in a side map or as node metadata) if it needs to be preserved for display. Building a trie that natively branches on both cases would roughly double the alphabet size for no real benefit, so normalization at the boundary is the standard, simpler solution.
Q26. How would you support autocomplete with typo tolerance (fuzzy matching)?
A: A pure trie only matches exact prefixes, so typo tolerance requires layering an edit-distance-bounded search on top: DFS through the trie while tracking accumulated edit distance against the target prefix, pruning any branch whose distance already exceeds the allowed threshold. This is more expensive than exact prefix lookup but still far cheaper than scanning the entire dictionary computing edit distance against every word.
Q27. How do production search engines combine tries with other structures for typeahead at scale?
A: At scale, a pure in-memory trie for millions of queries with rich ranking becomes impractical to keep fully synchronized and re-ranked live, so systems typically use a trie (or a compressed variant like a radix tree) only for the prefix-matching stage, then hand candidate results to a separate ranking layer backed by precomputed scores, caches, or a search index like an inverted index. Sharding the trie across servers and periodically rebuilding it from batch-updated frequency data is also common rather than mutating a single live structure under heavy concurrent load.
Q28. What is the Word Search II problem?
A: Given an m×n grid of letters and a list of words, find every word from the list that can be traced as a path of adjacent cells (up/down/left/right, no cell reused within one word) in the grid. It's the classic combination of graph backtracking (DFS through the grid) with a dictionary lookup structure, and is a favorite interview problem specifically because the naive approach is far too slow.
Q29. Why is using a trie better than searching for each word individually in Word Search II?
A: Searching for each word one at a time means starting a fresh DFS from every grid cell for every word, redoing shared-prefix work repeatedly across similar words. Building one trie from all words lets a single DFS pass over the grid explore all words simultaneously, following trie edges instead of comparing against each word string directly, and letting the trie's structure prune paths the moment no word shares that prefix.
Q30. How do you implement Word Search II with a trie plus backtracking?
A: Insert all target words into a trie whose terminal nodes store the actual matched word (not just a boolean, since you need to know precisely which word completed). Then run DFS from every grid cell, moving into a trie child only if the corresponding letter exists there; whenever a DFS path lands on a node with a stored word, record it. Mark visited cells temporarily (e.g., overwrite with a sentinel character) during the current DFS branch and restore them on backtrack.
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = buildTrie(words);
List<String> result = new ArrayList<>();
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
dfs(board, r, c, root, result);
}
}
return result;
}
private void dfs(char[][] board, int r, int c, TrieNode node, List<String> result) {
char ch = board[r][c];
if (ch == '#' || node.children[ch - 'a'] == null) return;
node = node.children[ch - 'a'];
if (node.word != null) {
result.add(node.word);
node.word = null; // avoid duplicate matches
}
board[r][c] = '#'; // mark visited
int[] dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < board.length && nc >= 0 && nc < board[0].length) {
dfs(board, nr, nc, node, result);
}
}
board[r][c] = ch; // restore
}Q31. Why is pruning important in the Word Search II trie solution?
A: Without pruning, the same dead-end trie subtree can be re-explored from many different starting cells even after every word under it has already been found, wasting time. Clearing a terminal node's stored word after it's matched (so it won't match again) and, more aggressively, removing trie nodes that have no children and no longer lead anywhere, keeps the search space shrinking as results are found rather than staying constant throughout.
Q32. What is the time complexity of the trie + backtracking Word Search II solution?
A: Building the trie costs O(total characters across all words). The grid search is O(r×c×4ᶜ) in the worst case, since each of the r×c starting cells can fan out into up to 4 directions per step for up to L steps (L = longest word length), though the trie's branch pruning makes the real-world constant factor far smaller than a brute-force word-by-word search, which would cost O(r×c×4ᶜ × number of words) without sharing.
Q33. How do you avoid revisiting the same cell during backtracking?
A: Temporarily overwrite the current cell's character with a sentinel value (like '#') that cannot match any trie child before recursing into neighbors, then restore the original character once all four directions have been explored from that cell. This avoids needing a separate visited[][] boolean array, saving memory, since the board itself doubles as the visited marker during the active DFS path.
Q34. Why store the actual word string in the trie's end node in Word Search II, instead of just a boolean?
A: Because the DFS reconstructs a path through the grid rather than through a pre-known string, there's no cheap way to recover which word was just matched purely from a boolean flag — you'd need to separately track the accumulated path characters. Storing the completed word directly on its terminal trie node lets the DFS report a match in O(1) the instant it lands on that node, with no extra bookkeeping.
Q35. How do you find the longest common prefix of an array of strings using a trie?
A: Insert every string into a trie, then walk from the root following the single child at each level as long as exactly one child exists and the current node isn't itself the end of a stored word. The moment a node has zero, two, or more children, or marks a complete word, the walk stops — the path accumulated so far is the longest common prefix.
String longestCommonPrefix(String[] words) {
TrieNode node = root;
StringBuilder prefix = new StringBuilder();
while (true) {
int childIndex = -1, childCount = 0;
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) { childCount++; childIndex = i; }
}
if (childCount != 1 || node.isEndOfWord) break;
prefix.append((char) ('a' + childIndex));
node = node.children[childIndex];
}
return prefix.toString();
}Q36. What determines when to stop walking the trie for longest common prefix?
A: The walk stops at the first "branching point" — a node with more than one child, meaning the stored strings diverge there — or at a node marking the end of a shorter word that is itself a complete stored string (since you can't extend the common prefix past a word that has already ended). Either condition means no single next character is shared by every remaining string.
Q37. How does the trie-based longest common prefix approach compare to horizontal scanning?
A: Horizontal scanning compares strings pairwise or column-by-column directly, typically O(S) where S is the sum of all character lengths, using O(1) extra space beyond the input. The trie approach costs O(S) to build the trie plus O(L) to walk it (L = length of the common prefix), using O(S) extra space for the trie itself — so it's usually a worse trade for this specific single-shot problem, and interviewers mainly expect it to test trie fluency rather than because it's the optimal solution here.
Q38. What is the Word Break problem?
A: Given a string s and a dictionary of words, determine whether s can be segmented into a sequence of one or more dictionary words placed back to back with no gaps or overlaps (the same word may be reused multiple times). It's a classic dynamic programming problem, since the answer for a suffix of s depends on whether some prefix of that suffix is a dictionary word and the rest can also be broken.
Q39. How does a trie help optimize Word Break over a plain HashSet dictionary?
A: With a HashSet, checking every possible substring starting at position i against the dictionary requires generating each candidate substring (an O(length) string-copy operation) before hashing it, repeated for every possible end position. A trie lets you walk character by character from position i, checking isEndOfWord as you go, without ever materializing substring objects — and you can stop early the moment no trie child exists for the next character, avoiding wasted comparisons entirely.
Q40. How do you implement Word Break with a trie plus DP?
A: Maintain a boolean dp array where dp[i] means the prefix s[0..i) can be fully segmented into dictionary words. For each index i where dp[i] is true, walk the trie starting from the root at position i; every time you pass a trie node marking isEndOfWord, set dp at that further index to true as well. dp[n] (the full string) is the final answer.
boolean wordBreak(String s, Trie dict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 0; i < n; i++) {
if (!dp[i]) continue;
TrieNode node = dict.root;
for (int j = i; j < n; j++) {
node = node.children[s.charAt(j) - 'a'];
if (node == null) break;
if (node.isEndOfWord) dp[j + 1] = true;
}
}
return dp[n];
}Q41. What is the time complexity of trie-based Word Break?
A: For each of the n starting positions where dp[i] is true, the inner trie walk advances at most until the end of the string or a missing child, so overall it's O(n²) in the worst case (bounded by string length rather than dictionary size) — the same asymptotic bound as the HashSet-based DP, but with a smaller constant factor since it avoids substring allocation and repeated hashing.
Q42. How do you implement a basic spell checker using a trie?
A: Load a dictionary of correctly spelled words into a trie once at startup. To spell-check a word, simply call search(word); if it returns false, the word is flagged as potentially misspelled. This gives O(m) checking per word regardless of dictionary size, which is the foundation that correction-suggestion logic builds on top of.
Q43. How do you suggest corrections for a misspelled word using a trie?
A: DFS through the trie while tracking how many character edits (insert, delete, substitute) the current path has accumulated relative to the target misspelled word, pruning any branch whose edit count already exceeds a chosen threshold (commonly 1 or 2). Whenever the DFS lands on a node marking isEndOfWord within budget, that word becomes a candidate suggestion. This is dramatically cheaper than computing full edit distance against every dictionary word individually.
Q44. How do you implement "did you mean" suggestions combining trie traversal with edit-distance pruning?
A: Recurse through the trie in lockstep with an index into the target word; if the current trie character matches the target character at that index, advance both without spending an edit; otherwise, branch into "spend an edit and advance the target index" to model substitution, always bounding total edits by a maxEdits parameter. Any branch reaching isEndOfWord with the target index fully consumed and edits within budget is collected as a suggestion.
void suggest(TrieNode node, char[] target, int index, int edits,
int maxEdits, StringBuilder path, List<String> results) {
if (edits > maxEdits) return;
if (index == target.length && node.isEndOfWord) {
results.add(path.toString());
}
for (int i = 0; i < 26; i++) {
if (node.children[i] == null) continue;
char c = (char) ('a' + i);
path.append(c);
boolean matches = index < target.length && target[index] == c;
suggest(node.children[i], target, index + (matches ? 1 : 0),
edits + (matches ? 0 : 1), maxEdits, path, results);
path.deleteCharAt(path.length() - 1);
}
}Q45. Why is a trie well suited for prefix-based spell-check and autocorrect versus a plain dictionary set?
A: Spell-check features like "complete this partial word" or "suggest words starting with what's typed so far" are fundamentally prefix queries, which a trie answers in O(p) time by design. A plain HashSet dictionary has no concept of prefixes at all — every such query would require iterating the entire vocabulary and calling startsWith() on each candidate, an O(n×p) operation that gets slower as the dictionary grows.
Q46. What are the trade-offs of a trie versus a HashSet for word lookups?
A: A HashSet gives O(1) average-case exact-match lookup with typically lower memory overhead per stored string, but offers no native prefix support. A trie gives O(m) exact-match lookup (slightly worse for very large dictionaries where hashing wins) but adds prefix search, autocomplete, and ordered traversal essentially for free as structural properties, at the cost of more per-character node overhead.
Q47. What are the trade-offs of a trie versus a HashMap for prefix queries specifically?
A: A HashMap has no notion of "prefix" at all; answering "does any key start with X" requires iterating every key and calling startsWith() on each one, which is O(n×p) — linear in dictionary size. A trie answers the same query in O(p) by walking directly to the prefix's node, completely independent of how many words are stored, which is the whole reason tries exist for this use case.
// HashSet-based prefix search: must scan every key - O(n * p)
boolean hasWordsWithPrefixHashSet(Set<String> dict, String prefix) {
for (String word : dict) {
if (word.startsWith(prefix)) return true;
}
return false;
}
// Trie-based prefix search: O(p), independent of dictionary size
boolean hasWordsWithPrefixTrie(Trie trie, String prefix) {
return trie.startsWith(prefix);
}Q48. When would you NOT use a trie?
A: Skip a trie when you only ever need exact-match lookups with no prefix, ordering, or autocomplete requirement — a HashSet or HashMap will be simpler and often more memory-efficient. Also avoid tries for very short fixed-alphabet keys like single characters or small enums, where the per-node overhead dwarfs any benefit, and for extremely large, sparse Unicode vocabularies where a compressed structure (radix tree) or a different index entirely (e.g., a database with a prefix index) fits better.
Q49. How does a trie compare to a balanced BST for storing strings?
A: A balanced BST of n strings gives O(log n × m) search (log n comparisons, each up to O(m) to compare full strings), while a trie gives O(m) search regardless of n. The BST is more memory-efficient per string (one node per string, not per character) but loses the natural prefix-sharing and prefix-query capability that makes tries attractive for dictionary and autocomplete workloads.
Q50. How does a trie compare to a Bloom filter?
A: A Bloom filter is a probabilistic set membership structure — extremely space-efficient, O(1) lookup, but can return false positives (never false negatives) and cannot enumerate its contents or answer prefix queries at all. A trie is exact (no false positives), supports prefix operations and enumeration, but uses substantially more memory per entry. Bloom filters suit "is this probably in the set" gatekeeping at massive scale; tries suit exact prefix-aware dictionaries.
Q51. How does a trie differ from a suffix tree?
A: A standard trie indexes a set of complete strings from their beginnings, answering prefix queries about whole words. A suffix tree indexes every suffix of a single (usually long) string, enabling arbitrary substring search, longest repeated substring, and similar problems in O(pattern length) time after O(text length) construction. They solve fundamentally different problems: "which words start with X" versus "does X occur anywhere within this one text."
Q52. How does a trie differ from a suffix array?
A: A suffix array is a sorted array of all starting indices of a string's suffixes, offering similar substring-search power to a suffix tree but with a much smaller memory footprint (just integers) at the cost of needing binary search plus an LCP array for full efficiency. A trie stores whole distinct strings, not suffixes of one string, and is optimized for word-level prefix queries across a dictionary rather than substring search within one large text.
Q53. How does a trie compare to a Ternary Search Tree (TST)?
A: A TST stores one character per node like a trie, but instead of an array/map of children, each node has exactly three pointers (left for smaller characters, right for larger, middle for the next character in the string) — making it far more memory-efficient than an array-based trie for sparse alphabets while retaining O(m) average-case operations. The trade-off is that TST operations are influenced by insertion order and can degrade toward O(m log n) or worse if the tree becomes unbalanced, unlike a standard trie's guaranteed O(m).
class TSTNode {
char data;
TSTNode left, mid, right; // left < data, right > data, mid = next char
boolean isEndOfWord;
}Q54. Why can a trie outperform a hash-based lookup for prefix operations even though single-key lookup might be slower?
A: A hash table has no structural relationship between keys that share characters — "cat" and "car" hash to completely unrelated buckets, so there's no way to exploit their shared prefix. A trie's entire design is built around shared prefixes occupying shared nodes, so any operation that cares about "words related by a common prefix" is a direct, efficient tree walk in a trie versus an exhaustive scan in a hash table.
Q55. How does hashing collision risk compare to a trie's deterministic traversal?
A: Hash tables rely on a hash function distributing keys evenly; a poor hash function or adversarial input can cause clustering, degrading average O(1) lookups toward O(n) in the worst case (mitigated in Java's HashMap by treeifying long collision chains into red-black trees since Java 8). A trie's traversal cost is deterministic and purely a function of the string's length — there's no hash function, no collision handling, and no data-dependent worst case beyond the string being unusually long.
Q56. What is a compressed trie (radix tree / Patricia trie)?
A: A compressed trie merges chains of single-child nodes into one edge labeled with a multi-character string, instead of one node per character. This collapses long unbranching paths (common in sparse tries with few words sharing few branch points) into a single edge, dramatically reducing node count while preserving the same prefix-query semantics as a standard trie.
class RadixNode {
String segment; // compressed multi-character edge label
Map<Character, RadixNode> children = new HashMap<>();
boolean isEndOfWord;
}Q57. How does a radix tree reduce memory compared to a standard trie?
A: A standard trie allocates one node per character, so a long unbranching path like "international" (14 characters, no branching) creates 14 separate node objects, each with its own child-array/map overhead. A radix tree collapses that entire unbranching chain into a single node holding the string "international" as one edge label, cutting node count — and therefore per-node object overhead — from 14 down to 1 for that segment.
Q58. When would you use a radix tree over a standard trie?
A: Use a radix tree when the dictionary is sparse relative to its key length — many long keys with few shared branch points — since that's exactly the scenario where a standard trie wastes the most memory on long single-child chains. Router routing tables, URL path matchers, and IP prefix tables are classic examples where keys are long but branching is relatively rare.
Q59. What is the trade-off of radix tree compression regarding insert/delete complexity?
A: Insert and delete become more complex because an edge label may need to be split (when a new word diverges partway through an existing compressed segment) or merged (when a node becomes single-child again after a delete). This adds string-splitting/concatenation logic and extra bookkeeping compared to a standard trie's simple "add/remove a single-character link" operations, though asymptotic time complexity remains proportional to key length.
Q60. How is a radix tree used in real systems like IP routing tables?
A: IP routing uses longest-prefix-match lookups over binary IP address prefixes, and a radix tree (often specifically a Patricia trie over the address bits) stores routing entries compactly while still supporting fast prefix matching — critical since routers must perform millions of lookups per second with tight memory budgets. The compression keeps the tree shallow and small even though IP prefixes can share very few common bit patterns across entries.
Q61. What is a Patricia trie specifically?
A: Patricia trie (Practical Algorithm To Retrieve Information Coded In Alphanumeric) is a specific, historically significant variant of a compressed binary radix trie where every internal node has exactly two children and stores a bit-index indicating which bit to test next, skipping over runs of non-branching bits entirely. It's the classical academic term that predates the more general "radix tree" terminology used in most modern engineering contexts.
Q62. What are the trade-offs between array-based children and HashMap-based children in a TrieNode?
A: A fixed-size array (e.g., size 26) gives guaranteed O(1) child access with zero hashing overhead, but every node pays for the full array regardless of how many children it actually has — wasteful for large or sparse alphabets. A HashMap only allocates entries for children that actually exist, saving memory in sparse cases, but adds per-entry object overhead (hash buckets, boxed Character keys) and slightly slower average-case access due to hashing.
// Array-based (fixed alphabet, O(1) access, some wasted memory)
class ArrayTrieNode {
ArrayTrieNode[] children = new ArrayTrieNode[26];
boolean isEndOfWord;
}
// HashMap-based (sparse alphabet friendly, per-entry overhead)
class MapTrieNode {
Map<Character, MapTrieNode> children = new HashMap<>();
boolean isEndOfWord;
}Q63. What is the memory overhead of a HashMap-based TrieNode compared to array-based?
A: Each HashMap entry in Java carries its own Node object overhead (hash, key reference, value reference, next-pointer for chaining) plus a boxed Character key, typically costing on the order of several dozen bytes per entry beyond the actual pointer being stored. An array slot, in contrast, is just a raw reference — 4 or 8 bytes depending on JVM pointer compression — with no extra wrapper object at all, making arrays far cheaper per filled slot.
Q64. When is array-based better despite its fixed overhead?
A: When the alphabet is small (26-62 characters) and nodes tend to be reasonably dense (many children actually populated, as in natural-language dictionaries with common prefixes), the fixed array cost per node is small in absolute terms and access speed benefits from no hashing and excellent CPU cache locality for the contiguous array. It's also simpler to implement correctly, which matters in a live interview setting.
Q65. When is HashMap-based children preferable?
A: When the alphabet is very large (full Unicode) or nodes are typically sparse (most nodes have only 1-2 real children, common deep in a trie or with less common alphabets), a HashMap avoids allocating dozens or hundreds of mostly-null array slots per node, trading a bit of per-access speed for potentially much lower total memory across the whole structure.
Q66. How do you handle full Unicode alphabets in a trie?
A: A fixed array indexed by raw char value is impractical for Unicode (65,536+ code points, and surrogate pairs for characters beyond the Basic Multilingual Plane), so Unicode tries almost always use HashMap-based children keyed by Unicode code point (an int, retrieved via String.codePointAt) rather than by char, correctly handling characters outside the BMP that Java represents as surrogate pairs.
class UnicodeTrieNode {
Map<Integer, UnicodeTrieNode> children = new HashMap<>();
boolean isEndOfWord;
}
void insert(UnicodeTrieNode root, String word) {
UnicodeTrieNode node = root;
int i = 0;
while (i < word.length()) {
int codePoint = word.codePointAt(i);
node = node.children.computeIfAbsent(codePoint, k -> new UnicodeTrieNode());
i += Character.charCount(codePoint);
}
node.isEndOfWord = true;
}Q67. How can trie memory be reduced further using a double-array trie?
A: A double-array trie encodes the entire structure into two large parallel primitive int arrays (base[] and check[]) instead of individual node objects with array/map fields, computing child transitions arithmetically rather than through object pointers. This eliminates per-node object header overhead entirely and gives excellent cache locality, at the cost of significantly more complex construction and update logic — it's mainly used in performance-critical production systems (like Japanese morphological analyzers) rather than typical interview answers.
Q68. How does object overhead in Java affect trie memory usage at scale?
A: Every TrieNode is a separate heap object carrying a JVM object header (typically 12-16 bytes) in addition to its actual fields, and an array-based node with 26 reference slots adds roughly 8 bytes per slot (or 4 with compressed oops) even when most are null. For a large dictionary with millions of nodes, this per-object overhead can dominate total memory usage — which is exactly the pressure that motivates HashMap-based children for sparse cases or a compressed/double-array trie for extreme scale.
Q69. How can you estimate the worst-case number of nodes for n words of average length m?
A: The absolute worst case, with zero shared prefixes among any words, is n×m total nodes (every character of every word gets its own unique node). Real dictionaries fall well short of this bound because natural-language vocabularies share common prefixes extensively (word roots, common short words), so actual node counts are typically a fraction of the theoretical n×m maximum — though the bound is still the correct one to cite for worst-case complexity analysis.
Q70. How do you implement a trie to support wildcard search where '.' matches any single character?
A: Extend the search DFS so that when the query character is '.', instead of following one specific child, it branches into every existing child of the current node and recurses down each. Any branch that reaches the end of the query string on a node with isEndOfWord true means the wildcard pattern matched; this is exactly LeetCode's "Design Add and Search Words Data Structure."
class WordDictionary {
TrieNode root = new TrieNode();
void addWord(String word) {
TrieNode node = root;
for (char c : word.toCharArray()) {
node = node.children.computeIfAbsent(c, k -> new TrieNode());
}
node.isEndOfWord = true;
}
boolean search(String word) {
return dfs(root, word, 0);
}
private boolean dfs(TrieNode node, String word, int i) {
if (i == word.length()) return node.isEndOfWord;
char c = word.charAt(i);
if (c == '.') {
for (TrieNode child : node.children.values()) {
if (dfs(child, word, i + 1)) return true;
}
return false;
}
TrieNode next = node.children.get(c);
return next != null && dfs(next, word, i + 1);
}
}Q71. How do you find all words in a trie matching a given wildcard pattern?
A: Reuse the same branching DFS logic as boolean wildcard search from Q70, but instead of returning true on the first match, accumulate the current path into a results list every time the DFS reaches the end of the pattern on an isEndOfWord node, and continue exploring remaining branches rather than short-circuiting. Worst case this touches every node reachable via wildcard positions, so complexity depends heavily on how many '.' characters and matching branches the pattern has.
Q72. How do you implement "Replace Words" (replace each word in a sentence with its shortest dictionary root) using a trie?
A: Insert every root word into a trie. For each word in the sentence, walk the trie character by character; the instant you land on a node marking isEndOfWord, stop and use the path accumulated so far as the replacement (it's guaranteed to be the shortest matching root since you stop at the first match found while walking left to right). If no root matches by the time the word or trie path ends, keep the original word unchanged.
String replaceWords(List<String> roots, String sentence) {
Trie trie = new Trie();
for (String r : roots) trie.insert(r);
StringBuilder result = new StringBuilder();
for (String word : sentence.split(" ")) {
result.append(shortestRoot(trie, word)).append(" ");
}
return result.toString().trim();
}
private String shortestRoot(Trie trie, String word) {
TrieNode node = trie.root;
StringBuilder prefix = new StringBuilder();
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) return word; // no root found
prefix.append(c);
node = node.children[idx];
if (node.isEndOfWord) return prefix.toString();
}
return word;
}Q73. How do you find the "Maximum XOR of Two Numbers in an Array" using a binary trie?
A: Build a binary trie where each number is inserted bit by bit from most significant to least significant bit, so each node has exactly two possible children (0 and 1). To maximize XOR against a given number, greedily walk the trie preferring the opposite bit at each level whenever it exists (opposite bits XOR to 1, maximizing the result), falling back to the same-bit child only when the opposite doesn't exist. Doing this for every number against the shared trie of all numbers gives O(32n) time instead of O(n²) brute-force pairwise XOR.
class BitTrieNode {
BitTrieNode[] children = new BitTrieNode[2];
}
int findMaximumXOR(int[] nums) {
BitTrieNode root = new BitTrieNode();
for (int num : nums) insert(root, num);
int maxXor = 0;
for (int num : nums) {
maxXor = Math.max(maxXor, queryMaxXor(root, num));
}
return maxXor;
}
void insert(BitTrieNode root, int num) {
BitTrieNode node = root;
for (int b = 31; b >= 0; b--) {
int bit = (num >> b) & 1;
if (node.children[bit] == null) node.children[bit] = new BitTrieNode();
node = node.children[bit];
}
}
int queryMaxXor(BitTrieNode root, int num) {
BitTrieNode node = root;
int result = 0;
for (int b = 31; b >= 0; b--) {
int bit = (num >> b) & 1;
int wantedBit = 1 - bit;
if (node.children[wantedBit] != null) {
result |= (1 << b);
node = node.children[wantedBit];
} else {
node = node.children[bit];
}
}
return result;
}Q74. What is a binary trie (bit trie) and how does it differ from a character trie?
A: A binary trie indexes integers by their individual bits rather than strings by their characters, so every node has exactly two children (representing bit 0 and bit 1) and the trie's depth equals the fixed bit-width of the integers being stored (commonly 32 or 64). It's structurally identical to a character trie with an alphabet size of 2, and is used for problems like maximum XOR pair, IP prefix matching, and certain bitwise range-query structures.
Q75. How does a trie help with the Palindrome Pairs problem?
A: Palindrome Pairs asks which pairs of words in a list concatenate to form a palindrome. A trie built from the reversed words lets you, for each word, walk the trie while checking if the remaining unmatched suffix (or the word's own remaining prefix) is itself a palindrome at each node passed — turning an O(n²×m) brute-force pairwise check into roughly O(n×m²) by reusing the reversed-word trie structure across all words instead of comparing every pair independently.
Q76. How do you distinguish exact-word lookup from prefix lookup cleanly in a trie API design?
A: Expose two separate methods with clearly different contracts — search(word) returns true only when isEndOfWord is set on the final node, while startsWith(prefix) returns true as soon as the final node exists at all, regardless of that flag. Keeping them as distinct methods (rather than one method with a boolean flag parameter) makes the API self-documenting and matches how these two operations are described in virtually every trie interview problem statement.
Q77. How would you serialize and deserialize a trie?
A: A simple scheme does a DFS, emitting a marker for whether the current node is a word-end, then recursively emitting each existing child prefixed by its character, followed by a distinct end-of-children sentinel so the deserializer knows when to stop reading children and pop back up a level. This preserves exact structure and can be reconstructed with a matching recursive parser reading the same token stream in order.
void serialize(TrieNode node, StringBuilder sb) {
sb.append(node.isEndOfWord ? '1' : '0');
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
sb.append((char) ('a' + i));
serialize(node.children[i], sb);
}
}
sb.append('#'); // end-of-children marker
}Q78. How do you find the longest word that can be built one character at a time by other words in the dictionary?
A: Insert all words into a trie. For each candidate word, walk the trie one character at a time, requiring that every intermediate node along the way (not just the final node) also has isEndOfWord true — meaning every prefix of the candidate is itself a complete dictionary word. Track the longest such "buildable" word, breaking ties by lexicographically smallest.
String longestWord(String[] words) {
Trie trie = new Trie();
for (String w : words) trie.insert(w);
String best = "";
for (String w : words) {
if (isBuildable(trie, w) &&
(w.length() > best.length() ||
(w.length() == best.length() && w.compareTo(best) < 0))) {
best = w;
}
}
return best;
}
private boolean isBuildable(Trie trie, String word) {
TrieNode node = trie.root;
for (char c : word.toCharArray()) {
node = node.children[c - 'a'];
if (node == null || !node.isEndOfWord) return false;
}
return true;
}Q79. How do you handle case sensitivity in a trie storing mixed-case words?
A: If case must be preserved and distinguished ("US" vs "us" are different entries), simply widen the alphabet so both uppercase and lowercase characters map to distinct child slots (e.g., size-52 array, or a HashMap keyed by the raw char). If case should be ignored for matching purposes but the original casing still needs to be displayed, normalize to one case for trie storage/traversal and keep the original strings in a side lookup keyed by the normalized form.
Q80. How would you implement a trie iterator to traverse words in sorted order?
A: Because array-based children are naturally indexed in alphabetical order (index 0 = 'a', 1 = 'b', ...), a straightforward DFS that visits children in index order and records completed words automatically produces output in lexicographically sorted order with no extra sorting step needed. Wrapping this in an Iterator interface just means pre-computing the ordered list once (or using a lazy generator/coroutine-style approach for true streaming).
class TrieIterator implements Iterator<String> {
private final Deque<String> buffer = new ArrayDeque<>();
TrieIterator(TrieNode root) {
collect(root, new StringBuilder());
}
private void collect(TrieNode node, StringBuilder path) {
if (node == null) return;
if (node.isEndOfWord) buffer.addLast(path.toString());
for (int i = 0; i < 26; i++) {
if (node.children[i] != null) {
path.append((char) ('a' + i));
collect(node.children[i], path);
path.deleteCharAt(path.length() - 1);
}
}
}
public boolean hasNext() { return !buffer.isEmpty(); }
public String next() { return buffer.pollFirst(); }
}Q81. What design issues arise with recursive versus iterative trie traversal for very long words?
A: Recursive insert/search/delete implementations grow the call stack proportional to word length, which is a non-issue for typical dictionary words but risks a StackOverflowError for pathological inputs (extremely long strings, or malicious input in a public-facing service). Iterative implementations using an explicit while-loop and a single mutable node reference avoid this risk entirely and are the safer default for production code handling untrusted input lengths.
Q82. How do you implement a trie that supports counting distinct prefixes?
A: This is the same prefixCount field described earlier (see the prefix-counting insert/query pattern): increment a counter on every node touched during insert, then a distinct-prefix query for length k just means walking k levels down any branch and checking that the node exists — the number of "distinct prefixes of length k" across the whole trie equals the number of distinct nodes at depth k, countable via a single BFS/DFS level scan.
Q83. How would you use a trie to implement IP routing longest-prefix match?
A: Build a binary trie over IP addresses' bits (32 levels for IPv4), where each stored route corresponds to a node marked with routing metadata (next-hop, etc.) at the depth equal to its prefix length (e.g., a /24 route marks a node 24 bits deep). To route a packet, walk the trie following the destination address's bits, remembering the deepest marked node encountered along the way — that's the longest matching prefix, giving the most specific applicable route.
Q84. How do you use a trie for T9 predictive text input?
A: Each digit key maps to a small set of letters (2 → "abc", 3 → "def", etc.); given a digit sequence, DFS through a dictionary trie where at each step you only follow children whose character belongs to the current digit's letter set, rather than following a single specific character. Any DFS path that consumes all digits while landing on an isEndOfWord node is a valid predicted word for that digit sequence.
static final String[] T9 = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
List<String> wordsForDigits(String digits, Trie dictionaryTrie) {
List<String> results = new ArrayList<>();
dfs(dictionaryTrie.root, digits, 0, new StringBuilder(), results);
return results;
}
private void dfs(TrieNode node, String digits, int i, StringBuilder path, List<String> results) {
if (node == null) return;
if (i == digits.length()) {
if (node.isEndOfWord) results.add(path.toString());
return;
}
for (char c : T9[digits.charAt(i) - '0'].toCharArray()) {
int idx = c - 'a';
if (node.children[idx] != null) {
path.append(c);
dfs(node.children[idx], digits, i + 1, path, results);
path.deleteCharAt(path.length() - 1);
}
}
}Q85. How does a trie help implement phone contact search by initials or prefix?
A: Storing contact names (or normalized tokens like first-name+last-name) in a trie lets a partially typed search term resolve to all matching contacts via a single startsWith walk plus a DFS collect, exactly like autocomplete. For multi-word names, some implementations insert multiple entry points per contact (e.g., both "john smith" and "smith john") so prefix search matches regardless of which name the user starts typing.
Q86. What's the difference between a trie's "prefix count" and "word count" at a node, and why track both?
A: prefixCount answers "how many stored words pass through this node," which includes words that are still longer than the current path; wordCount (or isEndOfWord) answers "how many stored words end exactly here." A node can have a high prefixCount but zero words ending there (it's purely a shared prefix), or the reverse in rarer cases — tracking both lets a single trie efficiently answer both "count words with this prefix" and "count occurrences of this exact word" without separate structures.
Q87. How would you detect if one word is a prefix of any other word already in the trie during insertion?
A: While walking the trie to insert a new word, check isEndOfWord on every intermediate node passed along the way — if any of them is already true, the new word extends an existing shorter word, meaning that shorter word is a prefix of the new one. Separately, after insertion completes, check whether the final node has any children — if so, the newly inserted word is itself a prefix of some longer existing word.
Q88. How can trie space usage blow up, and how do you mitigate it?
A: Space blows up when many stored strings share very little in common (few branching-point savings) combined with a large alphabet and array-based children, since each node pays for the full child array regardless of fill. Mitigations include switching to HashMap-based children for sparse cases, compressing non-branching chains with a radix tree, or bounding the alphabet to only the characters actually present in the dataset instead of a generic fixed size.
Q89. What happens to a trie's shape when inserted words share no common prefixes?
A: The trie degenerates into a shallow, extremely wide "forest" hanging off the root — essentially every word becomes its own independent chain starting at depth 1, with the root having as many children as there are distinct first characters. Total node count approaches the worst-case n×m bound in this scenario, since almost no structural sharing occurs beyond (at most) the first character.
Q90. What happens to a trie's shape when inserted words are very similar, like "a", "aa", "aaa", "aaaa"?
A: The trie degenerates into a single long chain, essentially behaving like a linked list where each node has exactly one child — worst-case depth equal to the longest word, with isEndOfWord flags set at multiple points along that single chain. This is the scenario where a trie offers no meaningful advantage over simpler structures, since there's no real branching to exploit.
Q91. How do you handle trie "underflow" — very sparse, long, unbranching chains — memory-wise?
A: This is exactly the scenario a compressed trie/radix tree is designed to fix: instead of one node per character along a long unbranching chain, collapse the entire chain into a single edge labeled with the full substring, cutting node count from O(chain length) down to O(1) for that segment while preserving identical query semantics.
Q92. Why is trie traversal generally less cache-friendly than array-based binary search?
A: Binary search over a sorted array walks through contiguous memory with excellent spatial locality, so the CPU cache can prefetch effectively. A trie traversal follows object references scattered across the heap — each child pointer can point anywhere the garbage collector placed that node — causing frequent cache misses as the traversal jumps between memory locations, which is a real-world performance cost not reflected in the asymptotic O(m) complexity.
Q93. What real-world applications commonly use tries besides autocomplete?
A: IP routing tables (longest-prefix match), spell checkers and predictive text (T9), IDE autocomplete for identifiers and file paths, phone contact/dialer search, DNS domain name lookups (often stored in reverse-label tries), URL routing tables in web frameworks, and word-game solvers (like Boggle/Word Search) that need fast prefix-pruned dictionary lookups are all common production uses beyond a search box.
Q94. How would you test a Trie implementation for correctness in an interview setting?
A: Cover: inserting then searching the same word returns true; searching a word never inserted returns false; searching a prefix that was never inserted as a complete word returns false even though startsWith on that same prefix returns true; inserting overlapping words like "car" and "card" and confirming both are independently found; deleting a word that's also a prefix of another and confirming the other word still searches correctly afterward; and edge cases like the empty string and single-character words.
Q95. What's the Big-O for building a trie from n words each of average length m?
A: Building the trie costs O(n×m) total — each of the n insert calls is O(m), and there are n of them, giving a combined bound independent of how much prefix sharing actually occurs (sharing only affects total node count, not the total characters that must be processed during insertion).
Q96. How do you handle an empty string insertion into a trie?
A: Inserting an empty string means no characters are walked at all, so the loop body never executes and isEndOfWord is set directly on the root node itself. Correspondingly, search("") should return true only if the root's isEndOfWord flag was set this way, and startsWith("") should always return true for any non-empty trie, since every string trivially starts with the empty prefix.
Q97. How do you extend startsWith to return a count instead of just a boolean?
A: This is the same technique as prefix counting described earlier: instead of returning "node != null," return the walked node's prefixCount field (or 0 if the node doesn't exist), which was incremented on every insert that passed through it. No extra traversal is needed beyond the O(p) walk to the prefix node itself.
Q98. What are common trie interview mistakes candidates make?
A: Forgetting to check isEndOfWord in search() and conflating it with startsWith() (returning true for any reachable node) is the most frequent bug. Others include off-by-one errors in array indexing (using the wrong base like 'A' instead of 'a'), forgetting to handle a missing child by returning early instead of throwing a NullPointerException, and not restoring backtracking state (like a visited marker) correctly in grid-search variants such as Word Search II.
Q99. How would you make a Trie thread-safe for concurrent access?
A: A simple approach wraps all mutating operations (insert, delete) in a write lock and read-only operations (search, startsWith) in a read lock using a ReentrantReadWriteLock, allowing concurrent reads to proceed in parallel while serializing writes. For very high read concurrency with infrequent writes, a copy-on-write strategy (build a new trie version and atomically swap a reference) avoids locking readers entirely at the cost of memory during rebuilds.
class ConcurrentTrie {
private final TrieNode root = new TrieNode();
private final ReadWriteLock lock = new ReentrantReadWriteLock();
void insert(String word) {
lock.writeLock().lock();
try {
// standard insert logic against root
} finally {
lock.writeLock().unlock();
}
}
boolean search(String word) {
lock.readLock().lock();
try {
// standard search logic against root
return true;
} finally {
lock.readLock().unlock();
}
}
}Q100. How do you choose between recursion and iteration for insert/search implementations in Java?
A: Iterative implementations are generally preferred in production Java code for insert/search/startsWith because they avoid call-stack growth proportional to word length and typically run slightly faster due to no method-call overhead. Recursive implementations are common in interview settings for delete (where post-order pruning logic is cleaner to express recursively) and for DFS-based collection operations like listing all words, where the recursion naturally mirrors the tree structure being traversed.
Q101. How can a trie be combined with a HashMap for a two-level indexing strategy?
A: A common optimization for very large dictionaries buckets words by their first character (or first few characters) into a HashMap of smaller sub-tries, so each sub-trie is shallower and lookups first do an O(1) HashMap dispatch before walking a much smaller trie for the remainder of the word. This can improve cache locality and parallelize construction/updates across buckets, at the cost of added implementation complexity over a single unified trie.
Q102. How would you implement "Design Add and Search Words Data Structure" supporting '.' wildcards?
A: This is precisely the wildcard-search trie covered earlier: addWord inserts normally via standard trie insert, and search performs a DFS where a '.' character branches into every existing child at that node instead of following one specific link, returning true if any branch reaches the end of the query on an isEndOfWord node. The full implementation and code sample for this exact pattern is shown above in the wildcard search question.
Q103. What is the difference between a Trie and a Suffix Trie when it comes to substring search?
A: A standard trie only lets you search for strings by their beginning — it cannot tell you whether a pattern occurs anywhere in the middle of a stored string. A suffix trie inserts every suffix of the target text as a separate trie entry, so searching for any substring becomes equivalent to a prefix search against that suffix trie, at the cost of O(n²) space to store all n suffixes naively (suffix trees and suffix arrays exist specifically to reduce this space cost).
Q104. How would you find the shortest unique prefix for every word in a list using a trie?
A: Insert all words into a trie while maintaining the prefixCount field described earlier. For each word, walk from the root accumulating characters until you reach a node whose prefixCount equals 1 — meaning no other word in the dictionary shares that prefix any further — and that accumulated path is the shortest prefix that uniquely identifies the word.
Map<String, String> shortestUniquePrefixes(String[] words) {
Trie trie = new Trie();
for (String w : words) trie.insert(w);
Map<String, String> result = new HashMap<>();
for (String w : words) {
TrieNode node = trie.root;
StringBuilder prefix = new StringBuilder();
for (char c : w.toCharArray()) {
prefix.append(c);
node = node.children[c - 'a'];
if (node.prefixCount == 1) break; // uniquely identifies the word
}
result.put(w, prefix.toString());
}
return result;
}Q105. How do you handle memory cleanup considerations for a large trie in Java?
A: Because nodes reference each other only downward (parent to child), a trie is naturally garbage-collectible in the normal way once dropped — but the delete operation's job of nulling out now-empty child links (see the pruning delete logic above) is what actually lets the JVM reclaim memory for individual removed words during the trie's lifetime, rather than leaving orphaned dead-end chains permanently retained. For very large tries under memory pressure, periodically rebuilding a compacted/compressed version can also help if fragmentation from repeated insert/delete cycles becomes an issue.
Q106. How would search-as-you-type combine autocomplete and spell-check correction in one trie-backed feature?
A: As the user types, run prefix-based autocomplete (Q21) against the partial input for instant suggestions; if the input so far yields zero matches after a reasonable number of characters, fall back to the edit-distance-bounded suggestion DFS (Q44) to offer likely-intended corrections instead. Ranking both result sets by frequency (Q23) before display lets the feature seamlessly blend "complete what you're typing" with "here's what you probably meant" using the same underlying trie.
Q107. How do you extend a trie node to store an associated value, like a Map<String, V>?
A: Add a generic value field (plus a boolean or sentinel indicating "this key has an associated value" to distinguish an explicitly-stored null from "no entry") to the node class. put(key, value) walks/creates the path exactly like insert, then sets the value on the final node; get(key) walks the path and returns the value only if the final node's hasValue flag is true, mirroring how a HashMap distinguishes a missing key from one mapped to null.
class TrieMapNode<V> {
TrieMapNode<V>[] children = new TrieMapNode[26];
V value;
boolean hasValue;
}
class TrieMap<V> {
private final TrieMapNode<V> root = new TrieMapNode<>();
void put(String key, V value) {
TrieMapNode<V> node = root;
for (char c : key.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) node.children[idx] = new TrieMapNode<>();
node = node.children[idx];
}
node.value = value;
node.hasValue = true;
}
V get(String key) {
TrieMapNode<V> node = root;
for (char c : key.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) return null;
node = node.children[idx];
}
return node.hasValue ? node.value : null;
}
}Q108. What is the difference between "search" returning a boolean vs "get" returning an associated value in a Trie-based Map?
A: A boolean search() only answers membership — "is this key present" — which is sufficient for a plain Trie/Set use case. A get() in a TrieMap must additionally distinguish "key absent" from "key present but mapped to null," which requires an explicit hasValue flag rather than relying on a null check alone, exactly analogous to how java.util.Map's get() and containsKey() serve different purposes.
Q109. How do you handle deletion cascading — removing now-unused ancestor nodes — efficiently?
A: This is handled by the same recursive delete pattern shown earlier (Q16): the recursion returns a boolean up each call frame indicating "my child became prunable," letting each ancestor level decide independently whether it too has become empty and non-terminal, and therefore also prunable. This bottom-up unwinding naturally cascades pruning as far up the tree as needed in a single O(m) pass, without a separate cleanup traversal.
Q110. Summarize the key trade-off decision points when designing a trie for a Java backend interview answer.
A: Choose array-based children for small, dense alphabets prioritizing raw speed and simplicity; choose HashMap-based children for large or sparse alphabets prioritizing memory. Choose a standard trie when insert/delete simplicity matters most; choose a compressed/radix trie when memory for long, sparsely-branching keys matters more than implementation complexity. Always clarify whether the interviewer needs exact match, prefix match, autocomplete ranking, or wildcard support, since each adds a different, well-known extension on top of the same core insert/search/startsWith foundation.
Post a Comment
Add