Quick Overview

Solve guaranteed capture time in a finite turn-based graph pursuit game, including Jerry-first moves, staying, optimal adversarial play, and infinite evasion on cycles.

Find the Guaranteed Capture Time in a Turn-Based Graph Game

Company: ZipHQ

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

Tom and Jerry move on a finite undirected graph. Their starting vertices are given and both always know the current positions. Each second, Jerry moves first to a neighbor or stays; Tom then moves to a neighbor or stays. Capture occurs as soon as they occupy the same vertex. Assuming Tom minimizes capture time and Jerry maximizes it, return the smallest number of seconds in which Tom can **guarantee** capture, or -1 if Jerry can evade forever. Implement `guaranteed_capture_time(n: int, edges: int[][], tom: int, jerry: int) -> int`. ### Constraints & Assumptions - `1 <= n <= 50`; vertices are `0..n-1`. Edges are unique undirected pairs of distinct valid vertices. Disconnected graphs are allowed. - Each player may stay in place every turn. There are no blocked rooms beyond missing edges and no random choices after the initial positions are supplied. - If initial positions are equal, return 0. Otherwise, capture during either player's move in the first second counts as 1 second, and similarly for later seconds. - Both players choose optimally with full state knowledge. A move onto the other player causes immediate capture; there is no edge-crossing event between simultaneous moves because moves are sequential. - Finiteness alone does not guarantee capture. This explicit -1 outcome preserves the general-graph rules instead of silently assuming a tree or another missing restriction. ### Examples ```text n = 3, edges = [[0,1],[1,2]], tom = 0, jerry = 2 result = 2 ``` ```text n = 4, edges = [[0,1],[1,2],[2,3],[3,0]], tom = 0, jerry = 2 result = -1 ``` On the cycle, Jerry can maintain an escape indefinitely under these rules even though the graph is finite. The report describes a hint based on comparing BFS distances from the two starting points. Explain why those distances alone do not solve this unrestricted adversarial game, and what additional graph restriction or changed objective would be needed before relying on such a shortcut. Your function must solve the stated game, including cycles and infinite evasion. ```hint Include whose move is next A game state depends on both positions and the turn phase. A capture guarantee requires one successful choice for Tom but must survive every legal choice Jerry can make. ```

Overview: Solve guaranteed capture time in a finite turn-based graph pursuit game, including Jerry-first moves, staying, optimal adversarial play, and infinite evasion on cycles.

Read the full ZipHQ Software Engineer interview experience this question came from

Tom and Jerry move on a finite undirected graph. Their starting vertices are given and both always know the current positions. Each second, Jerry moves first to a neighbor or stays; Tom then moves to a neighbor or stays. Capture occurs as soon as they occupy the same vertex. Assuming Tom minimizes capture time and Jerry maximizes it, return the smallest number of seconds in which Tom can **guarantee** capture, or -1 if Jerry can evade forever. Implement `guaranteed_capture_time(n: int, edges: int[][], tom: int, jerry: int) -> int`. ### Constraints & Assumptions - `1 <= n <= 50`; vertices are `0..n-1`. Edges are unique undirected pairs of distinct valid vertices. Disconnected graphs are allowed. - Each player may stay in place every turn. There are no blocked rooms beyond missing edges and no random choices after the initial positions are supplied. - If initial positions are equal, return 0. Otherwise, capture during either player's move in the first second counts as 1 second, and similarly for later seconds. - Both players choose optimally with full state knowledge. A move onto the other player causes immediate capture; there is no edge-crossing event between simultaneous moves because moves are sequential. - Finiteness alone does not guarantee capture. This explicit -1 outcome preserves the general-graph rules instead of silently assuming a tree or another missing restriction. ### Examples ```text n = 3, edges = [[0,1],[1,2]], tom = 0, jerry = 2 result = 2 ``` ```text n = 4, edges = [[0,1],[1,2],[2,3],[3,0]], tom = 0, jerry = 2 result = -1 ``` On the cycle, Jerry can maintain an escape indefinitely under these rules even though the graph is finite. The report describes a hint based on comparing BFS distances from the two starting points. Explain why those distances alone do not solve this unrestricted adversarial game, and what additional graph restriction or changed objective would be needed before relying on such a shortcut. Your function must solve the stated game, including cycles and infinite evasion. ```hint Include whose move is next A game state depends on both positions and the turn phase. A capture guarantee requires one successful choice for Tom but must survive every legal choice Jerry can make. ```

Constraints

  • 1 <= n <= 50; unique undirected edges connect distinct vertices numbered 0 through n-1.
  • Disconnected graphs and empty edge lists are allowed.
  • Each second Jerry moves first, then Tom; either may move to a neighbor or stay.
  • Capture is immediate upon equal positions; initial equality returns 0 and later captures count their current second.
  • Tom minimizes guaranteed capture time, Jerry maximizes it; return -1 for indefinite evasion.

Examples

Input: (3, [[0, 1], [1, 2]], 0, 2)

Expected Output: 2

Explanation: Jerry can stay at endpoint 2 during second one; Tom approaches through 1 and captures in second two.

Input: (4, [[0, 1], [1, 2], [2, 3], [3, 0]], 0, 2)

Expected Output: -1

Explanation: Jerry can keep choosing a vertex outside Tom's closed neighborhood before each Tom move.

Hints

  1. Track both positions and the turn phase; Tom needs one successful choice, while a guarantee must survive every Jerry choice.

Loading coding console...

Show the approach

Approach

Represent a state by (phase, Tom vertex, Jerry vertex), where phase 0 means Jerry moves next and phase 1 means Tom moves next. Add staying to each vertex's legal move list. Equal-position states are terminal at distance zero in both phases. Distances count individual player moves, including a move that causes capture.

Work backward from all terminal states with a FIFO queue. At a Tom state, one winning successor suffices: its minimax distance is one plus the minimum successor distance. At a Jerry state, every legal successor must be winning: its minimax distance is one plus the maximum successor distance. Maintain a remaining-successor counter for each Jerry state. Because the graph is undirected, predecessor positions are obtained from the same neighbor-plus-stay lists. A resolved phase-0 state informs Tom predecessors; a resolved phase-1 state informs Jerry predecessors.

All terminal distances are zero. Queue processing is nondecreasing in distance: every newly resolved state gets the currently popped distance plus one. Therefore the first resolved successor of a Tom predecessor is a minimum, and the last required resolved successor of a Jerry predecessor is a maximum. This establishes the exact min/max recurrence inductively and resolves each state only once. For a Jerry state, the counter reaches zero only after all distinct legal choices have resolved. Unique edges and one explicit stay entry ensure each choice is counted once.

When the queue empties, an unresolved Tom state has no resolved successor, while an unresolved Jerry state retains at least one unresolved successor. Jerry can always choose such a successor and Tom cannot leave the unresolved set, so capture can be avoided forever. Conversely, a resolved state has a strategy forcing the terminal set with the computed finite bound. Thus unresolved states return -1, including starts in different components.

The initial state has Jerry to move. If the minimax capture distance is h individual moves, the capture second is ceil(h/2), implemented as (h+1)//2. This also returns zero for initial capture. Counting a possible immediate capture after either phase gives the same second for the two moves of that second. The ceiling function is monotone and commutes with finite minimum and maximum, so converting the optimal individual-move bound preserves the optimal guaranteed number of seconds.

For n vertices and m edges, there are 2nn states and O(n*(n+m)) transitions including stays. Every state and transition is processed at most once. Time is O(n*(n+m)); distance, counters, and queue use O(nn), and adjacency uses O(n+m), giving O(nn+m) space.

Two BFS arrays from the initial positions describe only static shortest paths. They omit whose turn is next, Tom's future responses, and Jerry's choices after those responses; a finite cycle can support evasion forever despite all relevant BFS distances being finite. A shortcut would need additional assumptions and a separate proof. Restricting the graph to a tree removes cycles and may support a tree-specific pursuit argument, but does not by itself justify an arbitrary formula from two distances. Alternatively, changing the objective to comparing independent shortest arrival times to a fixed vertex makes the initial BFS distances directly relevant. Neither change is part of this game, so the implementation uses the full state-space analysis.

Time complexity:
O(n*(n+m)) for n vertices and m edges
Space complexity:
O(n*n+m)