Catch Me If You Can: Optimal Pursuer Movement on a Grid
Interview Experience
Problem
A pursuer and a target move on an N x M grid. They alternate turns — pursuer moves first. Each turn, a player may move to any orthogonally adjacent cell or stay in place. The pursuer catches the target if they occupy the same cell at the end of any turn.
Given the grid dimensions, starting positions, and a maximum number of turns T, determine the minimum number of turns for the pursuer to guarantee a catch, or return -1 if impossible within T turns.
python
def min_turns_to_catch(
n: int, m: int,
pursuer: tuple[int, int],
target: tuple[int, int],
T: int
) -> int:
pass
**Input**: n=4, m=4, pursuer=(0,0), target=(3,3), T=10
Output: 6
# Manhattan distance = 6; pursuer closes one step per turn if target runs away
**Input**: n=2, m=2, pursuer=(0,0), target=(1,1), T=3
Output: 2
Follow-ups
- How does BFS on a game-state space
(pursuer_pos, target_pos, turn)apply here? - If the target moves optimally to escape, does Manhattan distance still give the correct answer?
- How would you extend this to multiple pursuers?
- What changes if the grid has obstacles that block movement?
Full Details
Problem
A pursuer and a target move on an N x M grid. They alternate turns — pursuer moves first. Each turn, a player may move to any orthogonally adjacent cell or stay in place. The pursuer catches the target if they occupy the same cell at the end of any turn.
Given the grid dimensions, starting positions, and a maximum number of turns T, determine the minimum number of turns for the pursuer to guarantee a catch, or return -1 if impossible within T turns.
python
def min_turns_to_catch(
n: int, m: int,
pursuer: tuple[int, int],
target: tuple[int, int],
T: int
) -> int:
pass
**Input**: n=4, m=4, pursuer=(0,0), target=(3,3), T=10
Output: 6
# Manhattan distance = 6; pursuer closes one step per turn if target runs away
**Input**: n=2, m=2, pursuer=(0,0), target=(1,1), T=3
Output: 2
Follow-ups
- How does BFS on a game-state space
(pursuer_pos, target_pos, turn)apply here? - If the target moves optimally to escape, does Manhattan distance still give the correct answer?
- How would you extend this to multiple pursuers?
- What changes if the grid has obstacles that block movement?
About This Question
This is a candidate experience report from a ziphq interview during the phone round.
It covers the following topics: Phone, Graph, Coding, Onsite, Matrix .