Practice
1. Consider the following code snippet for counting beautiful arrangements. What is the final output when
n = 2?easy
Solution
Step 1: Trace backtrack calls for n=2
Positions: 1 and 2. At pos=1, try nums 1 and 2. Both satisfy divisibility. For pos=2, remaining number also satisfies divisibility.Step 2: Count valid permutations
Permutations: [1,2] and [2,1] both valid, total count = 2.Final Answer:
Option C -> Option CQuick Check:
Both permutations satisfy conditions, so output is 2 [OK]
Hint: Check all permutations for small n manually [OK]
Common Mistakes:
- Off-by-one in position indexing
- Counting invalid permutations
2. You are given an array of integers and need to find the lexicographically next greater permutation of its elements. Which approach guarantees finding this next permutation in optimal time without generating all permutations?
easy
Solution
Step 1: Understand the problem requirement
The problem asks for the lexicographically next greater permutation, which requires finding the next sequence just larger than the current one.Step 2: Identify the optimal approach
The approach scanning from the end to find a pivot where the sequence stops increasing, swapping with the smallest greater element on the right, then reversing the suffix guarantees the next permutation in O(n) time without generating all permutations.Final Answer:
Option A -> Option AQuick Check:
Brute force is correct but inefficient; DP and greedy do not guarantee correct next permutation [OK]
Hint: Next permutation uses pivot-swap-reverse pattern [OK]
Common Mistakes:
- Thinking brute force is optimal
- Using greedy from start fails on suffix order
3. You need to generate all unique permutations of an array that may contain duplicate elements. Which approach guarantees generating all unique permutations efficiently without producing duplicates during generation?
easy
Solution
Step 1: Understand the problem constraints
The problem requires generating all unique permutations of an array with duplicates, so duplicates must be avoided during generation to be efficient.Step 2: Evaluate approaches
Greedy algorithms do not guarantee all permutations; DP is not suitable here; generating all permutations and filtering duplicates is correct but inefficient. Backtracking with sorting and skipping duplicates during recursion ensures duplicates are pruned early.Final Answer:
Option B -> Option BQuick Check:
Backtracking with duplicate skipping is the standard optimal approach [OK]
Hint: Skip duplicates during backtracking after sorting [OK]
Common Mistakes:
- Thinking greedy or DP can generate unique permutations efficiently
4. Consider the following buggy code snippet for restoring IP addresses. Which line contains the subtle bug that causes invalid IP addresses to be included?
def restore_ip_addresses(s: str) -> List[str]:
res = []
stack = [(0, [])]
while stack:
start, path = stack.pop()
if len(path) == 4:
if start == len(s):
res.append(".".join(path))
continue
remaining_segments = 4 - len(path)
remaining_chars = len(s) - start
if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:
continue
for length in range(1, 4):
if start + length > len(s):
break
segment = s[start:start+length]
# Bug: Missing check for leading zeros
if length == 3 and int(segment) > 255:
continue
stack.append((start + length, path + [segment]))
return res
medium
Solution
Step 1: Identify missing validation
The code lacks a check to reject segments with leading zeros like '00' or '01', which are invalid.Step 2: Confirm other checks are correct
Check for segment > 255 and pruning are present and correct; appending to stack is correct.Final Answer:
Option A -> Option AQuick Check:
Missing leading zero check allows invalid IP segments [OK]
Hint: Leading zero check is mandatory to avoid invalid IPs [OK]
Common Mistakes:
- Forgetting leading zero validation
- Misplacing pruning conditions
5. Suppose you want to modify the palindrome partitioning algorithm to allow reuse of substrings in partitions (i.e., substrings can appear multiple times in different partitions). Which change to the algorithm is necessary to correctly handle this variant without losing valid partitions or causing duplicates?
hard
Solution
Step 1: Understand reuse requirement
Reusing substrings means substrings can appear multiple times in different partitions, so path management must allow multiple uses.Step 2: Identify necessary algorithm change
Memoizing palindrome checks improves efficiency by avoiding repeated palindrome computations, while backtracking logic remains unchanged to generate all valid partitions.Final Answer:
Option A -> Option AQuick Check:
Memoization optimizes palindrome checks without affecting partition generation correctness [OK]
Hint: Memoize palindrome checks to optimize without changing backtracking [OK]
Common Mistakes:
- Assuming popping affects substring reuse
- Using visited sets that block valid reuse
- Resetting path incorrectly losing partitions