MathWorks·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

MathWorks software engineer interview with a graph algorithms question that required actual working code plus complexity analysis. Pretty standard technical screen but they wanted more than just a sketch, they wanted something you could compile.

Questions Asked (1)

Given an unweighted graph with n vertices and m edges as an adjacency list, implement BFS from a source vertex s that returns both a shortest-distance array (with -1 for unreachable nodes) and a parent array for path reconstruction. Handle disconnected graphs and analyze time and space complexity.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The BFS itself wasn't the hard part, I've done it a hundred times.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem and edge cases, then walk through the BFS algorithm step-by-step, emphasizing initialization, queue operations, and neighbor traversal. Finally, analyze time and space complexity, and discuss how to reconstruct paths using the parent array.

Pro tip: Mention that BFS naturally handles disconnected graphs by leaving unreachable nodes at -1, and that the parent array can be used to reconstruct the shortest path by backtracking from the target to the source.

1. Clarify and Plan

Confirm input format (adjacency list), output requirements (distance and parent arrays), and edge cases like disconnected graphs or source not in graph. Outline the BFS approach.

2. Initialize Data Structures

Create distance array filled with -1, parent array filled with -1, and a queue. Set distance[s] = 0 and enqueue s.

3. Execute BFS

While queue is not empty, dequeue a vertex u. For each neighbor v of u, if distance[v] == -1, set distance[v] = distance[u] + 1, parent[v] = u, and enqueue v.

4. Return Results

After BFS, return the distance and parent arrays. Unreachable nodes remain -1 in both arrays.

5. Analyze Complexity

Time complexity: O(n + m) since each vertex and edge is processed once. Space complexity: O(n) for distance, parent, and queue.

Key Points to Mention

BFS guarantees shortest path in unweighted graphs.
Use a queue (FIFO) for level-order traversal.
Initialize distance array with -1 to mark unvisited nodes.
Parent array enables path reconstruction by backtracking.
Disconnected components are handled naturally: unreachable nodes stay -1.
Time complexity O(n + m) and space complexity O(n).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.