Recommended
Practice
1. You need to partition a string into substrings such that every substring is a palindrome. Which algorithmic approach guarantees finding all possible palindrome partitions efficiently by pruning invalid partitions early?
easy
Solution
Step 1: Understand problem requirements
The problem requires generating all palindrome partitions, not just counting or finding one.Step 2: Identify suitable algorithm
Backtracking explores all partitions and prunes invalid ones by checking palindrome substrings dynamically, ensuring completeness and correctness.Final Answer:
Option A -> Option AQuick Check:
Backtracking with palindrome checks finds all partitions [OK]
Hint: Backtracking explores all partitions with palindrome pruning [OK]
Common Mistakes:
- Assuming greedy longest palindrome picks all partitions
- Confusing counting palindromes with generating partitions
- Ignoring palindrome checks in BFS
2. Given the following code for palindrome partitioning, what is the final output when input string
s = "aab" is passed to partition(s)?
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[:])
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
easy
Solution
Step 1: Trace backtrack calls for s="aab"
Start=0, path=[]; check substrings: "a" (palindrome), "aa" (palindrome), "aab" (not palindrome). Explore "a" -> backtrack(1, ["a"]), then "a" -> backtrack(2, ["a", "a"]), then "b" -> backtrack(3, ["a", "a", "b"]) adds ["a", "a", "b"] to result.Step 2: Explore "aa" substring
From start=0, choose "aa" -> backtrack(2, ["aa"]), then "b" -> backtrack(3, ["aa", "b"]) adds ["aa", "b"] to result.Final Answer:
Option C -> Option CQuick Check:
Both partitions contain only palindromes and cover entire string [OK]
Hint: Trace recursion and palindrome checks carefully [OK]
Common Mistakes:
- Including non-palindromic substrings like "ab"
- Missing one valid partition
- Returning partial partitions
3. Examine the following buggy code snippet for Expression Add Operators. Which line contains the subtle bug that causes incorrect results on inputs with leading zeros?
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)):
# Bug: missing leading zero check
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
medium
Solution
Step 1: Identify handling of leading zeros
The code lacks the check 'if i != index and num[index] == '0': break' which prevents invalid operands like "05".Step 2: Confirm bug location
This missing check is critical and should be placed before parsing curr_str to avoid invalid expressions.Final Answer:
Option A -> Option AQuick Check:
Missing leading zero check causes invalid operands [OK]
Hint: Leading zero check missing causes invalid operands [OK]
Common Mistakes:
- Confusing backtracking cleanup lines as bug
- Thinking substring extraction is buggy
4. What is the time complexity of the optimal in-place next permutation algorithm for an input array of length n?
medium
Solution
Step 1: Identify the main operations
The algorithm scans from the end to find the pivot (O(n)), then scans again to find the swap element (O(n)), and finally reverses the suffix (O(n)).Step 2: Sum up the operations
All steps are linear scans or swaps, so total time complexity is O(n).Final Answer:
Option A -> Option AQuick Check:
No sorting or factorial generation involved, linear scans only [OK]
Hint: Next permutation scans array linearly multiple times [OK]
Common Mistakes:
- Confusing suffix reversal with sorting
- Assuming factorial due to permutations
5. Suppose the problem is modified so that digits can be repeated any number of times (reuse allowed), and you want to generate all letter combinations of length n from the given digits. Which modification to the algorithm correctly handles this reuse scenario?
hard
Solution
Step 1: Understand reuse requirement
Allowing reuse means digits can be chosen multiple times to build combinations of length n.Step 2: Identify correct approach
Backtracking can be modified to not increment the digit index after choosing a letter, allowing reuse until length n is reached.Step 3: Why other options fail
Iterative queue approach as-is assumes fixed digit positions; DP without reuse does not handle repeated digits; sorting and picking once per digit ignores reuse.Final Answer:
Option A -> Option AQuick Check:
Backtracking with flexible index handles reuse elegantly [OK]
Hint: Backtracking index controls reuse by not advancing [OK]
Common Mistakes:
- Trying to reuse digits in iterative approach without index control
- Ignoring reuse in DP or sorting