Practice
1. Given the following code snippet for finding concatenated words, what is the value of
memo after calling dfs('catsdog', 0) on the input ['cat', 'cats', 'dog', 'catsdog']?easy
Solution
Step 1: Trace dfs('catsdog', 0) calls and memo updates
Start=0: check prefixes 'cat'(0-3), 'cats'(0-4). 'cat' leads to dfs(3), 'cats' leads to dfs(4).Step 2: Evaluate dfs(3) and dfs(4)
dfs(3) checks 'sdog' prefix - no match, returns False; dfs(4) checks 'dog' prefix - matches 'dog', dfs(7) returns True; memo[4]=True, memo[3]=False, memo[0]=True.Final Answer:
Option C -> Option CQuick Check:
Memo correctly records True at 0 and 4, False at 3 [OK]
Hint: Memo stores start indices where suffix can form concatenation [OK]
Common Mistakes:
- Confusing indices or forgetting to memoize False results
2. Consider the following Python code implementing the optimal StreamChecker. Given the words ["cd", "f", "kl"], what is the return value of the query sequence: query('a'), query('b'), query('c'), query('d')?
Specifically, what does query('d') return?
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
class StreamChecker:
def __init__(self, words):
self.root = TrieNode()
self.max_len = max(len(w) for w in words)
self.stream = []
for word in words:
node = self.root
for ch in reversed(word):
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_word = True
def query(self, letter):
self.stream.append(letter)
if len(self.stream) > self.max_len:
self.stream.pop(0)
node = self.root
for ch in reversed(self.stream):
if ch not in node.children:
return False
node = node.children[ch]
if node.is_word:
return True
return False
sc = StreamChecker(["cd", "f", "kl"])
print(sc.query('a'))
print(sc.query('b'))
print(sc.query('c'))
print(sc.query('d'))
easy
Solution
Step 1: Trace the stream buffer after queries
After queries 'a', 'b', 'c', 'd', the stream buffer contains ['a','b','c','d'], but max_len=2, so oldest letters are popped. After 'c', stream=['b','c'], after 'd', stream=['c','d'].Step 2: Traverse trie with reversed stream
For query('d'), reversed stream is ['d','c']. Trie has reversed words: 'dc' for 'cd'. Traversing 'd' then 'c' hits is_word=True at 'c' node, so returns True. However, the query sequence is query('a'), query('b'), query('c'), query('d'). The query('c') returns False because 'c' alone is not a word. The query('d') returns True because 'cd' is in the dictionary and the stream buffer contains ['c','d'].Step 3: Check query('d') return value
Since the query('d') returns True, the correct answer is True.Final Answer:
Option B -> Option BQuick Check:
Stream buffer limited to max word length matches 'cd' suffix [OK]
Hint: Stream buffer limited to max word length [OK]
Common Mistakes:
- Not limiting stream buffer size
- Not reversing words in trie
- Returning false too early
3. Consider the following snippet from the optimal Trie + DFS solution for Word Search II. Given the board and words below, what is the final list of words found?
Board:
[['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']]
Words: ["oath", "pea", "eat", "rain"]
from typing import List
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
class Solution:
def buildTrie(self, words):
root = TrieNode()
for w in words:
node = root
for c in w:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.word = w
return root
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = self.buildTrie(words)
rows, cols = len(board), len(board[0])
result = []
def dfs(r, c, node):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
char = board[r][c]
if char == '#' or char not in node.children:
return
node = node.children[char]
if node.word:
result.append(node.word)
node.word = None
board[r][c] = '#'
dfs(r+1, c, node)
dfs(r-1, c, node)
dfs(r, c+1, node)
dfs(r, c-1, node)
board[r][c] = char
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return result
easy
Solution
Step 1: Trace DFS starting at 'o' (0,0)
"oath" is found by following o->a->t->h path on the board.Step 2: Trace DFS starting at 'e' (1,0)
"eat" is found by e->a->t path on the board.Final Answer:
Option D -> Option DQuick Check:
"pea" and "rain" cannot be formed on the board [OK]
Hint: Only words fully traceable on board are found [OK]
Common Mistakes:
- Including words not present on board
- Missing words found by DFS
- Not handling visited cells correctly
4. Consider the following buggy code snippet for the longest word in dictionary problem. Which line contains the subtle bug that can cause incorrect results?
medium
Solution
Step 1: Identify enqueue condition
The BFS queue should only include nodes representing complete words (child.word != None) to ensure all prefixes are valid.Step 2: Locate the bug
The code enqueues all children regardless of whether they represent complete words, allowing invalid prefixes to be considered, breaking the prefix condition.Final Answer:
Option A -> Option AQuick Check:
Enqueueing invalid prefix nodes causes incorrect longest word [OK]
Hint: Only enqueue nodes with complete words in BFS [OK]
Common Mistakes:
- Enqueueing all children regardless of word completion
- Misplacing word assignment in insert
- Sorting children incorrectly
5. Suppose the problem changes: you want to find the maximum XOR of two numbers in an array, but now numbers can be negative 32-bit integers. Which modification to the bitwise trie approach is necessary to handle negative numbers correctly?
hard
Solution
Step 1: Understand representation of negative numbers
Negative integers in 32-bit are stored in two's complement form, which can be treated as unsigned bit patterns for trie operations.Step 2: Modify trie insertion and traversal
Insert and traverse bits as unsigned 32-bit integers, including the sign bit, to correctly handle negative numbers.Step 3: Avoid incorrect approaches
Using 64-bit or adding constants changes problem semantics; ignoring sign bit loses information.Final Answer:
Option A -> Option AQuick Check:
Two's complement allows uniform bitwise trie handling of negative numbers [OK]
Hint: Two's complement bits can be treated as unsigned [OK]
Common Mistakes:
- Ignoring sign bit or converting to absolute values