skip to content

An installer loop pops a dependency and may push new ones onto its work list — what argues it terminates?

level: middleimportance: must knowfreq 58%

answer

  1. something must shrink on every pass
  2. not the length of the work list
  3. strictly decreasing, and bounded below
  4. no infinite descending chain allowed
  5. a pair: unvisited first, list size second

basics

~20 s

A variant: a measure that strictly decreases on every pass and cannot fall forever. The work list's length is not one here, since a pass may push. Pair the count of never-yet-visited dependencies with the list's length and compare the pairs in order.

solid answer

~40 s

Termination is its own obligation, separate from what the loop computes, and you discharge it by exhibiting a **variant function**: a measure that strictly decreases on every pass, inside an ordering that admits no infinite descent. The obvious candidate — how many items are on the work list — fails immediately, because a pass pops one item and may push several. What does fall is a pair: the number of dependencies never yet visited, and, as a tiebreak, the work list's length, compared in that order. Popping an already-visited item leaves the first component alone and drops the second. Popping a fresh one marks it visited, so the first component drops whatever the pushes do to the list. Both components are non-negative integers, so the pair cannot descend forever, and the loop must stop.

code

pseudocode · 9 lines
pseudocode
visited = empty set
work = [root]
while work is not empty:
    item = pop(work)
    if item in visited:
        continue          // pop already made progress, so no hang
    add item to visited
    for each dep in dependencies_of(item):
        push(work, dep)

go deeper

for a junior

Grasp the shape of the claim: to believe a loop stops, point at something that gets strictly smaller every time round and cannot get smaller forever. Naming that measure is the whole skill.

for a middle

Be able to run the case split out loud: for each path the body can take, say what the measure does. This is the tier where interviewers expect a measure that survives a pass that pushes more work than it popped.

for a senior

Show where the argument rests on a data structure — here the visited set — and say what a cyclic input does to it. Diagnosing a hung drain loop means finding the case where the measure fails to fall.

for a principal

The judgment is about which loops get a written termination argument at all: the ones over inputs you do not control, over graphs that may cycle, or over work that feeds itself. Requiring the measure to be named in review is a cheap standard.

## Termination is a separate obligation A loop owes two different arguments, and confusing them is why so many loops are "proved" and then hang. One argument says what is true when the loop stops — the property the body preserves on every pass. The other says that it *does* stop. The second is never implied by the first: a loop can preserve something perfectly well while running forever. The standard way to discharge the second is a **variant function**: some quantity computed from the loop's state, which 1. is defined at the top of every pass, 2. strictly decreases from one pass to the next, and 3. lives in an ordering that permits no infinite descending chain — a **well-founded** ordering. All three matter. Drop the strictness and the loop can idle. Drop well-foundedness and the measure can shrink forever without ever running out. ## Why the obvious measure fails here The installer drains a work list: each pass pops one pending dependency, and if that dependency is new, its own dependencies are pushed. So the length of the work list is not a variant. A single pass can leave the list **longer** than it found it — pop one, push four — and a measure that grows on even one pass proves nothing at all. This is the point of the question: the loop plainly terminates for a finite dependency graph, and the first measure a candidate reaches for does not show it. ## A measure that actually falls Take the pair **(number of dependencies never yet visited, size of the work list)** and compare pairs by the first component, using the second only to break ties. Now check the two cases a pass can take: - The popped item is already visited. The visited set does not change, so the first component is unchanged; the pop removed one entry and nothing was pushed, so the second component drops by one. The pair falls. - The popped item is new. It is added to the visited set, so the first component drops by one — and once the first component has fallen, it does not matter what the pushes did to the list, because the second component is only consulted on a tie. The pair falls. Every pass falls into one of those two cases, so the pair strictly decreases on every pass. Both components are non-negative integers drawn from a finite universe of dependencies, so no infinite descent is possible. The loop terminates. | Candidate measure | Strictly falls each pass? | Well-founded? | Verdict | |---|---|---|---| | Size of the work list | no — a pass may push more than it popped | yes | not a variant | | Count of items already installed | no — an already-visited pop installs nothing | yes | not a variant | | A shrinking retry delay | yes, if it always shrinks | no — a positive quantity halves forever | not a variant | | (unvisited count, work-list size), in that order | yes, in both cases | yes — pairs of non-negative integers | a variant | ## The visited set is load-bearing Notice what the argument leans on. Without a visited set, a cycle in the dependency graph re-pushes items that were already handled, the first component never falls, and no variant exists — correctly, because the loop genuinely does not terminate. The visited set is not an optimisation here; it is the thing that makes the first component fall monotonically. When an interviewer asks what would break the argument, that is the answer: a repeat visit. ## Strictly decreasing is not the same as approaching zero The subtlest failure is a measure that decreases forever. Halve a positive quantity on every pass and it strictly decreases, yet it never reaches zero and the loop never stops. That is exactly what well-foundedness rules out, and it is why variants are normally phrased over counts, over the size of a finite set, or over tuples of such counts compared in order. If your measure lives in a dense range, the argument is not finished. ## What a good answer sounds like Name the measure, show it falls in **each** case the body can take, and say why it cannot fall forever. Two sentences of that beat five minutes of tracing sample inputs, because a trace only ever shows the passes you chose to write down, while the variant covers every pass there could be.

  • Remove the visited set. What happens to the termination argument?
    It collapses, and correctly so. With nothing recording what has been handled, a cycle in the dependency graph keeps re-pushing items, the unvisited count never falls, and no variant exists. The loop really can run forever on a cyclic graph, so the missing argument is reporting a genuine defect rather than a proof gap.
  • A measure halves on every pass and is always positive. Why is that not enough?
    Because strictly decreasing is not the same as running out. Halving a positive quantity gives an infinite descending chain that never reaches a floor, so the loop can keep going forever while the measure keeps falling. A variant has to sit in an ordering where no such chain exists — counts and tuples of counts do.
  • Does exhibiting a variant tell you the loop produced the right answer?
    No. It buys you termination and nothing else. What the loop computes comes from the property the body preserves on every pass, read together with the condition that was false when it stopped. A loop can terminate promptly and still return nonsense.

A librarian reshelving books: the height of the returns trolley proves nothing, because readers keep adding to it. What falls every time a book goes back is the number of books still off the shelf.

saying these in an interview costs you the question

  • Says the loop ends because the work list keeps getting shorter
  • Offers a measure that falls on some passes and not others
  • Accepts a measure that can shrink forever without a floor
  • Confuses the property preserved each pass with the reason it stops
  • Treats the visited set as a speed-up rather than the reason it halts