Cat and Mouse

Cat and Mouse

What is this problem about?

The Cat and Mouse interview question is a complex graph-based game. A Mouse and a Cat are on a graph. The Mouse starts at node 1, the Cat at node 2, and node 0 is the "Hole." Players take turns moving to adjacent nodes. The Mouse wins if it reaches the Hole. The Cat wins if it catches the Mouse (same node). If the game continues indefinitely, it's a Draw. This Cat and Mouse coding problem is a pinnacle of game theory simulation.

Why is this asked in interviews?

This HARD problem is used by Google and Microsoft to test for extreme proficiency in dynamic programming and graph theory. It requires the Minimax algorithm or Topological Sort on game states. It tests how you handle "Draws" (cycles in the game graph), which is much harder than simple win/loss scenarios.

Algorithmic pattern used

This utilizes the Math, Graph, Memoization, Topological Sort, Game Theory, Dynamic Programming interview pattern.

• State: (mouse_pos, cat_pos, turn).
• Winning/Losing: Start with the known end states (Mouse at 0 is a Mouse win; Mouse == Cat is a Cat win).
• Propagation: Use a BFS-like approach (Topological Sort) to propagate these wins/losses backward to previous states. A state is a "win" if there's a move to a "loss" for the opponent. A state is a "loss" if all moves lead to a "win" for the opponent.

Example explanation

Graph: 0-1, 1-2, 2-0 (A triangle)

• Mouse at 1, Cat at 2.
• Mouse moves to 0. Mouse Wins. But if the graph was 1-3, 2-3, and the Hole was far away, the Cat could block the only path to the Hole, potentially leading to a Draw or a Cat win.

Common mistakes candidates make

• Simple DFS: Standard recursion will fail because of the potential for infinite loops (Draws).
• Ignoring Cat's restriction: Forgetting that the Cat usually cannot enter node 0 (the Hole).
• State Space: Not correctly accounting for the "Turn" in the state, which is necessary because the best move depends on whose turn it is.

Interview preparation tip

For game problems with cycles, think about "retrograde analysis." Start from the end (the result) and work your way back to the starting positions. This is often more reliable than forward-searching with DFS.