Recommended
Practice
1. What is the time complexity of the optimal iterative approach using a queue to generate all letter combinations for a digit string of length n, assuming each digit maps to at most 4 letters?
medium
Solution
Step 1: Identify number of combinations
Each digit maps to up to 4 letters, so total combinations are up to 4^n.Step 2: Analyze work per combination
Each combination is built by concatenating letters for n digits, so each combination requires O(n) time to build.Step 3: Simplify complexity expression
O(4^n * n) and O(n * 4^n) are equivalent; however, O(n * 4^n) because we process each digit and expand combinations exponentially is the standard notation emphasizing processing each digit and expanding combinations exponentially.Final Answer:
Option A -> Option AQuick Check:
Time is exponential in n with linear cost per combination [OK]
Hint: Exponential combinations times linear build cost [OK]
Common Mistakes:
- Confusing exponential base (2 vs 4)
- Ignoring concatenation cost per combination
2. Consider the following code snippet for palindrome partitioning. Which line contains a subtle bug that causes incorrect or duplicate partitions?
def partition(s):
def is_palindrome(left, right):
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def backtrack(start, path):
if start == len(s):
result.append(path) # Line X
return
for end in range(start, len(s)):
if is_palindrome(start, end):
path.append(s[start:end+1])
backtrack(end+1, path)
path.pop()
result = []
backtrack(0, [])
return result
medium
Solution
Step 1: Identify how results are stored
Appendingpathdirectly stores a reference, so later modifications affect all stored results.Step 2: Correct approach
Useresult.append(path[:])to append a copy, preserving each partition snapshot.Final Answer:
Option B -> Option BQuick Check:
Shared references cause incorrect final partitions [OK]
Hint: Always append a copy of path to results [OK]
Common Mistakes:
- Forgetting to copy path before appending
- Incorrect palindrome check boundaries
- Forgetting to pop after recursion
3. The following code attempts to generate all permutations of a list using Heap's algorithm but contains a subtle bug:
def permute(nums):
res = [nums[:]]
c = [0] * len(nums)
i = 0
while i < len(nums):
if c[i] < i:
if i % 2 == 0:
nums[0], nums[i] = nums[i], nums[0]
else:
nums[c[i]], nums[i] = nums[i], nums[c[i]]
res.append(nums)
c[i] += 1
i = 0
else:
c[i] = 0
i += 1
return res
medium
Solution
Step 1: Identify how results are stored
The code appendsnumsdirectly toreswithout copying.Step 2: Understand consequences of appending references
Sincenumsis mutated in-place, all entries inrespoint to the same list, resulting in duplicates of the final permutation.Final Answer:
Option B -> Option BQuick Check:
Appending a copynums[:]fixes the bug [OK]
Hint: Always append a copy of mutable lists to results [OK]
Common Mistakes:
- Forgetting to copy before appending results in duplicate references
4. Examine the following snippet from an optimized Sudoku solver. Which line contains a subtle bug that can cause incorrect solutions or failure to backtrack properly?
def backtrack():
if not empties:
return True
empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
r, c = empties[0]
for ch in get_candidates(r, c):
board[r][c] = ch
rows[r].add(ch)
cols[c].add(ch)
boxes[(r//3)*3 + c//3].add(ch)
empties.pop(0)
if backtrack():
return True
# Undo changes
board[r][c] = '.'
rows[r].remove(ch)
cols[c].remove(ch)
boxes[(r//3)*3 + c//3].remove(ch)
empties.insert(0, (r, c))
return False
medium
Solution
Step 1: Identify mutation of empties list
The line popping empties[0] removes the cell but is never restored on backtrack failure.Step 2: Consequence of missing restoration
Without re-adding the cell to empties after failed recursion, future calls miss this cell, causing incorrect state and solutions.Final Answer:
Option A -> Option AQuick Check:
Backtracking requires undoing all changes including empties list [OK]
Hint: Backtracking must undo all state changes, including empties list [OK]
Common Mistakes:
- Forgetting to restore empties after pop
- Assuming board reset is sufficient
5. What is the time complexity of the optimal backtracking with Trie approach for Word Search II, given a board of size MxN and a list of words with maximum length L? Assume the Trie is already built.
medium
Solution
Step 1: Identify branching factor in backtracking
From each cell, up to 4 directions are possible initially, then up to 3 directions for subsequent steps due to no revisiting.Step 2: Calculate complexity with pruning
Trie pruning reduces unnecessary paths, so complexity is roughly O(M * N * 4 * 3^(L-1)) where L is max word length.Final Answer:
Option A -> Option AQuick Check:
Matches known complexity from Trie + backtracking analysis [OK]
Hint: Branching factor reduces after first step due to visited constraints [OK]
Common Mistakes:
- Confusing W (number of words) as multiplicative factor in optimal approach.