FastPrepShortest Distances From an Adjacency Matrix
Problems/Shortest Distances From an Adjacency Matrix

Shortest Distances From an Adjacency Matrix

Boston Consulting Group logoBoston Consulting Group● MediumFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a Boston Consulting Group full-time phone screen. The report gives a shortest-path task on an unweighted, connected, undirected graph written as an adjacency matrix. It also mentions a follow-up with weights. Our version returns both the fewest edges and the smallest total weight. We chose how positive weights are written, the paired output, the limits, and the examples. No heuristic is needed. Our version is about 96% the same as the reported question.

You are given a connected, undirected graph as an integer adjacency matrix matrix, plus zero-based vertices source and target.

For distinct vertices, matrix[u][v] = 0 means there is no edge. A positive entry is the weight of the edge. The matrix is symmetric, every diagonal entry is zero, and the graph has no loops or multiple edges.

Return a two-element array of 64-bit integers:

  1. The fewest edges in any path from source to target, ignoring edge weights.
  2. The smallest sum of edge weights in any path from source to target.

These two minima are independent: the fewest-edge path need not have the least total weight. If the two vertices are equal, return [0,0]. Because the graph is connected, both answers always exist.

Function

shortestDistances(matrix: int[][], source: int, target: int) → long[]

Examples

Example 1

matrix = [[0,2,10],[2,0,3],[10,3,0]]source = 0target = 2return = [1,5]
matrix
01200210120321030

The direct edge 0 → 2 uses one edge but costs 10. The path 0 → 1 → 2 uses two edges and costs only 2+3=5.

Example 2

matrix = [[0,4,0,0],[4,0,6,0],[0,6,0,2],[0,0,2,0]]source = 3target = 0return = [3,12]
matrix
012300400140602060230020

The only simple route is 3 → 2 → 1 → 0, with three edges and total weight 2+6+4=12.

Constraints

  • 1 <= matrix.length <= 50, and matrix is square.
  • 0 <= matrix[u][v] <= 1000000.
  • matrix[u][v] = matrix[v][u], and matrix[u][u] = 0.
  • Positive entries define one connected graph.
  • 0 <= source, target < matrix.length.

More Boston Consulting Group interview questions

  • Build Taxi Driver Performance FeaturesOA · Seen Oct 2026
  • Predict Taxi Driver ClassesOA · Seen Oct 2026
  • Prepare Taxi Driver Classification DataOA · Seen Oct 2026
  • Summarize Taxi Drivers and RidesOA · Seen Oct 2026
  • Even-Position MonotonicityOA · Seen Jul 2026

Similar questions at other companies

  • Cheapest Flights Within K StopsAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Shortest Word Chain Between Two WordsFanatics · PHONE SCREEN
  • Shortest Path Node Count Avoiding Broken NodesGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
  • Maximum Survival Time in a Graph PursuitZip · PHONE SCREENZip interview questions
  • Find and Reconstruct a Binary-Matrix PathMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
  • Find a Directed Resource Access PathCoreWeave · PHONE SCREEN
  • Shortest Distance from All BuildingsWaymo · PHONE SCREENWaymo interview questions
  • Fire Station Response BillLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
  • Delivery Management SystemAkuna Capital · OAAkuna Capital interview questions
  • Minimum Friend API CallsMercor · ONSITE INTERVIEWMercor interview questions
All Boston Consulting Group interview questionsSee Boston Consulting Group hiring insights
Saved
class Solution {
    public long[] shortestDistances(int[][] matrix, int source, int target) {
        // Write your code here
    }
}
Checking account…