Practice
1. You need to generate all combinations of balanced parentheses pairs for a given number
n. Which algorithmic approach guarantees generating only valid sequences without generating invalid ones first?easy
Solution
Step 1: Understand problem constraints
We want to generate all valid parentheses sequences without generating invalid ones first.Step 2: Analyze approaches
Brute force generates all sequences including invalid ones, greedy fails to generate all valid sequences, DP counts sequences but does not generate them. Backtracking with pruning adds '(' or ')' only when valid, thus generating only valid sequences.Final Answer:
Option B -> Option BQuick Check:
Backtracking with pruning avoids invalid sequences [OK]
Hint: Backtracking prunes invalid sequences early [OK]
Common Mistakes:
- Thinking greedy can generate all valid sequences
- Confusing counting with generating sequences
2. You need to find the
k-th lexicographically smallest permutation of numbers from 1 to n. Which approach guarantees an optimal solution without generating all permutations explicitly?easy
Solution
Step 1: Understand the problem constraints
The problem requires finding the k-th permutation without enumerating all permutations, which is infeasible for large n.Step 2: Identify the approach that uses factorial number system
Using precomputed factorials, we can determine the index of each digit in the permutation directly, avoiding full enumeration.Final Answer:
Option B -> Option BQuick Check:
Factorial-based direct computation is optimal and avoids timeouts [OK]
Hint: Factorials let you jump directly to the k-th permutation [OK]
Common Mistakes:
- Thinking greedy swaps can find k-th permutation efficiently
- Assuming DP is needed here
- Trying to generate all permutations for large n
3. Consider the following BFS-based code snippet for removing invalid parentheses:
from collections import deque
def is_valid(s: str) -> bool:
count = 0
for c in s:
if c == '(': count += 1
elif c == ')':
count -= 1
if count < 0:
return False
return count == 0
def remove_invalid_parentheses_bfs(s: str):
res = []
visited = set([s])
queue = deque([s])
found = False
while queue:
size = len(queue)
for _ in range(size):
curr = queue.popleft()
if is_valid(curr):
res.append(curr)
found = True
if found:
continue
for i in range(len(curr)):
if curr[i] not in ('(', ')'):
continue
next_str = curr[:i] + curr[i+1:]
if next_str not in visited:
visited.add(next_str)
queue.append(next_str)
return res
print(remove_invalid_parentheses_bfs("()())()"))easy
Solution
Step 1: Trace BFS levels for input "()())()"
Initial string is invalid. BFS removes one parenthesis at each position generating candidates. The first valid strings found are "()()()" and "(())()".Step 2: Confirm both valid strings are collected
Since BFS stops adding new states after finding valid strings at current level, both minimal removal results are returned.Final Answer:
Option B -> Option BQuick Check:
Both minimal valid strings are returned [OK]
Hint: BFS returns all minimal valid strings at first valid level [OK]
Common Mistakes:
- Returning only one valid string
- Returning original invalid string
- Missing one minimal valid string
4. If the problem changes so that numbers can be reused multiple times in the permutation (i.e., repetition allowed), which modification to the algorithm is correct?
hard
Solution
Step 1: Understand repetition impact
Allowing reuse breaks the factorial number system assumption because permutations count changes drastically.Step 2: Identify correct approach
Backtracking with early stop can generate permutations with repetition and find the k-th one, as direct factorial indexing is invalid.Final Answer:
Option D -> Option DQuick Check:
Factorial indexing fails with repetition; backtracking is correct fallback [OK]
Hint: Factorial indexing requires unique elements; repetition breaks it [OK]
Common Mistakes:
- Trying to reuse factorial indexing without adjustment
- Ignoring repetition changes permutation count
- Assuming greedy works for k-th permutation with repetition
5. Suppose the Word Search problem is modified so that the same cell can be used multiple times in forming the word. Which modification to the backtracking algorithm correctly handles this change?
hard
Solution
Step 1: Understand new constraint
Cells can be reused multiple times, so marking visited cells to prevent reuse is no longer needed.Step 2: Modify algorithm accordingly
Removing in-place marking allows revisiting cells, correctly reflecting the relaxed constraint.Step 3: Evaluate other options
Keeping marking or using global visited set prevents reuse incorrectly; DP is not suitable here.Final Answer:
Option C -> Option CQuick Check:
Removing visited marking enables cell reuse as required [OK]
Hint: Relaxing constraints often means removing pruning steps [OK]
Common Mistakes:
- Keeping visited marking, causing false negatives
- Adding unnecessary global state