Recommended
Practice
1. You need to place
n queens on an nxn chessboard so that no two queens threaten each other (no two queens share the same row, column, or diagonal). Which algorithmic approach guarantees finding all valid solutions efficiently by pruning invalid partial placements early?easy
Solution
Step 1: Understand problem constraints
The problem requires placing queens so none attack each other, which involves checking columns and diagonals.Step 2: Identify algorithm that prunes invalid states early
Backtracking with pruning efficiently avoids exploring invalid partial solutions by tracking attacked columns and diagonals.Final Answer:
Option A -> Option AQuick Check:
Backtracking prunes invalid states early [OK]
Hint: Pruning columns and diagonals is key to efficient search [OK]
Common Mistakes:
- Thinking greedy placement always works
- Assuming DP applies directly
- Confusing BFS with pruning
2. 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
3. You are given a 2D grid of letters and a list of words. You need to find all words that can be formed by sequentially adjacent letters (horizontally or vertically) without reusing the same cell in a single word. Which algorithmic approach best guarantees an efficient solution for this problem?
easy
Solution
Step 1: Understand problem constraints
The problem requires searching multiple words in a grid with adjacency and no reuse constraints, which is expensive if done naively.Step 2: Identify efficient pruning technique
Backtracking with a Trie allows pruning search paths early when no word prefix matches, avoiding redundant searches.Final Answer:
Option C -> Option CQuick Check:
Trie pruning reduces search space drastically compared to naive DFS [OK]
Hint: Trie + backtracking prunes invalid prefixes early [OK]
Common Mistakes:
- Thinking greedy or DP alone can solve adjacency constraints efficiently.
4. What is the time complexity of the optimal palindrome partitioning algorithm that uses backtracking with dynamic palindrome checks by expanding around centers for palindrome verification on a string of length
n?medium
Solution
Step 1: Identify number of partitions
There are up to 2^(n-1) ways to partition a string of length n.Step 2: Analyze palindrome check cost
Using expand around center, palindrome check per substring is O(n) worst case, done during backtracking.Final Answer:
Option D -> Option DQuick Check:
Combining partitions and palindrome checks yields O(n * 2^n) [OK]
Hint: Partitions grow exponentially; palindrome checks add linear factor [OK]
Common Mistakes:
- Assuming palindrome checks are O(1) without DP
- Confusing total partitions with time complexity
- Ignoring recursion stack space
5. Consider the following code snippet intended to generate unique permutations of an array with duplicates. Which line contains a subtle bug that causes duplicate permutations to be generated?
def permuteUnique(nums):
nums.sort()
res = []
def backtrack(start=0):
if start == len(nums):
res.append(nums[:])
return
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1)
nums[start], nums[i] = nums[i], nums[start]
backtrack()
return resmedium
Solution
Step 1: Analyze duplicate skipping condition
The condition 'if i > start and nums[i] == nums[i-1]: continue' attempts to skip duplicates but does not consider whether the previous duplicate was used, causing some duplicates to be missed.Step 2: Verify other lines
Sorting input is correct; swapping before and after recursion is correct; iteration over indices is standard. The bug is in the duplicate skipping logic.Final Answer:
Option A -> Option AQuick Check:
Incorrect duplicate skipping causes duplicate permutations [OK]
Hint: Skipping duplicates requires tracking usage, not just comparing adjacent elements [OK]
Common Mistakes:
- Skipping duplicates by only comparing adjacent elements without usage tracking