FastPrepChoose a Shortest Path That Avoids Bob
Problems/Choose a Shortest Path That Avoids Bob

Choose a Shortest Path That Avoids Bob

Google logoGoogle● HardFULLTIMEONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report gives the task and interview context. The callable signature, deterministic tie-breaking, examples, and bounds are source-faithful reconstruction details; estimated fidelity is 90%.

Alice and Bob move simultaneously along one edge per second in an undirected, unweighted graph. Alice must choose a shortest path from her start to the destination. Bob may choose any walk to catch her.

Return whether Alice can choose a shortest path such that Bob cannot occupy the same node at the same or an earlier time at any step, including the destination. Bob's earliest arrival time therefore determines safety.

Function

canAliceReachSafely(n: int, edges: int[][], aliceStart: int, bobStart: int, destination: int) → boolean

Examples

Example 1

n = 5edges = [[0,1],[1,4],[0,2],[2,3],[3,4]]aliceStart = 0bobStart = 3destination = 4return = false

Alice takes 0-1-4; Bob reaches the destination too late.

Example 2

n = 4edges = [[0,1],[1,3],[2,1]]aliceStart = 0bobStart = 2destination = 3return = false

Bob reaches the shared middle node before Alice.

Example 3

n = 3edges = [[0,1],[1,2]]aliceStart = 0bobStart = 0destination = 2return = false

Bob starts on Alice, so capture is immediate.

Constraints

  • 1 <= n <= 100000.
  • 0 <= edges.length <= 200000.

More Google problems

  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public boolean canAliceReachSafely(int n, int[][] edges, int aliceStart, int bobStart, int destination) {
        // write your code here
    }
}
Checking account…