skip to content

Every module in a build declares at least one prerequisite module; why must a dependency cycle exist?

level: seniorimportance: should knowfreq 38%

answer

  1. finiteness is doing the work
  2. name the largest object first
  3. a longest chain cannot be extended
  4. the last link must point inward
  5. n plus one visits over n modules

basics

~20 s

Because the module set is finite. Take a longest chain of distinct modules, each waiting on the next; the last module's prerequisite cannot be new without extending the chain, so it lies inside it and closes a cycle.

solid answer

~50 s

This is the **extremal principle**: instead of searching, name the largest object and let maximality do the work. Take a chain of distinct modules `m1` waits on `m2` waits on ... waits on `mk`, chosen as long as any such chain can be. Finiteness guarantees a longest one exists. Now `mk` has a prerequisite, by hypothesis. If that prerequisite were a module not already in the chain, the chain could be extended by one, contradicting the choice of a longest chain. So it is some `mj` already in the chain, and `mj ... mk mj` is a cycle. The same conclusion also follows by pigeonhole: follow one prerequisite per step for n steps among n modules and you have visited n + 1 modules, so one repeats. The extremal route proves existence; the walk hands you the actual cycle.

code

pseudocode · 13 lines
pseudocode
# n = number of modules; every module declares >= 1 prerequisite
find_cycle(start, n):
    visited = empty list
    m = start
    repeat n + 1 times:
        append m to visited
        m = any prerequisite of m        # exists by hypothesis

    # n + 1 entries drawn from n modules: some module occurs twice
    first  = smallest i such that visited[i] occurs again later
    second = the next index after first holding visited[first]

    return visited[first .. second - 1]  # a cycle, in wait order

go deeper

for a junior

Recall the two ingredients that force the conclusion: the set of modules is finite, and every one of them waits on something. Neither alone is enough, and no inspection of the data is needed.

for a middle

Explain the maximality step in your own words: a longest chain of distinct modules cannot be extended, so the last module's prerequisite must already lie inside the chain, which closes a cycle.

for a senior

Show that you can turn the argument into a diagnostic: the walk of n + 1 visits both bounds the search and produces the repeated module, so the guaranteed cycle becomes a printable error rather than a claim.

for a principal

Use it at the level of the format rule. A declaration rule that requires every module to name a prerequisite guarantees an unbuildable configuration for any finite set, which is an argument against the rule itself, not against a particular repository.

## The extremal move Most proof techniques act on a claim. The **extremal principle** acts on the *objects*: pick the largest, longest, heaviest or smallest one and then show that its extremality forbids something. It works because an extremal object cannot be improved by definition, so any construction that would improve it is impossible — and that impossibility is usually the whole argument. The prerequisite question is the clean case. The hypothesis is that **every** module declares at least one prerequisite, and the set of modules is finite. Nothing is known about which module waits on which. ## Running it on the build 1. Consider chains of **distinct** modules `m1, m2, ..., mk` where each waits on the next. Single modules are chains of length one, so at least one chain exists. 2. Chains have distinct entries, so no chain is longer than the number of modules. Lengths are therefore bounded, and **a longest chain exists**. 3. Fix one longest chain and look at its last module `mk`. By hypothesis it waits on something. 4. That prerequisite is either outside the chain or inside it. Outside is impossible: appending it would produce a longer chain of distinct modules, contradicting step 2. 5. So the prerequisite is some `mj` inside the chain, and `mj -> mj+1 -> ... -> mk -> mj` is a **cycle**. A module that waits on itself is included as a cycle of length one; nothing in the argument needs special-casing for it. ## The pigeonhole route to the same conclusion The same fact falls out of counting. Start anywhere and follow one prerequisite per step. Each step is possible because every module has at least one. After n steps over n modules the walk has visited n + 1 modules, and n + 1 visits drawn from n modules force a repeat. The stretch of the walk between the two visits to the repeated module is a cycle. | Route | What it needs | What it yields | |---|---|---| | Extremal (longest chain) | A bound on chain length, from finiteness | Existence of a cycle, with no cycle named | | Pigeonhole (walk n + 1 visits) | Every module has at least one prerequisite | A concrete cycle plus a bound on the work to find it | Both arguments use finiteness and the every-module-waits hypothesis; they differ in whether the conclusion comes with a witness attached. ## Where the argument breaks - **Drop finiteness and it fails.** Over an unbounded structure there may be no longest chain to name, and an infinite descending chain with no repeat is entirely consistent with every element having a successor. Finiteness is not decoration here; it is the load-bearing hypothesis. - **Drop the hypothesis and it fails.** If modules may declare zero prerequisites, the walk simply stops and the structure may be perfectly acyclic. Every element having at least one successor is exactly what turns *the chain ends here* into a contradiction. - **Edge counting does not substitute.** More wait-edges than modules does not force a cycle in general; an acyclic dependency set can carry far more edges than it has modules. What forces the cycle is that **every** module has an outgoing wait, not the total number of edges. - **It gives some cycle, not a distinguished one.** Neither route finds the shortest cycle, all cycles, or the one that matters to the user. It answers *is there one*, and the walk answers *here is one*. ## Why an engineer bothers The payoff is that a property of the data can be asserted **from the declaration rule alone**. If a build format requires every module to name at least one prerequisite, the format guarantees an unresolvable build for any finite module set — no scan required to know it, and no amount of testing will find the configuration that escapes it. That is a design-review conclusion, and it arrives before anyone has written a cycle detector. The second payoff is the bound. The walk converts *a cycle exists* into *a cycle is reachable within n + 1 visits from any starting module*, which is a worst-case cost for the diagnostic, and the repeated module is the error message. The extremal argument is what convinces you the search cannot come back empty; the walk is what you actually ship. ## The shape to carry away Whenever a claim is *something must exist* over a finite structure with a local guarantee at every element, try naming the extremal object first. The pattern recurs well beyond dependencies: the longest run, the heaviest item, the earliest deadline, the deepest nesting. In each case the question to ask is the same — **what would extending or improving this object require, and why is that impossible?**

  • Does the argument still work if the longest chain is not unique?
    Yes. It needs only that some chain of maximum length exists, which finiteness supplies; uniqueness is never used. Pick any chain that cannot be extended and the same contradiction applies, since extending it by an outside prerequisite would contradict its maximality.
  • What breaks if modules are allowed to declare zero prerequisites?
    The conclusion goes away entirely. A chain may simply end at a module with nothing to wait on, and the whole structure can be acyclic. The hypothesis that every module waits on something is exactly what stops the walk terminating and turns the end of a chain into a contradiction.
  • Which of the two routes gives you the cycle itself, and why does that matter?
    The walk. The extremal argument establishes existence without naming modules; following one prerequisite per step for n + 1 visits produces a repeated module, and the segment between its two occurrences is a concrete cycle you can print. Existence convinces the reviewer; the witness goes in the error message.

saying these in an interview costs you the question

  • Claims the dependency data must be inspected before a cycle can be asserted
  • Argues from edge count alone, which a large acyclic dependency set refutes
  • Applies the argument where chain length is unbounded and no longest chain exists
  • Thinks the longest-chain argument produces the shortest cycle
  • Treats a module that waits on itself as a separate case rather than a one-module cycle
  • Drops the every-module-waits hypothesis and still expects the conclusion