Given a fixed-size chess board, find the shortest path between two positions (e.g., for a knight or similar chess piece).
Given a fixed-size chess board, find the shortest path between two positions (e.g., for a knight or similar chess piece). You must implement the solution from scratch including main(), custom function signatures with input/output, and your own test cases. The base problem uses a fixed board size. Candidate must discuss tradeoffs between BFS and DFS before choosing an approach.
What if some cells on the board are blocked/impassable? How would you modify your solution?
What if the chess board is infinitely large? How would you handle that?
| Approach | Notes |
|---|---|
| DFS | Does not guarantee shortest path; may explore deep paths unnecessarily. Simpler to implement recursively but wrong for shortest-path problems. |
| BFS with symmetry optimization | Convert (x, y) to first quadrant using symmetry to reduce state space; also allow slightly negative coordinates (e.g., -2) to handle edge cases near the origin. Harder to think of under interview pressure. |
Common mistakes: Adding 'static' to the outer class definition in Java caused a syntax error that took significant time to debug; the interviewer had to hint at the fix.; Being out of practice writing a full Java file from scratch (main(), class definitions, test cases) led to avoidable syntax errors under time pressure.
Interviewer hints: The interviewer was largely silent/muted during the coding portion and only became interactive during the follow-up discussion phase.; The interviewer helped point out the Java 'static outer class' syntax error when the candidate was stuck.
What passers do: Candidate briefly analyzed DFS vs. BFS tradeoffs before committing to BFS, which the interviewer expected as part of the problem setup.; Candidate achieved a bug-free solution with ~15 minutes remaining, leaving enough time to discuss both follow-ups.