A work-list loop breaks as soon as it finds a conflict — what must hold at that exit point?
answer
- a second way out of the loop
- the preserved property still holds there
- this exit's condition is not the normal one
- property and exit condition imply the tail
- every path must set what the tail reads
basics
~20 sAt that exit, the property the loop preserves on every pass together with the condition that fired the break must imply whatever the code after the loop assumes. The normal exit condition — the work list emptied — is false there, so the tail cannot rely on it.
solid answer
~50 sAn early exit is a second way out, and it carries its own obligation. Whatever the body preserves on every pass is still true the instant the jump fires — a `break` does not suspend it — but the condition that holds there is the *break's* condition, not the loop's normal one. So the tail of the routine may conclude only what those two together give you: here, that a conflicting item was found and that every item examined before it was conflict-free. It may **not** assume the work list was drained, because it was not. In practice the check is mechanical: for each exit, write the condition true at that point, and read the code after the loop asking whether it holds under that condition — including whether every variable it reads was assigned on that path.
code
pseudocode · 9 linesconflict = none // set for the normal exit
for each item in pending:
if conflicts_with(installed, item):
conflict = item
break // exit condition: this item conflicts
// after the loop:
// conflict is none -> the list was walked, nothing conflicts
// conflict is set -> that item conflicts, earlier ones did notgo deeper
Know that leaving a loop early means the loop's normal stopping condition did not happen, so anything written after the loop has to make sense in both cases.
Be able to state, for each exit, the condition that is true there, and then read the tail against both. This is the tier where an interviewer expects the check rather than an opinion about early exits.
Demonstrate it on messy code: find the variable the early exit never sets, or the line after the loop that only makes sense on the normal exit. That review habit is the deliverable.
Set the line for the team: early exits are fine when each one corresponds to a condition someone can name, and the cost you are budgeting is one more exit condition per jump for every future reader.
## A loop has as many exits as it has jumps out The familiar reading of a loop has one way out: the condition goes false. Add a `break` and there are two, and the code after the loop runs after **either**. That is the whole content of the question. What makes a `break` safe is not that it is short or that it is near the top; it is that you can state what is true when it fires and check the tail against it. Three things are in play at any exit: - **The property the body preserves.** Whatever the loop keeps true on every pass is true at the jump too. A jump out of the body does not suspend it — the body simply stops early, and the property was established before the skipped part. - **The exit condition.** This differs per exit. On the normal exit it is the loop condition turned false. On a `break` it is the condition guarding the `break`. - **What the tail assumes.** The postcondition the rest of the routine is written against. The obligation is: preserved property **and** exit condition must together imply what the tail assumes — separately, at every exit. ## Working the two exits of a conflict search Suppose the loop walks pending items and keeps true: *every item examined so far is conflict-free.* It breaks on the first conflicting item, recording it. | Exit | Condition true there | What the tail may conclude | |---|---|---| | Normal | no items left to examine | every item is conflict-free; there is no conflict | | break | this item conflicts | a conflict exists, and it is the first one in order | Both conclusions are useful and they are **different**. Code after the loop that says "the list is empty, so we are clear to install" is reading the normal exit's condition on a path where it is false. That is the defect an early exit most often introduces, and it is invisible if you only ever trace inputs that do not conflict. ## Every path must set what the tail reads The second, more mundane obligation: a variable the tail reads must be assigned on **every** path out. A search loop that assigns its result only after the loop — or only inside the `break` — leaves the other path reading whatever was there before. Two disciplines cover it: 1. Initialise the result before the loop to the value that means "normal exit happened", and let the `break` path overwrite it. 2. Or assign on both paths explicitly, so that the reader sees two assignments and no default. The first is usually clearer, because it makes "nothing found" a stated value rather than an accident of initialisation. ## An off-by-one is an exit-condition bug, not a tracing bug The same discipline finds the classic index error without tracing anything. Say the body reads the item at position `i`, and valid positions run from the first up to one before the count. The body may only run when `i` is a valid position — so that must be implied by the loop's condition. If the condition admits `i` equal to the count, it does not imply it, and the very last pass reads outside the range. You find that by comparing the condition against what the body requires, in one reading. A hand trace only tells you about the inputs you happened to pick, and the failing pass is the one people skip. ## Does an early exit break the single-exit rule? The old **single-entry/single-exit** discipline was written against jumps that could land anywhere, including backwards and into the middle of another block. A `break` is nothing like that: it is one forward jump to a destination the reader can see without searching — the statement after the loop. The honest position is not "early exits are forbidden" but "each early exit adds an exit condition somebody has to discharge". One that removes a duplicated read — the loop-and-a-half shape, where you can only tell whether there is work after you have already fetched it — usually pays for itself. Several scattered through a long body, each with a different condition, usually do not. ## The interview signal A weak answer says "break just leaves the loop". A strong one names the two exits, states the condition at each, and then checks the code after the loop against both. That is the move that generalises: it is the same check whether the loop exits early, exits normally, or has no early exit at all.
- What is the loop-and-a-half problem, and how does an early exit address it?Some loops can only tell whether there is work after they have already fetched something, so the test belongs in the middle of the body. Writing it with the test at the top forces the fetch to appear twice — once before the loop and once at the foot of the body — and the two copies drift apart. A mid-body exit removes the duplication, at the cost of one exit condition to discharge.
- How does reasoning about the exit condition find an off-by-one that a hand trace misses?You compare what the body requires against what the loop condition guarantees. If the body reads the item at a position, the condition must imply that position is valid; a condition that admits one position past the end does not, so the last pass reads out of range. That comparison covers every pass at once, while a trace only covers the inputs you chose.
- The tail says the work list is empty after the loop. Why is that wrong here?Because it is the normal exit's condition, and the break path leaves items unexamined. Any conclusion that depends on the list being drained has to be moved under the normal-exit branch, or replaced by something both exits establish.
saying these in an interview costs you the question
- Thinks a break suspends what the loop keeps true
- Lets the code after the loop assume the list was drained
- Reads a result variable the early-exit path never assigned
- Says any early exit violates single-entry/single-exit and must go
- Checks the exit by tracing two sample inputs by hand
- Discharges only the normal exit and ignores the jump