skip to content

Two teams computed the same payroll deduction with different expressions — how do you prove the two always agree?

level: middleimportance: should knowfreq 40%

answer

  1. tests sample, rewriting covers everything
  2. unfold both sides first
  3. normalise to a common form
  4. name every law you invoke
  5. rounding does not distribute

basics

~20 s

Unfold both expressions by substituting their definitions, then rewrite each using laws that genuinely hold for the operations involved until both reach a common form. Equal forms prove agreement for every input the laws cover.

solid answer

~50 s

You reason equationally rather than sample. Unfold both sides — replace each call by its body with arguments substituted — until both are written in the same vocabulary, then rewrite one or both using laws that actually hold for the operations involved, until the two reach a common form. So `gross - gross * 0.18 - gross * 0.05` normalises to `gross * (1 - 0.23)` by distributivity, and the two formulations agree for every input. The important discipline is naming the side conditions you leaned on: both functions must be pure, both must be defined over the inputs you care about, and every algebraic law you invoked must hold for the arithmetic as implemented — if each deduction is rounded to the nearest cent before subtraction, distributivity no longer applies and the two forms can differ by a cent. Tests can only sample inputs; a rewrite chain covers them all, but only under the laws you actually invoked.

code

pseudocode · 11 lines
pseudocode
deductionsA(gross) = gross * 0.18 + gross * 0.05
deductionsB(gross) = gross * 0.23

// Exact arithmetic: equal by distributivity
//   gross * 0.18 + gross * 0.05
// = gross * (0.18 + 0.05)
// = gross * 0.23

// Rounded to cents at each step, gross = 1015.15:
//   A: 182.73 + 50.76 = 233.49  -> net 781.66
//   B:                   233.48  -> net 781.67

go deeper

for a junior

The takeaway is that two differently written expressions can be shown equal by rewriting rather than by running examples, and that this only works when both are pure.

for a middle

Produce the chain: unfold both, factor with a named law, compare the forms, then state the assumptions you used. Naming the law is the part interviewers listen for.

for a senior

Show the failure case you have met — an algebraically valid rewrite that changed a rounded total — and the structural fix, usually pushing rounding to a single boundary.

for a principal

The decision is where exactness is held and where money is rounded, since that boundary determines which parts of the system stay amenable to this reasoning at all.

## Why proof rather than testing Two teams write the same deduction differently — one subtracts each component, the other applies a combined factor. Tests can show they agree on the inputs you thought of. Equational reasoning can show they agree on every input, and it costs a few lines. That is possible only because both expressions are pure: a call may be replaced by its value, and equals by equals, so the page can be manipulated like algebra. ## The method 1. **Unfold both sides.** Replace every call by its body with arguments substituted in, until both expressions are written in the same vocabulary of primitive operations. 2. **Normalise with laws you can justify.** Apply only laws the operations genuinely satisfy — distributivity, associativity, an identity element — and name each one as you use it. 3. **Compare the forms.** If both reach the same expression, they agree wherever the laws you used apply. 4. **Discharge the side conditions.** State the assumptions the chain rested on, out loud. This step is what separates a proof from a hopeful sketch. Worked on the payroll pair: - `deductionsA(gross) = gross * 0.18 + gross * 0.05` - `deductionsB(gross) = gross * 0.23` Unfolding gives `gross * 0.18 + gross * 0.05`; factoring by distributivity gives `gross * (0.18 + 0.05)`; reducing the constant gives `gross * 0.23`, which is `deductionsB` unfolded. Three rewrites, and the pair is settled for every `gross`. ## The side conditions, and the one that actually bites - **Both sides are pure.** If either does something on the way, they can compute the same number and still not be interchangeable. - **Both are defined over the inputs in question.** An expression that fails on negative pay is not equal to one that returns a number there; it is equal only on the domain where both produce a value. - **Every law invoked holds for the arithmetic as implemented.** This is the condition people skip. Distributivity is a law about exact numbers. Payroll arithmetic usually rounds to the smallest currency unit, and rounding does not distribute. That last one is worth a concrete case, because it is the difference between reasoning and hand-waving. Suppose each deduction is rounded to cents before it is subtracted, and gross pay is `1015.15`: | formulation | rewrite chain | result | |---|---|---| | component-wise | `182.727` rounds to `182.73`; `50.7575` rounds to `50.76`; `1015.15 - 182.73 - 50.76` | `781.66` | | combined factor | `233.4845` rounds to `233.48`; `1015.15 - 233.48` | `781.67` | The algebra was right and the conclusion was still false for this program, because the function being compared is not "multiply and subtract" — it is "multiply, round, subtract", and the rewrite step that factored the constant out assumed a law rounding does not satisfy. In payroll that cent is a reconciliation failure, not a rounding nuance. ## Reading the failure correctly It is tempting to conclude that equational reasoning is unreliable. The opposite is true: the reasoning is what **found** the discrepancy, by forcing someone to name the law being used and then ask whether the implementation satisfies it. The two useful responses are both structural: - **Reason about the function you actually have.** Include the rounding in the expression you unfold, and the two formulations simply are not equal — which is the correct conclusion. - **Move the rounding to one place.** Keep the calculation exact and round once at the boundary, and the algebraic laws hold across everything inside that boundary again, restoring the licence you wanted. ## What this is worth in an interview The expected answer is not a formal derivation. It is the shape: unfold, rewrite with named laws, compare, then state the assumptions. A candidate who adds the last step unprompted — "and this holds as long as both are pure, both are defined here, and the arithmetic really is associative" — is demonstrating the thing the question is testing, which is whether purity is a working tool for them or a slogan. The follow-up an interviewer likes here is "how would you have caught the cent?", and the good answer is that the proof attempt itself surfaced it, at a cost measured in minutes rather than in a quarter-end reconciliation.

  • If the two formulations turn out not to be equal, what has the attempt bought you?
    The exact input class where they diverge, and the rewrite step that assumed too much. That is far more actionable than a failing test, which tells you one input disagrees but not which law was wrong. It also usually suggests the fix: either reason about the real function including its rounding, or restructure so the law you wanted actually holds.
  • How do property-based tests relate to this kind of reasoning?
    They express the same equation as a check over generated inputs. They cannot prove it, but they explore far more of the input space than hand-picked cases and tend to find exactly the boundary values a rewrite chain glossed over. The usual practice is to reason first and encode the surviving equation as a property.
  • Does proving two expressions equal mean either may be used anywhere the other appears?
    Only where the proof's side conditions hold. Equal values do license substitution, but the chain was proved on a domain and under named laws; outside that domain — undefined inputs, different rounding, a wider numeric range — the equality was never established, so the swap is not licensed there either.

saying these in an interview costs you the question

  • Says passing tests on sample inputs proves the two expressions equal
  • Applies distributivity or associativity without asking whether the arithmetic satisfies it
  • Believes rounding is irrelevant to equational reasoning
  • Skips stating the domain on which the two are defined
  • Concludes the reasoning was useless because the rounded results differed