Minimum Union of Two Routes
Updated
Problem statement
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) → intExamples
Example 1
n = 7edges = [[0,2],[1,2],[2,3],[3,6],[0,4],[1,4],[4,5],[5,6]]a = 0b = 1d = 6return = 4The 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 = -1Alice 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 = 4Alice and Bob start together, so they can share the entire four-edge path to 4.
Constraints
1 <= n <= 2000000 <= edges.length <= 200000- Every row of
edgesis[u, v]with0 <= u, v < n. 0 <= a, b, d < na,b, anddmay 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