Shortest Hop Path Between Machines
Google● MediumINTERNONSITE INTERVIEWProblem statement
A data center contains n machines numbered from 0 through n - 1. Each pair connections[i] = [u, v] is a bidirectional connection between machines u and v. Every connection takes one hop.
Return a path from source to target that uses the minimum possible number of hops, including both endpoints. If several shortest paths exist, return the lexicographically smallest machine sequence. If the target is unreachable, return an empty array.
When source == target, return the one-machine path [source].
Function
shortestMachinePath(n: int, connections: int[][], source: int, target: int) → int[]Examples
Example 1
n = 6connections = [[0,2],[2,5],[0,1],[1,5],[1,3],[3,4]]source = 0target = 5return = [0,1,5]Paths [0, 1, 5] and [0, 2, 5] both use two hops. The path through machine 1 is lexicographically smaller.
Example 2
n = 4connections = [[0,1],[2,3]]source = 0target = 3return = []The source and target lie in different connected components, so no path exists.
Constraints
1 <= n <= 200000.0 <= connections.length <= 300000.- Every connection contains two distinct machine IDs in
[0, n - 1]. - No undirected connection appears more than once.
0 <= source, target < n.