Your accumulator-passing walk over an account statement returns the per-entry balances in reverse — what in the rewrite causes that?

seniorshould knowfreq 38%

answer

which end the accumulator grows at
the earliest entry is added earliest
the base case returns it untouched
cheap insertion has a direction
one extra pass, still linear

basics

~20 s

The accumulator is extended at its cheap end before each recursive call, so the earliest entry is added first and ends up deepest, and the base case returns that collection untouched. The usual fix is one final reversing pass.

solid answer

~50 s

Order comes from when each value is added, and the rewrite changed that. In the unwinding version each balance was attached to the result of the recursive call, so values were assembled from the last entry backwards and came out in input order. In accumulator-passing style each balance is added to the accumulator before the next call, so the earliest entry is added first; if the accumulator is a sequence extended at its front — the constant-time end for a singly linked immutable list — the earliest entry sits deepest and the output is newest-first. The base case returns the collection unchanged, so nothing re-orders it later. The standard fix is to reverse once at the wrapper: one extra pass, so 2n steps for n entries, still linear. Appending at the far end instead would cost a spine copy per entry and make the walk quadratic.

Order comes from *when* each value is added, and the rewrite changed that. In the unwinding version each balance was attached to the result of the recursive call, so values were assembled from the last entry backwards and came out in input order. In accumulator-passing style each balance is added to the accumulator **before** the next call, so the earliest entry is added first; if the accumulator is a sequence extended at its front — the constant-time end for a singly linked immutable list — the earliest entry sits deepest and the output is newest-first. The base case returns the collection unchanged, so nothing re-orders it later. The standard fix is to reverse once at the wrapper: one extra pass, so 2n steps for n entries, still linear. Appending at the far end instead would cost a spine copy per entry and make the walk quadratic.

code

pseudocode · 8 lines

pseudocode

function balancesFrom(entries, balance, collected)
    if entries is empty
        return collected
    newBalance = balance + amount(first(entries))
    return balancesFrom(rest(entries), newBalance, prepend(newBalance, collected))

function balances(entries)
    return reverse(balancesFrom(entries, 0, emptyList))

go deeper

for a junior

Remember that a sequence built by adding to its front comes out reversed, and that a single reversing pass at the end restores the original order. Trace two entries by hand to see it.

for a middle

Explain why the rewrite changed the order: values are added before the recursive call rather than attached after it returns, and the base case hands the collection back untouched.

for a senior

Show the diagnosis and the cost reasoning together — exactly reversed with correct values points at the accumulator's end, and reverse-once is 2n steps while append-each is quadratic.

for a principal

The call you own is whether the reversed order should be fixed at all: a consumer that wants newest-first makes the extra pass pure waste, so the decision belongs at the boundary where the order is specified.

Why order changed at all

An accumulator whose value is a number hides this completely: a total is the same whichever way you accumulate it. An accumulator that retains a sequence exposes it, because a sequence records the order in which things were put into it.

The two shapes add values at opposite times:

Unwinding form. Each level computes its own value and attaches it to whatever the recursive call returned. The deepest call returns first, so the last entry's value is placed first and every earlier entry is attached in front of it as the calls return. The result comes out in input order without anyone arranging it.
Accumulator-passing form. Each level adds its value to the accumulator and then calls down. The first entry is added first, the second second, and the finished collection is returned by the base case untouched. If each addition goes to the front of the collection, the first entry ends up at the back.

Tracing it on a statement

Entries in date order with amounts +10 then -4, starting balance 0, prepending each running balance:

step	entry consumed	running balance	accumulator after the step
1	—	`0`	`[]`
2	`+10`	`10`	`[10]`
3	`-4`	`6`	`[6, 10]`
4	— (base case)	—	returns `[6, 10]` — newest first

The output is not scrambled and not sorted; it is exactly reversed, which is the signature of this cause rather than of a bug in the balance arithmetic itself.

Why it is prepending in the first place

On a singly linked immutable sequence, adding at the front is a constant-time operation that shares the whole existing sequence; adding at the far end must copy the spine, which costs a step per existing element. So a rewrite that appended n running balances one at a time would perform on the order of n²/2 copying steps for n entries, while prepending performs n constant-time steps. The reversal is the price of that choice, and it is a good trade.

The options when the order matters

Reverse once at the end, inside the wrapper. For n entries the walk is n steps and the reversal is another n, so 2n steps overall — still linear, and the constant is small. This is the default answer.
Have the consumer read it newest-first. A statement view that displays most recent first wants this order already, so the reversal would just be undone by the display layer.
Accumulate into a structure with cheap addition at both ends, so the order is right on arrival. This removes the pass at the cost of a heavier structure than a linked sequence.
Return the reversed order and say so in the name. Honest, and occasionally the right call for an internal helper; a poor one for anything a caller might mistake for chronological.

When the reversal is invisible

Where the accumulator holds a value produced by an order-insensitive combining step — a total, a count, a maximum — the reversal has no observable effect and there is nothing to fix. Two cautions on that:

With inexact arithmetic, a total accumulated in one direction can differ in its last digits from the same total accumulated in the other; the order is not observable in the structure but it is observable in the value.
A step that is order-sensitive in a subtler way — subtracting each entry from the running value, concatenating text — changes the answer, not merely its presentation. That is a correctness defect and no reversing pass repairs it.

How to recognise this in production

The symptom is distinctive: the collection is exactly reversed, the aggregate values inside it are individually correct, and the defect appeared in the same change that removed the deep-recursion problem. Before reaching for a sort, check which end the accumulator is extended at and what the base case returns. A sort by timestamp would also "fix" the output while costing more and hiding the real cause.

Where candidates slip

Expecting the accumulated sequence to keep input order, because the numbers inside it are right.
Blaming the base case, which returns the accumulator unchanged and is not where the order was decided.
Switching to appending at the far end, turning a linear walk into a quadratic one to avoid a single extra pass.
Claiming the reversing pass makes the whole walk quadratic; it adds one linear pass, not one per entry.
Sorting the output to restore order, which is more expensive and leaves the cause in place.

## Why order changed at all An accumulator whose value is a number hides this completely: a total is the same whichever way you accumulate it. An accumulator that **retains a sequence** exposes it, because a sequence records the order in which things were put into it. The two shapes add values at opposite times: - **Unwinding form.** Each level computes its own value and attaches it to whatever the recursive call returned. The deepest call returns first, so the last entry's value is placed first and every earlier entry is attached in front of it as the calls return. The result comes out in input order without anyone arranging it. - **Accumulator-passing form.** Each level adds its value to the accumulator and then calls down. The first entry is added first, the second second, and the finished collection is returned by the base case untouched. If each addition goes to the front of the collection, the first entry ends up at the back. ## Tracing it on a statement Entries in date order with amounts `+10` then `-4`, starting balance `0`, prepending each running balance: | step | entry consumed | running balance | accumulator after the step | |---|---|---|---| | 1 | — | `0` | `[]` | | 2 | `+10` | `10` | `[10]` | | 3 | `-4` | `6` | `[6, 10]` | | 4 | — (base case) | — | returns `[6, 10]` — newest first | The output is not scrambled and not sorted; it is exactly reversed, which is the signature of this cause rather than of a bug in the balance arithmetic itself. ## Why it is prepending in the first place On a singly linked immutable sequence, adding at the front is a constant-time operation that shares the whole existing sequence; adding at the far end must copy the spine, which costs a step per existing element. So a rewrite that appended n running balances one at a time would perform on the order of n²/2 copying steps for n entries, while prepending performs n constant-time steps. The reversal is the price of that choice, and it is a good trade. ## The options when the order matters 1. **Reverse once at the end**, inside the wrapper. For n entries the walk is n steps and the reversal is another n, so 2n steps overall — still linear, and the constant is small. This is the default answer. 2. **Have the consumer read it newest-first.** A statement view that displays most recent first wants this order already, so the reversal would just be undone by the display layer. 3. **Accumulate into a structure with cheap addition at both ends**, so the order is right on arrival. This removes the pass at the cost of a heavier structure than a linked sequence. 4. **Return the reversed order and say so in the name.** Honest, and occasionally the right call for an internal helper; a poor one for anything a caller might mistake for chronological. ## When the reversal is invisible Where the accumulator holds a value produced by an order-insensitive combining step — a total, a count, a maximum — the reversal has no observable effect and there is nothing to fix. Two cautions on that: - With inexact arithmetic, a total accumulated in one direction can differ in its last digits from the same total accumulated in the other; the order is not observable in the structure but it is observable in the value. - A step that is order-sensitive in a subtler way — subtracting each entry from the running value, concatenating text — changes the *answer*, not merely its presentation. That is a correctness defect and no reversing pass repairs it. ## How to recognise this in production The symptom is distinctive: the collection is exactly reversed, the aggregate values inside it are individually correct, and the defect appeared in the same change that removed the deep-recursion problem. Before reaching for a sort, check which end the accumulator is extended at and what the base case returns. A sort by timestamp would also "fix" the output while costing more and hiding the real cause. ## Where candidates slip - Expecting the accumulated sequence to keep input order, because the numbers inside it are right. - Blaming the base case, which returns the accumulator unchanged and is not where the order was decided. - Switching to appending at the far end, turning a linear walk into a quadratic one to avoid a single extra pass. - Claiming the reversing pass makes the whole walk quadratic; it adds one linear pass, not one per entry. - Sorting the output to restore order, which is more expensive and leaves the cause in place.

When does the reversed order not matter at all?
When the accumulator holds a value produced by an order-insensitive combining step — a total, a count, a maximum — the reversal is not observable in the structure, because no sequence is retained. Even then, with inexact arithmetic a total accumulated in the opposite direction can differ in its last digits, so "not observable" is about the shape rather than the exact bits.
Why not append each balance to the end of the accumulator instead of prepending?
On a singly linked immutable sequence, adding at the far end copies the spine, so one append costs a step per element already collected and n appends cost on the order of n² steps. Prepending is constant time, so the idiomatic shape is to prepend n times and reverse once — 2n steps in total.

saying these in an interview costs you the question

Expects the accumulated sequence to keep the input's order
Blames the base case rather than the end being extended
Fixes the order by appending, making the walk quadratic
Claims a final reversing pass makes the walk quadratic
Sorts the output instead of addressing the cause
Assumes order never matters because the total is unchanged

Your accumulator-passing walk over an account statement returns the per-entry balances in reverse — what in the rewrite causes that?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Why order changed at all

Tracing it on a statement

Why it is prepending in the first place

The options when the order matters

When the reversal is invisible

How to recognise this in production

Where candidates slip

▾common follow-ups2 questions

▾red flags6 flags

Why order changed at all

Tracing it on a statement

Why it is prepending in the first place

The options when the order matters

When the reversal is invisible

How to recognise this in production

Where candidates slip

answer

go deeper