A step where each row's value depends on the previous row's result — when does that still have a whole-column form?
answer
- ask whether it reassociates
- blocks, combine, fix up
- prefix scan against general recurrence
- an associative operator and an identity
- shipped primitive, not merely possible
basics
~20 sA carry that folds under an associative operator — addition, maximum, last-known-value — is a prefix scan: it splits and recombines, so one compiled pass can produce it. A carry whose next state is an arbitrary function of the previous one cannot.
solid answer
~50 sThe test is **associativity**, not whether the step looks sequential. If the carry is a fold under an associative operator, the work splits: compute each block independently, combine the block summaries, then fix up each block with what arrived from its left. That is a prefix scan, and running totals, running extrema and carrying the last known value forward are all of that shape — several designs ship them as compiled whole-column primitives, and you should use one when it exists. If the next state is an arbitrary function of the previous one — an accumulator that resets when it crosses a threshold, a value clamped and fed back, a state machine whose transition depends on accumulated state — nothing compact summarises a block independently of what enters it, so there is nothing to combine and a loop is the honest answer. Two caveats: what is mathematically splittable is not always shipped as a primitive, and over floating point a split scan differs in the last digits.
go deeper
Recall that most element-wise work has no memory of the previous row, and that a step carrying state from row to row is the exception that needs a closer look before it is rewritten.
Explain associativity as the property that lets work be split: if regrouping the steps gives the same answer, block summaries can be combined and a single pass exists for the whole column.
Classify the carry in front of you instead of reciting a rule, and know that a compiled primitive may exist for one shape of carry and not for another on the same tool.
Decide what the codebase does with genuinely sequential steps — isolate each behind one reviewed function or accept loops scattered through transforms — and budget for the floor they set on every run.
## The test is associativity, not appearance "Each row needs the previous row's answer" describes a great many computations, and it does not by itself decide anything. The question that decides is whether the carry's combining operator is **associative**: does grouping the steps differently give the same answer? Written out, associativity says that combining a with b and then with c gives what combining a with the result of b and c gives. If that holds, the computation can be cut anywhere and glued back together. If it does not, it cannot. This matters because the whole-column form exists exactly when the work can be split, and the reason a compiled pass can be fast — and, on some engines, spread across threads — is that splitting is legal. ## Why associativity buys a split A prefix scan produces, for each position, the fold of everything up to and including it. An associative operator lets that be computed in three phases rather than one sequential walk: 1. **Per block, independently.** Each block computes its own local scan and its own total, using nothing from any other block. 2. **Combine the summaries.** Fold the block totals together to learn what arrives at the left edge of each block. 3. **Fix up.** Apply each block's incoming value to its local scan. Every phase is cheap and the first and third are per-value work over packed bytes. That is the mechanism behind a compiled running-total primitive; it is not a special case of magic, it is associativity being exploited. ## The carries that pass the test | carry | combining operator | splittable? | |---|---|---| | running total | addition | yes | | running maximum or minimum | maximum, minimum | yes | | running count of qualifying rows | addition | yes | | carrying the last known value forward | take the newer value unless it is absent | yes | | running combination of flags | bitwise and, bitwise or | yes | | an accumulator reset when it crosses a threshold | none that composes | no | | a value clamped, then fed back into the next step | none that composes | no | | a state machine whose transition reads the accumulated state | none that composes | no | Carrying the last known value forward is the one people misclassify most often, because it reads as pure sequence. Its operator is "take the newer value unless it is absent, in which case keep the older", and that composes: a block is summarised by its own filled result plus the last known value it ends with, and combining is applying the left neighbour's ending value to any leading absences. ## The interesting middle Some recurrences are splittable in principle without any tool shipping a primitive for them. A step of the form "multiply the previous result by something and add something" is an affine function of the previous state, and composing two affine functions gives another affine function — so block summaries do exist and the scan is possible. Whether that helps you depends entirely on whether the tool in front of you exposes a way to express it. If it does not, you are back to a loop even though the mathematics permits better. Say both parts in an interview: the theoretical classification, and the practical one. ## When the test fails When no compact block summary exists, accept it and write the loop deliberately: - Keep the loop as tight as the host language allows, reading from and writing to packed storage rather than rebuilding a record per step. - If the tool offers a compiled per-record path — a way to hand the body to something that compiles it rather than interpreting it per value — that is usually the largest available win, and it does not change the computation. - Isolate the sequential step behind one named function with its own check, so the one part of the pipeline that resists rewriting is also the part nobody quietly reimplements. - Expect it to set a floor: it is the step that does not shrink when everything around it gets faster. ## Two things that are easy to get wrong - **Over-classifying.** "It depends on the previous row, therefore no whole-column form exists" is the single most common wrong answer, and writing a hand loop for a running total when a compiled scan primitive is sitting there is the visible symptom. - **Under-classifying.** Declaring an operator associative without checking. The cheap empirical test is to compute a short input straight through, then compute it in two halves and combine the halves the way a split pass would. If the combined answer needs information the block summary does not carry, the operator is not associative. One last consequence worth carrying: over floating-point values, splitting and recombining a scan changes which roundings happen, so a split running total will differ in its last digits from a strictly sequential one. That is expected, not a defect — but it means the rewrite cannot be checked against the old code with an equality.
- How do you test whether a carry is associative without proving it formally?Take a short input, compute it straight through, then compute it in two halves and combine the halves the way a split pass would. If several different split points all agree with the straight-through answer, the operator reassociates. If combining needs information the block summary does not carry, it does not.
- Carrying the last known value forward looks sequential — why does it split?Its operator is "take the newer value unless it is absent, in which case keep the older one", and that composes. A block can be summarised by its own filled result plus the last known value it ends with, and combining is applying the previous block's ending value to any leading absences of the next.
- What does a genuinely sequential step cost beyond its run time?It sets a floor no rewrite removes, so it is the part of the job that does not shrink when the hardware or the rest of the pipeline improves. It is also the step most likely to be reimplemented differently by the next person, which is why keeping it in one named place with its own check usually beats shaving its constant factor.
saying these in an interview costs you the question
- Says any dependence on the previous row rules out a whole-column form.
- Writes a hand loop for a running total when a compiled scan exists.
- Calls a carry associative without checking that regrouping gives the same answer.
- Assumes every design ships the same set of scan primitives.
- Forgets that splitting a floating-point scan moves the last digits.