How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at MathWorks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at MathWorks during technical interviews.

Implement BFS shortest paths with reconstruction

Quick Overview

This question evaluates understanding of graph traversal via breadth-first search, computation of shortest paths in unweighted graphs, and path reconstruction using parent arrays, assessing algorithmic reasoning and implementation skills in the Coding & Algorithms domain.

Company: MathWorks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Given an unweighted graph with n vertices and m edges represented as an adjacency list, implement breadth-first search (BFS) from a source vertex s to return: ( 1) an array dist where dist[v] is the length of the shortest path from s to v (or −1 if unreachable); and ( 2) an array parent to reconstruct one shortest path. Handle disconnected graphs, analyze time and space complexity, and provide code in C, C++, Java, or JavaScript.

Quick Answer: This question evaluates understanding of graph traversal via breadth-first search, computation of shortest paths in unweighted graphs, and path reconstruction using parent arrays, assessing algorithmic reasoning and implementation skills in the Coding & Algorithms domain.

Given an unweighted graph with `n` vertices (labeled `0` to `n-1`) represented as an adjacency list `adj` (where `adj[u]` is the list of vertices adjacent to `u`), and a source vertex `s`, run breadth-first search from `s` and return two arrays: 1. `dist` — `dist[v]` is the number of edges on the shortest path from `s` to `v`, or `-1` if `v` is unreachable from `s`. 2. `parent` — `parent[v]` is the vertex immediately before `v` on one shortest path from `s` to `v`. Set `parent[s] = -1`, and `parent[v] = -1` for any unreachable `v`. Return the result as a list of two arrays: `[dist, parent]`. The graph may be disconnected. To make `parent` deterministic, explore each vertex's neighbors in the order they appear in `adj[u]`, and record `parent[v]` only the first time `v` is discovered. **Example.** With `n = 6`, `adj = [[1,2],[0,3],[0,3,4],[1,2,5],[2,5],[3,4]]`, `s = 0`: `dist = [0,1,1,2,2,3]` and `parent = [-1,0,0,1,2,3]`. To reconstruct the shortest path to vertex 5: 5 ← 3 ← 1 ← 0, i.e. `0 -> 1 -> 3 -> 5`.

Constraints

1 <= n <= 10^5
0 <= s < n
0 <= m <= 2 * 10^5 (m = total number of directed entries across the adjacency list)
Each entry in adj[u] is a valid vertex index in [0, n-1]
The graph is unweighted and may be disconnected

Examples

Input: (6, [[1, 2], [0, 3], [0, 3, 4], [1, 2, 5], [2, 5], [3, 4]], 0)

Expected Output: [[0, 1, 1, 2, 2, 3], [-1, 0, 0, 1, 2, 3]]

Explanation: Connected graph from source 0. Distances grow level by level; parent records the discoverer of each vertex, e.g. parent[5]=3 (path 0->1->3->5).

Input: (5, [[1], [0, 2], [1], [4], [3]], 0)

Expected Output: [[0, 1, 2, -1, -1], [-1, 0, 1, -1, -1]]

Explanation: Disconnected graph: component {0,1,2} is reachable from source 0; component {3,4} is not, so vertices 3 and 4 keep dist=-1 and parent=-1.

Input: (1, [[]], 0)

Expected Output: [[0], [-1]]

Explanation: Single isolated vertex which is the source: dist[0]=0, parent[0]=-1.

Input: (4, [[], [], [], []], 2)

Expected Output: [[-1, -1, 0, -1], [-1, -1, -1, -1]]

Explanation: No edges and source 2: only vertex 2 is reachable (distance 0); all other vertices remain unreachable.

Input: (3, [[1, 2], [0, 2], [0, 1]], 1)

Expected Output: [[1, 0, 1], [1, -1, 1]]

Explanation: Triangle with source 1: vertices 0 and 2 are both one edge away and are discovered directly from 1, so parent[0]=parent[2]=1.

Hints

BFS visits vertices in non-decreasing order of distance from the source, so the first time you reach a vertex is along a shortest path.
Use a single dist array initialized to -1 as both the 'visited' marker and the distance: dist[v] == -1 means v is unvisited/unreachable.
When you pop u and look at a neighbor v that is still unvisited, set dist[v] = dist[u] + 1 and parent[v] = u, then enqueue v.
Process adj[u] in order and only set parent[v] on first discovery so the reconstructed path is deterministic. parent[s] stays -1, and any vertex never reached keeps dist = parent = -1.

Quick Overview