Top 3 Backtracking Interview Questions
Browse 3 real-world technical and behavioral interview questions about Backtracking. Review scenarios, edge cases, and architectural best practices.
Count the ways to place N queens on an N by N board so that no two attack each other.
One queen per row is forced, so search row by row and keep sets of used columns, used sums and used differences to reject a conflict before recursing. The anti-diagonal is the row plus column and the main diagonal the row minus column, and that difference must be shifted into range, not reduced with an absolute value.
Generate every permutation of an array that may contain duplicates, then tell me how large the search tree is
Backtracking builds each candidate incrementally and undoes the last choice on return; duplicates are suppressed by sorting and skipping a repeated value whose identical predecessor is unused. The tree holds under e times n factorial nodes, so pruning only pays when it removes subtrees near the root. It also connects recursion to the point an interviewer is testing.
You are given a grid of letters and a word. When do you stop searching, and what stops you revisiting the same cell?
You stop on four conditions and the success check has to come first, before bounds or character comparison. Revisiting is prevented per path rather than globally: a cell is marked when the search enters it and unmarked when the search leaves it, because a cell that ruins one candidate path has to remain available to a different one.