N-Queens
Solve the N-Queens puzzle, where $N$ queens must be placed on an $N \times N$ chessboard such that no two queens attack each other. Return all distinct solutions. Use Backtracking.
Why Interviewers Ask This
Stripe asks this to evaluate a candidate's mastery of recursive backtracking and constraint satisfaction under pressure. They specifically look for the ability to visualize board state changes, manage complex indexing without off-by-one errors, and optimize pruning strategies to avoid unnecessary computation on large N values.
How to Answer This Question
1. Clarify Constraints: Immediately ask about input size limits (e.g., N=8 vs N=12) and expected output format to gauge performance requirements.
2. Define State: Explain your representation of the board, such as using three boolean arrays for columns and diagonals instead of a full matrix to achieve O(1) conflict checks.
3. Outline Backtracking Logic: Describe the recursive function where you iterate through rows, attempting to place a queen in valid columns, then recursing to the next row.
4. Pruning Strategy: Detail how you skip invalid placements immediately based on column or diagonal conflicts before making the recursive call.
5. Optimization Discussion: Propose bit manipulation techniques if N is large, demonstrating awareness of space-time trade-offs relevant to Stripe's high-throughput systems.
Key Points to Cover
- Demonstrating O(N^2) space optimization using sets instead of a 2D array
- Explaining the logic for calculating unique diagonal indices (row - col and row + col)
- Clearly articulating the base case and the recursive step structure
- Discussing pruning techniques to eliminate invalid branches early
- Mentioning bit manipulation as an advanced optimization for performance
Sample Answer
To solve the N-Queens problem efficiently, I would first clarify the constraints with the interviewer, as the solution complexity grows exponentially. My approach uses depth-first search with backtracking. Instead of mai…
Common Mistakes to Avoid
- Using a full 2D grid for state tracking, leading to inefficient O(N^2) lookups per placement
- Failing to handle diagonal index calculations correctly, causing false positives in conflict detection
- Not resetting the board state after recursion returns, resulting in incorrect subsequent solutions
- Ignoring edge cases like N=1 or N=2 where no solution exists or is trivial
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.