Work Order Lead Time: Critical Path Through an Operations DAG to Shipping
Company: Hadrian
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
A manufacturing work order is modeled as a directed acyclic graph. Each node is an operation, such as machining or inspection, that takes a whole number of days. Each edge `(source, target)` is a dependency: operation `target` cannot start until operation `source` has finished. Every path ends at a single terminal node of type `"shipping"`.
Operations that do not depend on each other can run at the same time, so the total lead time of the work order is its critical path length: the longest path from any starting node (a node with no incoming edges) to the shipping node. Return the lead time.
### Function Signature
```python
def work_order_lead_time(nodes: list[tuple[str, str, int]], edges: list[tuple[str, str]]) -> int:
```
Each node is `(id, type, duration)`, with `duration` in days, and each edge is `(source, target)`.
### Rules
- The length of a path is the sum of the durations of all nodes on it, including its first node and the shipping node.
- A starting node is a node with no incoming edges. If the work order contains only the shipping node, that node alone forms the only path.
- Return the maximum length over all paths that begin at a starting node and end at the shipping node.
- Node types other than `"shipping"` do not affect the result.
### Constraints
- `1 <= len(nodes) <= 10^4`
- `0 <= len(edges) <= 5 * 10^4`
- `0 <= duration <= 1000` for every node.
- Node ids are unique, nonempty strings of at most 20 characters. Types are nonempty lowercase strings.
- Exactly one node has type `"shipping"`, and it has no outgoing edges.
- Every edge connects two different existing nodes, and no edge appears twice.
- The graph has no cycles, and every node has a directed path to the shipping node.
- The answer is at most `10^7`.
### Examples
**Example 1**
```text
Input: nodes = [("m1", "machining", 2), ("m2", "machining", 4), ("i1", "inspection", 1),
("m3", "machining", 3), ("i2", "inspection", 2), ("ship", "shipping", 0)]
edges = [("m1", "i1"), ("m2", "i1"), ("i1", "m3"), ("i1", "i2"),
("m3", "ship"), ("i2", "ship"), ("m1", "i2")]
Output: 8
```
The starting nodes are `m1` and `m2`. The longest path is `m2 -> i1 -> m3 -> ship`, with length 4 + 1 + 3 + 0 = 8. The other paths are shorter: for example, `m1 -> i1 -> m3 -> ship` has length 6, `m2 -> i1 -> i2 -> ship` has length 7, and `m1 -> i2 -> ship` has length 4.
**Example 2**
```text
Input: nodes = [("x", "machining", 1), ("y", "machining", 1), ("z", "inspection", 1),
("w", "machining", 5), ("ship", "shipping", 1)]
edges = [("x", "y"), ("y", "z"), ("z", "ship"), ("w", "ship")]
Output: 6
```
The chain `x -> y -> z -> ship` has more operations but length 4, while `w -> ship` has length 5 + 1 = 6.
**Example 3**
```text
Input: nodes = [("ship", "shipping", 2)], edges = []
Output: 2
```
The shipping node is the only node, so the lead time is its own duration.
Overview: A manufacturing work order is modeled as a directed acyclic graph of operations with durations in days, and every path ends at one shipping node. Compute the total lead time as the critical path length from any starting operation to shipping. It tests graph modeling, dependency ordering and longest-path reasoning.
Read the full Hadrian Software Engineer interview experience this question came from
A manufacturing work order is modeled as a directed acyclic graph. Each node is an operation, such as machining or inspection, that takes a whole number of days. Each edge `(source, target)` is a dependency: operation `target` cannot start until operation `source` has finished. Every path ends at a single terminal node of type `"shipping"`.
Operations that do not depend on each other can run at the same time, so the lead time of the work order is its critical path length: the longest path from any starting node (a node with no incoming edges) to the shipping node. Implement `work_order_lead_time(nodes, edges)` and return the lead time.
Each node is `(id, type, duration)`, with `duration` in days, and each edge is `(source, target)`, where `source` and `target` are node ids.
### Rules
- The length of a path is the sum of the durations of all nodes on it, including its first node and the shipping node.
- A starting node is a node with no incoming edges. If the work order contains only the shipping node, that node alone forms the only path.
- Return the maximum length over all paths that begin at a starting node and end at the shipping node.
- Node types other than `"shipping"` do not affect the result.
- Nodes and edges may be listed in any order.
### Input and output
- Python: `nodes` is a list of `(id, type, duration)` tuples and `edges` is a list of `(source, target)` tuples.
- JavaScript: each node is an array `[id, type, duration]` and each edge is an array `[source, target]`.
- Java: `nodes` is a `java.util.List<java.util.List<Object>>`; each inner list holds `id` (a `String`), `type` (a `String`) and `duration` (a `Number`). `edges` is a `java.util.List<java.util.List<String>>` whose inner lists hold `source` and `target`.
- C++: `nodes` is a `std::vector<std::tuple<std::string, std::string, int>>` and `edges` is a `std::vector<std::vector<std::string>>` whose inner vectors hold `source` and `target`.
- Return one integer, the lead time. The answer is at most 10^7, so it never exceeds 2^31 - 1 and fits in a 32-bit `int` in Java and C++.
### Constraints
- `1 <= len(nodes) <= 10^4`
- `0 <= len(edges) <= 5 * 10^4`
- `0 <= duration <= 1000` for every node.
- Node ids are unique, nonempty strings of at most 20 characters. Types are nonempty lowercase strings.
- Exactly one node has type `"shipping"`, and it has no outgoing edges.
- Every edge connects two different existing nodes, and no edge appears twice.
- The graph has no cycles, and every node has a directed path to the shipping node.
- The answer is at most `10^7`.
### Example 1
```text
Input: nodes = [("m1", "machining", 2), ("m2", "machining", 4), ("i1", "inspection", 1),
("m3", "machining", 3), ("i2", "inspection", 2), ("ship", "shipping", 0)]
edges = [("m1", "i1"), ("m2", "i1"), ("i1", "m3"), ("i1", "i2"),
("m3", "ship"), ("i2", "ship"), ("m1", "i2")]
Output: 8
```
The starting nodes are `m1` and `m2`. The longest path is `m2 -> i1 -> m3 -> ship`, with length 4 + 1 + 3 + 0 = 8. The other paths are shorter: `m1 -> i1 -> m3 -> ship` has length 6, `m2 -> i1 -> i2 -> ship` has length 7, `m1 -> i1 -> i2 -> ship` has length 5, and `m1 -> i2 -> ship` has length 4.
### Example 2
```text
Input: nodes = [("x", "machining", 1), ("y", "machining", 1), ("z", "inspection", 1),
("w", "machining", 5), ("ship", "shipping", 1)]
edges = [("x", "y"), ("y", "z"), ("z", "ship"), ("w", "ship")]
Output: 6
```
The chain `x -> y -> z -> ship` has more operations but length 4, while `w -> ship` has length 5 + 1 = 6.
Constraints
- 1 <= len(nodes) <= 10^4
- 0 <= len(edges) <= 5 * 10^4
- 0 <= duration <= 1000 for every node.
- Node ids are unique, nonempty strings of at most 20 characters. Types are nonempty lowercase strings.
- Exactly one node has type "shipping", and it has no outgoing edges.
- Every edge connects two different existing nodes, and no edge appears twice.
- The graph has no cycles, and every node has a directed path to the shipping node.
- The answer is at most 10^7, so it fits in a signed 32-bit integer.
Examples
Input: ([('ship', 'shipping', 2)], [])
Expected Output: 2
Explanation: Example 3: only the shipping node, so the lead time is its own duration 2.
Input: ([('ship', 'shipping', 0)], [])
Expected Output: 0
Explanation: Minimum valid input with a zero-duration shipping node: the only path has length 0.
Hints
- Operations that do not depend on each other run at the same time, so the lead time is set by the slowest chain of dependencies, not by the total of all durations or by how many operations a path has (see Example 2).
- A path's length counts node durations, not edges, and it includes both the starting node's duration and the shipping node's duration.
- Nothing guarantees that the nodes or the edges are listed in dependency order.