Common Patterns
Backtracking
Systematic search with pruning — how backtracking powers solutions to constraint satisfaction, configuration, and combinatorial problems.
Some problems just can't be solved with a clean formula. You need to try things, see if they work, and undo them when they don't. That's backtracking in a nutshell.
In AI coding interviews, backtracking shows up a lot through problems like configuration generators, scheduling problems, puzzle solvers, and anything where you're searching through a combinatorial space for valid arrangements. These problems are perfect for this format because the solution structure is complex enough to be interesting but follows a recognizable template that you and the AI can collaborate on effectively.
The easiest way to picture it is you're walking a maze, pick a direction, and go until you hit a wall, then back up to the last fork and try another path. That's the whole pattern. Most backtracking problems are just dressed-up versions of this same thing.
You don't need to have backtracking memorized before walking into the interview. Interviewers want to see that you can recognize when a problem calls for systematic search, articulate that to the AI, and verify that the generated solution actually prunes correctly.
Recognizing the pattern
Backtracking usually announces itself in the prompt. If the problem says "find all valid configurations" or "generate all arrangements satisfying these rules," it's almost certainly backtracking. Scheduling problems where resources have constraints, configuration generators where options depend on previous choices, puzzle solvers with rules that restrict placement, these all follow the pattern.
These problems tend to fall into a few categories. Once you've seen each shape once, the rest is mostly recognition:
- Placement problems: arrange items in a grid or structure so they don't conflict. N-Queens, Sudoku, crossword puzzle generators.
- Scheduling and assignment: assign tasks to resources, time slots to events, or workers to shifts, subject to constraints like availability and capacity.
- Configuration generation: produce all valid configurations of a system. Think feature flag combinations that satisfy dependency rules, or network topologies that meet connectivity requirements.
- Path and partition problems: find paths through a maze, partition sets into groups meeting certain criteria, or generate all valid orderings of tasks with dependencies.
The common thread is you're building a solution incrementally, and at each step you can check whether you've already violated a constraint. If you have, there's no point continuing down that path.
Search with early termination
The backtracking template
Worked example: N-Queens
Constraint propagation: making pruning aggressive
Prompting the AI
Verifying the AI's code
When to use vs. alternatives
What interviewers expect
Putting it together
Purchase Premium to Keep Reading
Unlock this article and so much more with Hello Interview Premium
Reading Progress
On This Page