← Modular Interview Insights

Modular·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Mar 2026

Summary

Got a coding problem at Modular for a software engineer role that was all about graph traversal. The problem itself was well-defined but required you to think carefully about both the computation and the reconstruction of the path, not just the length.

Questions Asked (1)

Q1

Given a list of tasks with names, dependencies, and durations representing a directed acyclic graph, compute the critical path length (longest path by total duration) and output the actual sequence of tasks on that path. Multiple test graphs may be given.

Algorithms & Data StructuresSystem Design
Author's notes

The length part I got pretty quickly, topological sort plus a running max.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the tasks as a weighted DAG where edge weights are task durations, then compute the longest path using topological order dynamic programming. To reconstruct the actual sequence, store predecessor pointers for each node and backtrack from the node with the maximum distance.

Pro tip: Clarify upfront whether the graph is guaranteed acyclic and whether multiple critical paths exist—if so, ask which one to output or if any is acceptable. Also, mention that you can handle multiple test graphs by wrapping the algorithm in a loop and resetting state.

1. Clarify input format and constraints

Confirm how tasks, dependencies, and durations are represented (e.g., adjacency list, edge list) and whether the graph is guaranteed a DAG. Ask about output format for multiple graphs and tie-breaking rules.

2. Build graph and compute in-degrees

Construct an adjacency list with edge weights equal to task durations. Compute in-degrees for all nodes to prepare for topological sorting.

3. Topological sort and longest path DP

Perform topological sort (Kahn's algorithm or DFS). Process nodes in topological order, updating the longest distance to each neighbor and recording the predecessor that gives the maximum.

4. Reconstruct critical path

Identify the node with the maximum distance (critical path length). Backtrack using predecessor pointers to build the sequence of tasks from start to end.

5. Handle multiple test graphs and edge cases

Loop over each test graph, resetting data structures. Consider edge cases: empty graph, single node, disconnected components, and multiple critical paths.

Key Points to Mention

  • Topological sorting is essential for processing nodes in dependency order.
  • Dynamic programming recurrence: dist[v] = max(dist[u] + weight(u, v)) for all incoming edges u->v.
  • Predecessor tracking to reconstruct the actual path, not just the length.
  • Time complexity: O(V + E) for topological sort and DP, plus O(V) for backtracking.
  • Space complexity: O(V + E) for graph storage and O(V) for distance and predecessor arrays.
  • Handling multiple test graphs by iterating and resetting state between runs.

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