Escape The Ghosts

Escape The Ghosts

What is this problem about?

The Escape The Ghosts interview question is a tactical game played on a 2D plane. You start at (0, 0) and want to reach a specific target coordinate. However, there are several "ghosts" at various starting positions. In each turn, you and all the ghosts can move one unit in any of the four cardinal directions. If a ghost reaches the target at the same time as you or before you, or if a ghost intercepts you along the way, you lose. You need to determine if there is a strategy to reach the target safely.

Why is this asked in interviews?

Google and Wix ask the Escape The Ghosts coding problem to see if a candidate can identify a simple mathematical shortcut in what looks like a complex simulation or game theory problem. It tests your ability to simplify conditions and realize that the "best" strategy for both you and the ghosts is to move directly to the target.

Algorithmic pattern used

This problem follows a Math and Manhattan Distance pattern. The core realization is that you can only win if your distance to the target is strictly less than the distance of any ghost to the target. If a ghost can reach the target before or at the same time as you, it can simply wait there or intercept you, and you cannot win. The distance used is the Manhattan Distance: |x1 - x2| + |y1 - y2|.

Example explanation

Suppose your target is at (5, 0). Your distance is |5-0| + |0-0| = 5. There is a ghost at (2, 2). The ghost's distance to the target is |5-2| + |0-2| = 3 + 2 = 5. Since the ghost can reach the target in 5 steps (the same as you), it can meet you at the target. You cannot escape. If the ghost was at (6, 6), its distance would be |5-6| + |0-6| = 1 + 6 = 7. Since 7 > 5, you can reach the target before that specific ghost.

Common mistakes candidates make

• Simulating the Game: Trying to use BFS or complex pathfinding to see if you can "out-maneuver" the ghosts.
• Euclidean Distance: Using straight-line distance instead of Manhattan distance (grid-based movement).
• Ignoring the "Intercept" Case: Over-complicating the logic by thinking about where a ghost might catch you in the middle of the path, when the target-arrival time is the only metric that matters.

Interview preparation tip

In "chase" problems on a grid, always check if comparing the time-to-target (distance) is sufficient. Often, the shortest path is the only one that matters for both parties.