FastPrepMinimum Union of Two Routes
Problems/Minimum Union of Two Routes

Minimum Union of Two Routes

Google logoGoogle● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report gives an undirected, unweighted graph, two starts, a shared destination, and the goal of the fewest edges in the union of routes. It gives a Y-shaped merge proof, a three-BFS formula, a zero-indexed Python interface, -1 for unreachable, and linear-time complexity. It does not give input limits, how to handle duplicate edges, or whether the three endpoints may be the same. Our version is about 96% the same as the reported question.

You are given an undirected, unweighted graph with n vertices numbered from 0 to n - 1. Alice starts at vertex a, Bob starts at vertex b, and both must reach destination d.

Alice chooses one path from a to d, and Bob chooses one path from b to d. The cost of their two routes is the number of distinct undirected edges that appear in the union of both paths.

Return the minimum possible cost. Return -1 when either traveler cannot reach d.

Repeated rows in edges represent the same undirected connection. Self-loops do not help a route and may be ignored.

Function

minimumUnionEdges(n: int, edges: int[][], a: int, b: int, d: int) → int

Examples

Example 1

n = 7edges = [[0,2],[1,2],[2,3],[3,6],[0,4],[1,4],[4,5],[5,6]]a = 0b = 1d = 6return = 4

The travelers can meet at vertex 2. The edges from 0 and 1 to 2 contribute two edges, and the shared suffix 2 - 3 - 6 contributes two more.

Example 2

n = 4edges = [[0,1],[2,3]]a = 0b = 2d = 3return = -1

Alice and the destination are in different connected components, so no valid pair of routes exists.

Example 3

n = 5edges = [[0,1],[1,2],[2,3],[3,4]]a = 0b = 0d = 4return = 4

Alice and Bob start together, so they can share the entire four-edge path to 4.

Constraints

  • 1 <= n <= 200000
  • 0 <= edges.length <= 200000
  • Every row of edges is [u, v] with 0 <= u, v < n.
  • 0 <= a, b, d < n
  • a, b, and d may refer to the same vertex.

More Google Onsite Interview questions

  • Evaluate a Nested Math ExpressionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Distinct Subset SumsONSITE INTERVIEW · Seen Nov 2026
  • Playlist With No Same Artist in a RowONSITE INTERVIEW · Seen Nov 2026
  • Route Pattern MatcherPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
  • Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
  • Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026

Similar questions at other companies

  • Cheapest Flights Within K StopsAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Fire Station Response BillLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
  • Minimum Friend API CallsMercor · ONSITE INTERVIEWMercor interview questions
  • Shortest Increasing Path to a TargetUber · ONSITE INTERVIEWUber interview questions
  • Find and Reconstruct a Binary-Matrix PathMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
  • Open the Lock and Return a Shortest PathZip · PHONE SCREEN · ONSITE INTERVIEWZip interview questions
  • Shortest Travel Time in a Grid with Traffic LightsWaymo · PHONE SCREENWaymo interview questions
  • Delivery Management SystemAkuna Capital · OAAkuna Capital interview questions
  • Shortest Word Chain Between Two WordsFanatics · PHONE SCREEN
  • Shortest Path from an Encoded GraphIntuit · OAIntuit interview questions

Interview reports that mention this question

  • Google Software Engineer Onsite Questions: 10 Experiences

Google interview experiences

  • Google L5 Security Engineer Domain Knowledge Round: 1 Experience
  • Google OA: What It Tests (2026)
  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int minimumUnionEdges(int n, int[][] edges, int a, int b, int d) {
      // Write your code here.
    }
}
Checking account…