Implement BFS shortest paths with reconstruction
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.