← MathWorks Interview Insights

MathWorks·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Got a graph problem at MathWorks that looked like a shortest path question until you realized the twist made it a lot messier. Single technical round, coding focused, left feeling like I mostly held it together but the runtime discussion at the end got shaky.

Questions Asked (1)

Q1

You're given a weighted directed graph and an integer K. You can add up to K extra edges of weight 1 between any nodes you choose. Find the minimum-weight path from node 1 to the last node after placing those extra edges optimally.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

My first instinct was just run Dijkstra and call it a day, which obviously doesn't work because the extra edges change the graph structure depending on where you put them.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a shortest path in an expanded graph where each state is (node, number of extra edges used). Use Dijkstra's algorithm on this expanded graph, considering both original edges and extra edges of weight 1. The answer is the minimum distance to the last node over all possible numbers of extra edges used (0 to K).

Pro tip: Mention that the expanded graph has O(K * V) states and O(K * (E + V^2)) edges if extra edges are considered between all pairs, but you can optimize by only considering extra edges from the current node to any other node, reducing to O(K * (E + V)) edges. This shows awareness of complexity trade-offs.

1. Clarify the problem

Confirm that extra edges can be added between any nodes, including already connected ones, and that they have weight 1. Also confirm that the path can use any number of extra edges up to K.

2. Define the state space

Define a state as (node, k) where k is the number of extra edges used so far. The goal is to reach (last_node, k) for any k ≤ K with minimum total weight.

3. Construct transitions

From state (u, k), you can traverse an original edge (u, v) with weight w to (v, k), or use an extra edge to go to any node v with weight 1 to (v, k+1) if k < K.

4. Run Dijkstra

Run Dijkstra's algorithm on the expanded graph starting from (1, 0). Since all edge weights are non-negative, Dijkstra is optimal.

5. Extract the answer

The answer is the minimum distance among all states (last_node, k) for k = 0 to K.

Key Points to Mention

  • Expanded graph representation with state (node, extra_edges_used)
  • Dijkstra's algorithm for non-negative weights
  • Time complexity: O(K * (E + V) log(KV)) with optimized extra edges
  • Space complexity: O(K * V) for distances
  • Handling of extra edges: from any node to any other node with weight 1
  • Optimization: only consider extra edges from current node to all others, not all pairs

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