← Google Interview Insights

Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jul 2026

Summary

Graph problem at Google for a software engineer role. One question, but it had enough layers to keep me busy for the whole session.

Questions Asked (1)

Q1

Given an undirected unweighted graph representing a bus network with n nodes, two people start at different nodes A and B and both need to reach a destination node. They can meet anywhere along the way, and once they meet, they travel together so the cost from the meeting point to the destination is only counted once. Find the minimum total number of steps for both to reach the destination, or return -1 if it's not possible.

Algorithms & Data Structures
Author's notes

The shared-cost-after-meeting part is what tripped me up initially.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding a meeting node M that minimizes dist(A, M) + dist(B, M) + dist(M, D). Precompute shortest distances from A, B, and D using BFS, then iterate over all nodes to find the minimum total cost, returning -1 if no valid meeting node exists.

Pro tip: Clarify that the meeting point must be on a shortest path from the destination to avoid unnecessary detours, and mention that BFS is optimal for unweighted graphs. Also, consider edge cases like A or B already at D, or the graph being disconnected.

1. Understand the problem and define the cost function

Restate the problem: two people start at A and B, can meet at any node M, and then travel together to D. The total cost is dist(A, M) + dist(B, M) + dist(M, D).

2. Precompute shortest distances

Run BFS from A, B, and D to compute the shortest distance from each node to A, B, and D respectively. This takes O(n + m) time per BFS.

3. Iterate over all possible meeting nodes

For each node M, if all three distances are finite, compute the total cost and keep track of the minimum. If no node yields a finite cost, return -1.

4. Analyze time and space complexity

The algorithm runs in O(n + m) time and uses O(n) space for the distance arrays, which is optimal for this problem.

5. Discuss edge cases and optimizations

Mention cases where A or B is already at D, or where the graph is disconnected. Also, note that the meeting point must lie on a shortest path from D to avoid extra cost.

Key Points to Mention

  • BFS for unweighted graphs to compute shortest paths
  • Minimizing dist(A, M) + dist(B, M) + dist(M, D) over all nodes M
  • Time complexity O(n + m) and space complexity O(n)
  • Handling disconnected graphs and unreachable nodes
  • Edge cases: A or B already at D, or A and B at the same node
  • The meeting point must be on a shortest path from D to avoid unnecessary detours

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.