How should I practice Minimum Shared Route Length for Two Travelers?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen problems in FastPrep.

Is Minimum Shared Route Length for Two Travelers associated with Google?

FastPrep tags this as a Google phone screen coding practice problem when the problem catalog has that company and stage context.

Minimum Shared Route Length for Two Travelers

Google● MediumNEW GRADPHONE SCREEN

Learn

Problem statement

An undirected, unweighted graph represents n cities numbered from 0 to n - 1. Two travelers start at cities a and b, and both want to reach city destination.

They may travel separately, or meet at any city and share the remainder of the route. A shared edge is counted only once. Return the minimum possible number of distinct route edges used by the two travelers together. Return -1 if no valid pair of routes exists.

Function

minimumSharedRouteLength(n: int, edges: int[][], a: int, b: int, destination: int) → int

Examples

Example 1

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

The travelers meet at city two and share the final two edges.

Example 2

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

Each traveler can use one direct edge to the destination.

Example 3

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

The first traveler cannot reach the destination or any meeting city reachable by the second traveler.

Constraints

1 <= n <= 200000.
0 <= edges.length <= 300000.
Every edge contains two distinct valid city IDs.
a, b, and destination are valid city IDs.