Google 2027 SDE Intern (Passed): Undirected Unweighted Graph — Fewest Edges for Alice and Bob to Reach the Destination

Overview

Google has already sent out a wave of OAs for 2027 Summer Interns, and the fastest candidates have finished their VOs. Here's a question I got.

The interviewer gave a hard undirected, unweighted graph problem. If you haven't reviewed this part of graph theory, it's very easy to get stuck. I wasn't asked to finish the code, but I had to explain the solution clearly.

Problem

Given an undirected, unweighted graph: Alice starts at A, Bob starts at B, and both are going to D.

Each picks a path to D. Put every edge used by either path into a set; minimize the size of that set.

Approach: three BFS runs + enumerate the meeting point

Key observation: in an optimal solution, the two paths meet at some node X and then travel together to D, so the shared edges are counted only once.

• Alice: A → X
• Bob: B → X
• Together: X → D

So the answer is:

min over X of dist(A, X) + dist(B, X) + dist(X, D)

X can be A, B or D itself, which covers the case where they share no edges at all (X = D).

The graph is unweighted, so run BFS from A, B and D to get the three distance arrays, then try every X. Time O(V + E), space O(V).

from collections import deque

def bfs(adj, src):
    dist = {src: 0}
    q = deque([src])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

def min_union_edges(n, edges, a, b, d):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    da, db, dd = bfs(adj, a), bfs(adj, b), bfs(adj, d)
    best = min(
        (da[x] + db[x] + dd[x] for x in range(n) if x in da and x in db and x in dd),
        default=-1,
    )
    return best   # -1 means someone can't reach D

Talking points

• Clarify first: is the graph connected? Can A, B and D coincide? What to return if someone can't reach D?
• Explain why the optimum is always Y-shaped: two paths that split and later meet again gain nothing — the later segments can be merged into one.
• This is really a Steiner tree problem with 3 terminals; on an unweighted graph you can solve it by enumerating the center.

There were follow-ups afterwards that I won't list here.