The build DAG's critical path, not its topological order, bounds wall-clock time — how do you act on that?
answer
- one order is not a schedule
- what happens with unlimited workers?
- the longest chain never compresses
- compare it with total work over workers
- one linear pass in topological order
basics
~20 sA topological order is one serialisation, not a schedule. The floor on wall-clock time is the longest weighted path through the graph, and with W workers also total work divided by W. Act on whichever floor binds.
solid answer
~50 sMeasure both lower bounds before spending anything. The **critical path** is the longest chain of dependent stages weighted by duration, computed in one linear pass in topological order: the earliest start of a node is the maximum over its predecessors of their earliest start plus their duration. The **work bound** is total duration divided by worker count. Wall-clock time can never drop below either. If work/W dominates, buying workers helps and the fix is a purchase. If the critical path dominates, adding workers changes nothing — the fix must change the graph: split a hub stage everything waits on, parallelise inside the longest stage, cache or skip stages whose inputs are unchanged, or delete a dependency edge that was never real. Track the critical path as a metric with the owning teams named, because the chain usually crosses team boundaries and no single team can see it.
go deeper
Grasp the distinction first: a topological order says what may run before what, while a schedule says what runs when and on which worker. Independent stages can run at the same time even though the order lists them one after another.
Be able to compute the earliest start of every stage in one linear pass in topological order and name the resulting longest weighted path. Know that this is O(V + E) on a DAG and that slack falls out of the reverse pass.
Diagnose a real pipeline: measure the critical path and total work, compare against worker count, and say which floor binds before proposing anything. Point at the specific hub stage or stale dependency edge that would actually shorten the chain.
Own the tradeoff between buying capacity and restructuring a graph the whole organisation edits. Make the critical path a tracked, owned metric across team boundaries, gate new edges on it, and set the stopping point by the latency budget rather than by how much is left to optimise.
## The confusion this question exists to break A topological order answers "in what sequence *could* I run everything one at a time". A build farm does not run things one at a time. The order is a valid serialisation, but treating it as the schedule silently assumes one worker, and then the natural conclusion — "the build takes the sum of all stage durations" — is wrong in both directions: parallel execution is faster, and adding workers past a point buys nothing. ## The two lower bounds Give each node a duration. Two quantities bound the wall-clock makespan from below, and neither can be beaten by any scheduler: **1. The critical path (span).** The longest *weighted* path through the DAG. Every node on it must wait for its predecessor on that path, so those durations add up no matter how many workers exist. This is the bound that holds even with unlimited workers. **2. Work over workers.** Total duration of all nodes divided by W. You cannot execute more than W units of work per unit time. Makespan >= max(critical path, work / W). A good greedy scheduler — hand any free worker any ready node — lands within a constant factor of optimal for this problem, so these bounds are not merely theoretical floors; they predict real behaviour well enough to plan with. ## Computing the critical path One linear pass. Process nodes in topological order and compute the earliest start: ``` earliest[u] = 0 for every source earliest[v] = max over predecessors u of ( earliest[u] + dur[u] ) ``` Because every predecessor is processed before the node itself, each value is final when read. Total cost O(V + E) — the same as ordering. Longest path is intractable on general graphs, where you can go around a cycle forever; on a DAG it is linear, and that difference is worth being able to state. Recover the path itself by remembering which predecessor supplied each maximum and walking back from the last-finishing node. The complementary quantity, the *latest start* that keeps the makespan unchanged, is the same pass over the reversed graph. The difference between latest and earliest start is a node's **slack**; nodes with zero slack are exactly the critical ones. Slack is what tells you which stages are safe to leave slow. ## Reading the numbers as a decision | Observation | What it means | Where money goes | |---|---|---| | work/W >> critical path | Worker-starved | Add workers; the graph is fine | | critical path >> work/W | Chain-bound | Restructure the graph; workers won't help | | The two are close | Balanced | Chase both, small gains from each | The classic incident is doubling the fleet and watching build time move by a few percent. That is the second row, and the numbers would have predicted it for free before the invoice. ## Levers when the chain binds - **Split a hub.** One coarse stage that half the graph waits on is both a long node and a synchronisation barrier. Splitting it into independently consumable outputs shortens the chain and widens the graph at once. - **Parallelise inside the longest node.** The critical path counts durations; halving the slowest node's duration halves its contribution. - **Cut a fake edge.** Dependency graphs accumulate edges added defensively that no longer reflect a real input relationship. Removing one can collapse a long chain. - **Cache or skip.** A stage whose inputs are unchanged contributes zero when its result is reused, which shortens the effective path on most runs even if the worst-case path is unchanged. ## The organisational half This is why the question is a leadership one. The critical path almost always crosses team boundaries: each team sees its own stage as fast, and nobody owns the chain. So the durable move is not the one-off refactor, it is making the path *visible and owned* — publish it per run with the responsible teams named, alarm on regressions, and require that a new dependency edge on the critical path be justified. Otherwise the chain regrows within a quarter and the next response is another fleet purchase. The other judgement is knowing when to stop. If the critical path is twenty minutes and the latency budget is thirty, further graph surgery is spending engineering time to move a number nobody is waiting on. Bound the effort by the budget, not by how satisfying the optimisation is.
- How do you compute the critical path, and why is longest path cheap here?One pass in topological order: a node's earliest start is the maximum over its predecessors of their earliest start plus their duration, and every predecessor is already final when you read it. That is O(V + E), plus a back-walk through the recorded maxima to recover the path. Longest path is intractable on general graphs because cycles can be traversed repeatedly; acyclicity is exactly what removes that.
- How do you tell a team that doubling the build fleet will not help?Show both floors. Give the total work divided by the current worker count and the critical path measured on the same runs. If the path dominates, present the chain stage by stage with the owning teams named — that converts a budget argument into a concrete list of stages to split, cache, or unhook, and it usually reveals that no single team could have seen the problem alone.
- Which stages should you deliberately leave slow?The ones with slack — where the latest start that preserves the makespan is later than the earliest possible start. Computing latest starts is the same linear pass over the reversed graph. A stage with ten minutes of slack can get twice as slow before it affects wall-clock time, so optimisation effort spent there returns nothing and is better redirected onto the zero-slack chain.
- When should you stop optimising the graph?When the critical path is comfortably inside the latency budget the organisation actually needs, with margin for growth. Past that point graph surgery costs engineering time and adds structural complexity that a future contributor must understand, in exchange for moving a number nobody is waiting on. Keep the metric monitored so regressions surface, and spend the effort elsewhere.
Nine people cannot deliver a baby in one month. Extra workers help only where work is genuinely independent; a chain of steps that must happen in sequence sets a floor no headcount can lower.
saying these in an interview costs you the question
- Treats the topological order as the schedule itself
- Says more workers always shorten wall-clock time
- Ignores total work divided by worker count
- Thinks longest path is intractable even on a DAG
- Optimises stages that have plenty of slack