Round 1
Questions: You are given an infinite size chess board (coordinates vary from -inf to +inf), and a knight initially at a given start point. You need to tell the minimum number of moves required for a knight to reach a given end point. (NO further constraints were provided even after asking)
Part 2: You are also given a list of blocked points where the knight can't go.
Solution:
- For part 1, the solution involves using a simple BFS (Breadth-First Search) approach, utilizing a map to track points and the number of moves required to reach them, since you can't define any grid here.
- For part 2, while considering the neighbor points in the BFS solution, an additional condition should be added to check if the neighbor belongs to the blocked points.
TWIST: This solution will not work if the endpoint is surrounded by blocked points from all sides, making it impossible for the knight to reach the endpoint. In an infinite grid, new neighbors will continuously be added to the queue, leading to an infinite loop without a grid size to limit it.
Candidate's Approach
The candidate proposed using BFS to explore the knight's movements on an infinite chessboard. They recognized the need to track visited points and the number of moves taken. However, they encountered a challenge when considering blocked points, realizing that simply checking for blocked neighbors would not suffice if the endpoint was surrounded by blocks, leading to an infinite search loop.
Interviewer's Feedback
No feedback provided.