Shortest Distance Between Two Nodes
Scale AI● MediumNEW GRADONSITE INTERVIEWProblem statement
For this practice exercise, an undirected graph has n vertices labelled 0 through n-1. Each row [u,v] in edges joins u and v in both directions and has length one.
Return the minimum number of edges in any path from source to target. Return 0 if they are the same vertex, and -1 if no path connects them. Declared vertices with no incident edges still exist.
There are no self-loops or duplicate undirected edges. Cycles and disconnected components are allowed.
Interview context
The original graph question first constructs a graph from a Python dictionary. A related report describes distances on a tree and says there were three questions without defining the later questions. The dictionary schema, direction, weights, labels, returned shape and endpoint rules are absent. The indexed edge array, unit undirected edges, scalar result and input bounds here are explicit practice choices. Preserve dictionary parsing as interview context; it is not an additional parsing task in this callable.
Function
shortestNodeDistance(n: int, edges: int[][], source: int, target: int) → intExamples
Example 1
n = 5edges = [[0,1],[1,2],[2,3],[0,4],[4,3]]source = 0target = 3return = 2The path 0 → 4 → 3 uses two edges, shorter than 0 → 1 → 2 → 3.
Example 2
n = 4edges = [[0,1]]source = 0target = 3return = -1Vertex 3 is isolated and cannot be reached from vertex 0.
Example 3
n = 1edges = []source = 0target = 0return = 0A vertex is zero edges away from itself, including an isolated vertex.
Constraints
- For this exercise, assume
1 <= n <= 500and0 <= edges.length <= 1000. - Each edge has exactly two valid, different indices in
[0,n-1]. Every undirected edge occurs once, in either orientation. sourceandtargetare valid indices. All supplied inputs satisfy these rules.