Top 3 Pruning Interview Questions

Browse 3 real-world technical and behavioral interview questions about Pruning. Review scenarios, edge cases, and architectural best practices.

Related Topics:Backtracking Recursion Search

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.

hardcoding

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.

mediumcoding

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.

mediumcoding