Recommended
Practice
1. You are given a numeric string and a target integer. You need to insert binary operators (+, -, *) between digits to form expressions that evaluate to the target. Which algorithmic approach guarantees finding all valid expressions efficiently while handling operator precedence and avoiding invalid operands like those with leading zeros?
easy
Solution
Step 1: Understand problem requirements
The problem requires exploring all ways to insert operators to reach a target, respecting operator precedence and avoiding invalid operands like those with leading zeros.Step 2: Identify suitable algorithm
Backtracking with pruning and operand parsing systematically explores all valid expressions, correctly handles precedence (especially multiplication), and prunes invalid paths early.Final Answer:
Option A -> Option AQuick Check:
Backtracking explores all valid expressions with pruning [OK]
Hint: Backtracking explores all operator insertions with pruning [OK]
Common Mistakes:
- Assuming greedy or DP can handle operator precedence and invalid operands
2. 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
3. Consider the following snippet from an optimized Sudoku solver using backtracking with heuristics. Given the board below, what is the length of candidates for the first empty cell chosen after sorting empties by candidate count?
Board:
[['5', '3', '.', '.', '7', '.', '.', '.', '.'],
['6', '.', '.', '1', '9', '5', '.', '.', '.'],
['.', '9', '8', '.', '.', '.', '.', '6', '.'],
['8', '.', '.', '.', '6', '.', '.', '.', '3'],
['4', '.', '.', '8', '.', '3', '.', '.', '1'],
['7', '.', '.', '.', '2', '.', '.', '.', '6'],
['.', '6', '.', '.', '.', '.', '2', '8', '.'],
['.', '.', '.', '4', '1', '9', '.', '.', '5'],
['.', '.', '.', '.', '8', '.', '.', '7', '9']]
Code snippet:
def get_candidates(r, c):
b = (r//3)*3 + c//3
return [ch for ch in '123456789' if ch not in rows[r] and ch not in cols[c] and ch not in boxes[b]]
empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
first_empty = empties[0]
candidates_len = len(get_candidates(first_empty[0], first_empty[1]))
candidates_len?easy
Solution
Step 1: Identify first empty cell after sorting
Check empties and compute candidates for each; the cell with fewest candidates is chosen first.Step 2: Calculate candidates for first empty cell (0,2)
Row 0 has {'5','3','7'}, column 2 has {'8'}, box 0 has {'5','3','6','9','8'}. Candidates are digits not in any of these sets: '1','2','4'. So length is 3.Final Answer:
Option B -> Option BQuick Check:
Counting candidates for (0,2) yields 3 [OK]
Hint: Count candidates by excluding row, column, box digits [OK]
Common Mistakes:
- Forgetting box constraints
- Miscounting candidates for first empty cell
4. You are given a 2D grid of characters and a target string. You need to determine if the string can be formed by sequentially adjacent cells (horizontally or vertically) without revisiting any cell. Which algorithmic approach best guarantees an optimal solution for this problem?
easy
Solution
Step 1: Understand problem constraints
The problem requires checking if a word can be formed by adjacent cells without reuse, which is a classic backtracking scenario.Step 2: Identify suitable algorithm
Backtracking with in-place marking efficiently explores all paths while preventing revisiting cells, guaranteeing correctness and optimal pruning.Final Answer:
Option A -> Option AQuick Check:
Backtracking explores all valid paths with pruning [OK]
Hint: Backtracking fits adjacency and no-reuse constraints [OK]
Common Mistakes:
- Assuming greedy or DP can solve adjacency constraints optimally
5. 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