How should I practice Minimum-Cost Meeting City?

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

Is Minimum-Cost Meeting City associated with Google?

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

Problem · Graph

Minimum-Cost Meeting City

Learn this problem

● Medium

GoogleINTERNPHONE SCREEN

See Google hiring insights

Problem statement

An undirected, unweighted graph represents n cities numbered from 0 to n - 1. Travelers start at cities x and y. They may travel separately to a meeting city m, then ride together from m to destination.

The cost of choosing m is dist(x, m) + dist(y, m) + dist(m, destination), so the shared final route is counted once.

Return the meeting city with minimum cost. If several cities have the same minimum cost, return the smallest city index. Return -1 if no city is reachable from both travelers and can reach destination.

Function

minimumCostMeetingCity(n: int, edges: int[][], x: int, y: int, destination: int) → int

Examples

Example 1

n = 7edges = [[0,2],[1,2],[2,3],[3,6],[0,4],[1,4],[4,5],[5,6]]x = 0y = 1destination = 6return = 2

Meeting at city 2 costs 1 + 1 + 2 = 4. Meeting at city 4 also costs 4, so the smaller city index 2 wins the tie.

Example 2

n = 4edges = [[0,1],[2,3]]x = 0y = 2destination = 3return = -1

The travelers start in different connected components, so no valid meeting city exists.

Constraints

1 <= n <= 200000
0 <= edges.length <= 200000
Every row of edges is [u, v] with 0 <= u, v < n and u != v.
0 <= x, y, destination < n