Skip to content
Tech Interview Prep
Technical interview guide

Backtracking

Recursive brute-force search with early pruning: build a partial solution, and abandon it the moment it can't possibly work.

Read
42 min
Practice MCQs
25
Interview Q&A
25
Edition
v7
Editorial status
Reviewed

Scope: Language-neutral, with generator and recursion behaviour cited from CPython 3.14.

Curated: · Written: · Reviewed:

25 questions

MCQ-2This Python 3 function is meant to return every permutation of `nums`. Called as `permute([1, 2])`, what does it return? ```python def permute(nums): res, path = [], [] def dfs(): if len(path) == len(nums): res.append(path[:]) return for n in nums: if n in path: continue path.append(n) dfs() dfs() return res ```
MCQ-1The generator below is meant to emit every permutation of [1, 2, 3]. It is called once with `used = {1: False, 2: False, 3: False}`, `path = []`, and an empty `out` list. ```python def permute(path, used, out): if len(path) == 3: out.append(list(path)) return for x in (1, 2, 3): if used[x]: continue used[x] = True path.append(x) permute(path, used, out) path.pop() # used[x] = False <- missing ``` What does `out` hold when the call returns?
MCQ-16An 8-queens solver keeps one shared `cols` list, appending a column before recursing and popping it after: ```python def solve(cols): if len(cols) == 8: solutions.append(cols) return for c in range(8): if safe(cols, c): cols.append(c) solve(cols) cols.pop() ``` It reports 92 solutions, but `print(solutions)` prints 92 empty lists. Which change records the 92 boards while keeping the single shared `cols` list?
MCQ-10A candidate writes a swap-based generator for all permutations of a distinct array of length n. It appends the working array when the recursion index reaches n, and swaps a[i] with a[j] before and after each recursive call. A reviewer deletes the second swap to save a line. For n = 3 the generator still reaches the base case six times, but it emits [1,2,3], [1,3,2], [3,1,2], [3,2,1], [1,2,3], [1,3,2]. Which statement explains the output?
MCQ-8A candidate writes two recursive generators over the same list of n distinct integers: one emits every k-combination, the other every permutation. The combinations generator passes a startIndex down each call; the permutations generator instead keeps a used array. In review, the candidate is asked why the two searches need different bookkeeping. Which statement is the reason?
MCQ-12A `combine(n, k)` generator called with n=5, k=2 returns 20 tuples instead of the expected 10, because the recursion loops over the whole candidate list at every level and only checks the length at the base case. Which change removes the duplicates, and what does it enforce?
MCQ-11The function below is meant to return every combination of `candidates` that sums to `target`, where each candidate may be reused any number of times. Run with `candidates = [2, 3, 5, 7]` and `target = 10`, what does it actually return? ```python def combine(candidates, target): res = [] def backtrack(start, remaining, path): if remaining == 0: res.append(path[:]) return if remaining < 0: return for i in range(start, len(candidates)): path.append(candidates[i]) backtrack(i + 1, remaining - candidates[i], path) path.pop() backtrack(0, target, []) return res ```
MCQ-3A backtracking subset generator runs `for i in range(start, len(nums)):` and inside the loop applies `if i > start and nums[i] == nums[i - 1]: continue`. On `nums = [3, 1, 3]` it still emits duplicate subsets; adding `nums.sort()` at the top removes them. What does sorting change that makes the check work?
MCQ-23A team's `subsetsWithDup` sorts the input and skips duplicates with a `nums[i] == nums[i-1]` check in its backtracking loop. Their suite runs 200 random inputs of length ≤ 6 and asserts only that each returned subset is sorted and contains no repeated element; all 200 pass. A reviewer reports that on `[1,2,2]` the function returns only 4 subsets (`[]`, `[1]`, `[1,2]`, `[2]`) and is missing results. Which single assertion, added to the suite, would have caught this bug without also failing on a correct implementation?
MCQ-13A word-search function walks an m×n grid with DFS, adding every cell it enters to one `visited` set that is never cleared. On the grid `[['A','B','C','E'],['S','F','E','S'],['A','D','E','E']]` it returns false for `ABCESEEEFS`, which is present. What is the cause?
MCQ-9A backtracking N-Queens solver for an 8×8 board keeps three occupancy arrays: `cols[c]`, `d1[r - c + 7]` for one diagonal family, and `d2[r + c]` for the other. A refactor broke the placement routine, it now sets `cols[c]` and `d1[r - c + 7]` but never sets `d2[r + c]`, while the conflict test still reads all three arrays. Each option lists the queens the solver has placed in rows 0–3, written as (row, column) pairs. Which board does the solver accept even though it contains an attacking pair?
MCQ-4A backtracking solver colors the vertices of a graph in the order A, B, C, D using three colors {1,2,3}. The edges are A-B, A-C, B-C, A-D, B-D, C-D. It checks each edge as soon as both endpoints are colored and backtracks immediately on a conflict. Count one node for each partial assignment that passes every check among its colored vertices; the empty root is not counted. How many nodes does the search visit?
MCQ-5A Sudoku solver represents each cell's candidates as a 9-bit mask. On assigning a digit to a cell, it clears that digit's bit in the masks of every peer in the same row, column, and box. On backtracking, it restores only the assigned cell's mask to include the digit again. Running it on a 17-given puzzle with a known unique solution returns 'no solution' after exploring 1,234 nodes. Which change fixes the solver?
MCQ-6A backtracking solver assigns meetings to time slots. After constraint propagation, five meetings remain unassigned: | Meeting | Remaining slots | Unassigned meetings it constrains | |---|---|---| | M1 | Mon, Tue, Wed, Thu | 2 | | M2 | Mon, Tue | 3 | | M3 | Mon, Tue, Wed | 5 | | M4 | Mon, Tue | 4 | | M5 | Wed, Thu | 1 | The solver selects the next variable by minimum remaining values (MRV), breaking ties with the degree heuristic (the variable that constrains the most unassigned meetings). Which meeting does it assign next?
MCQ-20A team runs a backtracking solver for 6-queens. The full search finds 4 solutions. They add a symmetry-breaking rule: the first queen is restricted to columns 0, 1, and 2 of row 0, and they will double the restricted count to recover the full count. They run the restricted solver. Which outcome should they expect?
MCQ-19A 0/1 knapsack search maximises value under capacity 10 and uses branch and bound with an incumbent. At one node, 10 units of capacity are still free, none of the three remaining items has been taken yet, and the incumbent, the best complete solution verified so far, is worth 36. The remaining items are X (weight 6, value 20), Y (weight 5, value 19) and Z (weight 4, value 17). The bound function packs the remaining items greedily by value density without splitting any of them: it takes Z (4.25 per unit), then Y (3.8 per unit), and X no longer fits, so the bound is 17 + 19 = 36. The node is pruned because 36 is not greater than the incumbent. What does that prune do?
MCQ-14A team counts monotone paths from the top-left to the bottom-right of a 20×20 grid with blocked cells. Their plain backtracking version finishes in 12 s. They add @cache keyed on (row, col, path), where path is the tuple of cells visited so far; the memoised version now takes 31 s and peaks at 2.4 GB. What explains the regression?
MCQ-25A team is selecting which of 60 candidate features to ship. Feature i has an integer cost c_i drawn from a wide range (values up to 10^9) and a value v_i, and the shipped set's total cost must not exceed a budget of 10^9. They write a memoised recursion keyed on (index, remaining budget). On a test instance the run is still going after an hour, the memo table holds only a few thousand entries, and instrumentation shows the recursion has visited on the order of 2^60 nodes. What does this tell the team about the memoisation?
MCQ-15A pricing service must answer two questions over a 24-item catalog with whole-dollar prices: (1) how many subsets of items total exactly $500, and (2) the list of those subsets. The current code enumerates all 2^24 subsets for both queries; each takes about 40 s. Which statement about the two queries is right?
MCQ-7A dedup job enumerates every subset of a 22-field schema and keeps those whose SHA-256 over the sorted field names equals a target digest. The run takes 1.7 s. Product wants the schema grown to 30 fields with the job still under 2 s. What should the team expect?
MCQ-24A nightly job finds the first ordering of 11 tasks that satisfies a precedence predicate. It finishes in 40 ms on the 8-task test fixture, but in production with 11 tasks the container is OOM-killed after about 30 s. The container's memory limit is fixed and cannot be raised. The loop is: ```python from itertools import permutations for p in list(permutations(tasks)): if valid(p): break ``` Which change lets the job finish?
MCQ-17A Python 3.12 worker runs a recursive backtracking search that makes exactly one recursive call per element of its input; staging runs with 200-element inputs pass. A production request arrives with a 4,000-element input, and the worker uses the default sys.getrecursionlimit(). What happens, and what is the right change?
MCQ-18A route planner searches a uniform tree with branching factor 10, and the goal always sits at depth 5. Each stored node costs 200 bytes, and the team caps frontier memory at 1 MB. They replace breadth-first search with iterative deepening. What does the new run cost?
MCQ-22A Python service runs a backtracking search over user-supplied constraint graphs. It defines NODE_BUDGET = 2_000_000 and a nodes counter, but the counter is incremented only when a complete solution is found. A crafted input expands 40 million nodes and pins one worker for 8 s before returning a solution; normal requests expand 100,000 nodes in 20 ms. Which change bounds the work for this endpoint?
MCQ-21A team ships a backtracking scheduler for 40 tasks with 8 candidate slots each, so the worst case is 8^40 nodes. With MRV ordering and forward checking, every production instance so far explores at most 3×10^4 nodes and returns in under 20 ms. A customer asks for a contractual guarantee that every instance finishes within 1 second. What is the correct response?