FastPrepShortest Path in an Unweighted Graph
Problems/Shortest Path in an Unweighted Graph

Shortest Path in an Unweighted Graph

Capital One logoCapital One● EasyINTERNONSITE INTERVIEW
QuestionFunctionExamplesConstraints

Problem statement

Source note: A 2026 report on a Capital One software engineering intern interview in Toronto names a single coding task, finding a shortest path with breadth-first search. It gives nothing else about the task.

The report gives no input format, graph type, limits or rule for an unreachable target. Here the graph is undirected and every road counts as 1, given as n nodes and a list of edges. You return the fewest roads from source to target, 0 when they are the same node, and -1 when no path exists. The graph has up to 5000 nodes and 10^4 edges, with no self-loops or repeated edges.

The judged task matches the report at about 70%.

You are given an undirected graph with n nodes, numbered 0 to n - 1. Each edges[i] = [a, b] is a road between nodes a and b that you can travel in both directions. Every road has the same length.

Return the smallest number of roads on a path from source to target. If source and target are the same node, return 0. If no path connects them, return -1.

Function

shortestPath(n: int, edges: int[][], source: int, target: int) → int

Examples

Example 1

n = 6edges = [[0,1],[1,2],[2,3],[3,4],[0,5],[5,4]]source = 0target = 4return = 2

There are two ways from node 0 to node 4. The path 0 → 1 → 2 → 3 → 4 uses 4 roads. The path 0 → 5 → 4 uses only 2 roads, so the answer is 2.

Example 2

n = 5edges = [[0,1],[1,2],[3,4]]source = 0target = 4return = -1

From node 0 you can reach only nodes 1 and 2. Node 4 is joined only to node 3, so no path reaches it and the answer is -1.

Example 3

n = 4edges = [[1,0],[2,1],[3,2]]source = 0target = 3return = 3

Each road is listed with the larger node first, but roads work in both directions. The path 0 → 1 → 2 → 3 uses 3 roads, so the answer is 3.

Constraints

  • 1 <= n <= 5000
  • 0 <= edges.length <= 10^4
  • edges[i].length == 2
  • 0 <= edges[i][0], edges[i][1] < n
  • edges[i][0] != edges[i][1]
  • No two edges connect the same pair of nodes.
  • 0 <= source, target < n

More Capital One problems

  • Digit-Coded Card ValidationONSITE INTERVIEW · Seen Nov 2026
  • Rank Football TeamsOA · Seen Oct 2026
  • Count Subarrays Matching a Comparison PatternOA · Seen Oct 2026
All Capital One interview questionsSee Capital One hiring insights
Saved
public int shortestPath(int n, int[][] edges, int source, int target) {
    // Write your code here.
}
Checking account…