Shortest Path, Nodes on Any Shortest Path, and Whether Alice Can Evade Bob

Read the full interview experience this question came from →

Quick Overview

In an unweighted undirected graph, find Alice's shortest path to a target, identify every node that lies on some shortest path, and decide whether she can walk a shortest path without being intercepted by a chaser, Bob. It tests breadth-first search, distance-based proofs and precise modeling of game rules.

Shortest Path, Nodes on Any Shortest Path, and Whether Alice Can Evade Bob

Company: Google

Role: Software Engineer

Category: Software Engineering Fundamentals

Difficulty: medium

Interview Round: Onsite

You are given an undirected, unweighted graph with `n` nodes, numbered `0` to `n - 1`, and a list of edges. Alice stands at node `a` and needs to reach a target node `t`. The interview had a base question and two follow-ups on the same graph. ### Constraints and Clarifications - Every edge has length 1, and the graph may be disconnected. - Assume the graph can be large, so each part should run in time close to linear in the number of nodes and edges. - Time is measured in steps: in one step a person moves along one edge. ### Clarifying Questions - What should be returned when `t` cannot be reached from `a`? - For the base question, is the length of a shortest path enough, or must an actual path be returned? - Can the edge list contain self-loops or duplicate edges? ### Part 1 — Shortest path for Alice Find a shortest path from `a` to `t`. ```hint Unweighted means layered Think about the order in which nodes are discovered when every edge costs the same. ``` #### What This Part Should Cover - The search, why it yields shortest distances when every edge has length 1, and how the path itself is recovered - An unreachable target and the case `a = t` - Time and space complexity ### Part 2 — Every node that can lie on a shortest path Find all nodes that appear on at least one shortest path from `a` to `t`. ```hint Look from the other end too Consider what a second search, started somewhere other than Alice's node, would tell you about each node. ``` #### What This Part Should Cover - An exact test for whether a node lies on some shortest path, and why it is correct - Why enumerating the shortest paths is not feasible - Complexity, and how the same idea applies to edges ### Part 3 — Bob tries to catch Alice Bob stands at another node `b`. Alice picks one of the shortest paths from `a` to `t` and starts walking it, and Bob starts moving at the same moment. Determine whether Alice can reach `t` safely, without being caught by Bob. ```hint Earliest arrival Once the movement rules are fixed, ask for each node on Alice's route how early Bob could be standing there. ``` #### Clarifying Questions for this Part - May Bob stand still during a step, or must he move along an edge in every step? - Is Alice caught only when both are on the same node at the same time, or also when they cross the same edge in opposite directions during one step? - If Bob reaches `t` at the same moment as Alice, or before her, is she caught? - Does Bob know which path Alice chose, so that the question is whether some shortest path is safe against every move Bob could make? #### What This Part Should Cover - A precise statement of the catch rules and of what "safe" means - A per-node (and, if needed, per-edge) safety condition, and how to evaluate it over all of Alice's candidate paths at once - How the answer changes if Bob may wait versus if he must keep moving - Complexity ### What a Strong Answer Covers - Breadth-first search used correctly, reasoning with distances rather than enumerating paths - A proof-level argument for the shortest-path membership test - Movement and capture rules agreed explicitly before any code is written for Part 3 - Recognition of how much the chosen rules simplify or complicate Part 3, with a correct algorithm for the rules chosen - Linear-time solutions and careful handling of unreachable nodes ### Follow-up Questions - How do Parts 2 and 3 change when edges have positive weights? - How would you handle several chasers starting at different nodes? - If Alice may take any path rather than a shortest one, how do you decide whether she can reach `t` safely?

Overview: In an unweighted undirected graph, find Alice's shortest path to a target, identify every node that lies on some shortest path, and decide whether she can walk a shortest path without being intercepted by a chaser, Bob. It tests breadth-first search, distance-based proofs and precise modeling of game rules.

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

Google logo
Google
Sep 16, 2026
mediumSoftware EngineerOnsiteSoftware Engineering Fundamentals
10
0

You are given an undirected, unweighted graph with n nodes, numbered 0 to n - 1, and a list of edges. Alice stands at node a and needs to reach a target node t. The interview had a base question and two follow-ups on the same graph.

Constraints and Clarifications

  • Every edge has length 1, and the graph may be disconnected.
  • Assume the graph can be large, so each part should run in time close to linear in the number of nodes and edges.
  • Time is measured in steps: in one step a person moves along one edge.

Clarifying Questions Guidance

  • What should be returned when t cannot be reached from a ?
  • For the base question, is the length of a shortest path enough, or must an actual path be returned?
  • Can the edge list contain self-loops or duplicate edges?

Part 1 — Shortest path for Alice

Find a shortest path from a to t.

What This Part Should Cover Guidance

  • The search, why it yields shortest distances when every edge has length 1, and how the path itself is recovered
  • An unreachable target and the case a = t
  • Time and space complexity

Part 2 — Every node that can lie on a shortest path

Find all nodes that appear on at least one shortest path from a to t.

What This Part Should Cover Guidance

  • An exact test for whether a node lies on some shortest path, and why it is correct
  • Why enumerating the shortest paths is not feasible
  • Complexity, and how the same idea applies to edges

Part 3 — Bob tries to catch Alice

Bob stands at another node b. Alice picks one of the shortest paths from a to t and starts walking it, and Bob starts moving at the same moment. Determine whether Alice can reach t safely, without being caught by Bob.

Clarifying Questions for this Part Guidance

  • May Bob stand still during a step, or must he move along an edge in every step?
  • Is Alice caught only when both are on the same node at the same time, or also when they cross the same edge in opposite directions during one step?
  • If Bob reaches t at the same moment as Alice, or before her, is she caught?
  • Does Bob know which path Alice chose, so that the question is whether some shortest path is safe against every move Bob could make?

What This Part Should Cover Guidance

  • A precise statement of the catch rules and of what "safe" means
  • A per-node (and, if needed, per-edge) safety condition, and how to evaluate it over all of Alice's candidate paths at once
  • How the answer changes if Bob may wait versus if he must keep moving
  • Complexity

What a Strong Answer Covers Guidance

  • Breadth-first search used correctly, reasoning with distances rather than enumerating paths
  • A proof-level argument for the shortest-path membership test
  • Movement and capture rules agreed explicitly before any code is written for Part 3
  • Recognition of how much the chosen rules simplify or complicate Part 3, with a correct algorithm for the rules chosen
  • Linear-time solutions and careful handling of unreachable nodes

Follow-up Questions Guidance

  • How do Parts 2 and 3 change when edges have positive weights?
  • How would you handle several chasers starting at different nodes?
  • If Alice may take any path rather than a shortest one, how do you decide whether she can reach t safely?