Practice
1. Consider the following Python code snippet implementing the optimal backtracking approach for Expression Add Operators. Given input num = "123" and target = 6, what is the content of the result list after the function completes?
from typing import List
def addOperators(num: str, target: int) -> List[str]:
res = []
path = []
def backtrack(index: int, evaluated: int, last_operand: int):
if index == len(num):
if evaluated == target:
res.append(''.join(path))
return
for i in range(index, len(num)):
if i != index and num[index] == '0':
break
curr_str = num[index:i+1]
curr = int(curr_str)
length_before = len(path)
if index == 0:
path.append(curr_str)
backtrack(i+1, curr, curr)
path[length_before:] = []
else:
path.append('+'); path.append(curr_str)
backtrack(i+1, evaluated + curr, curr)
path[length_before:] = []
backtrack(0, 0, 0)
return res
easy
Solution
Step 1: Trace backtracking calls for num="123", target=6
At index=0, path starts with "1". Then at index=1, add '+' and "2", evaluated=3. Then at index=2, add '+' and "3", evaluated=6, matches target, so "1+2+3" is added.Step 2: Check other possible expressions
"123" alone evaluates to 123, not 6. "1+23"=24, "12+3"=15, none equal 6. So only "1+2+3" is in result.Final Answer:
Option D -> Option DQuick Check:
Only "1+2+3" sums to 6 [OK]
Hint: Only "1+2+3" equals 6 with given operators [OK]
Common Mistakes:
- Assuming "123" or "1+23" equals target
2. Given the following code snippet for
getPermutation, what is the returned value when calling getPermutation(3, 3)?easy
Solution
Step 1: Trace factorial array computation
factorial = [1, 1, 2] for n=3.Step 2: Calculate indices and build result
k=3 -> k=2 zero-based. For i=2: idx=2//2=1, pick '2'. For i=1: k=2%2=0, idx=0//1=0, pick '1'. For i=0: k=0%1=0, idx=0//1=0, pick '3'. Result = '213'.Final Answer:
Option C -> Option CQuick Check:
Output matches expected k-th permutation '213' [OK]
Hint: Remember to convert k to zero-based before indexing [OK]
Common Mistakes:
- Off-by-one error in k adjustment
- Wrong index calculation in loop
- Not popping used numbers
3. Given the following code for generating unique permutations, what is the final output when the input is
[1,1,2]?
from typing import List
def permuteUnique(nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
def backtrack(start=0):
if start == len(nums):
res.append(nums[:])
return
seen = set()
for i in range(start, len(nums)):
if nums[i] in seen:
continue
seen.add(nums[i])
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start]
backtrack()
return res
print(permuteUnique([1,1,2]))easy
Solution
Step 1: Trace initial sorting and first level of recursion
Input sorted to [1,1,2]. At start=0, i iterates over 0 to 2. First, swap nums[0] with nums[0] (1), add 1 to seen, recurse.Step 2: Trace subsequent recursion and skipping duplicates
At start=1, i iterates 1 to 2. Swap nums[1] with nums[1] (1), add 1 to seen, recurse. Then swap nums[2] with nums[1] (2), add 2 to seen, recurse. Duplicate 1 at i=2 skipped due to seen.Final Answer:
Option C -> Option CQuick Check:
Output matches expected unique permutations in lex order [OK]
Hint: Sort input and skip duplicates with seen set [OK]
Common Mistakes:
- Misordering output permutations due to swap order
4. You are given a partially filled 9x9 grid where each row, column, and 3x3 sub-box must contain digits 1 through 9 without repetition. Which algorithmic approach guarantees finding a valid solution if one exists?
easy
Solution
Step 1: Understand problem constraints
The problem requires filling cells respecting row, column, and box constraints, which is a classic constraint satisfaction problem.Step 2: Identify algorithm that guarantees solution
Backtracking with constraint propagation prunes invalid choices early, and heuristic ordering reduces branching, ensuring completeness and efficiency.Final Answer:
Option D -> Option DQuick Check:
Constraint propagation + heuristic ordering is standard for Sudoku solvers [OK]
Hint: Constraint satisfaction problems need backtracking with pruning [OK]
Common Mistakes:
- Assuming greedy or BFS alone can solve Sudoku efficiently
5. 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