How do you state a property for a function that has no inverse to round-trip against?
answer
- State a rule, not an expected value
- Fence the answer instead of pinning it
- Doing it twice changes nothing
- A slow obvious version can judge the fast one
- Relate two runs when neither answer is known
basics
~10 sAssert a rule the output must satisfy rather than a specific value: an invariant or postcondition, idempotence, agreement with a simpler reference implementation, or a metamorphic relation between two runs on related inputs.
solid answer
~50 sFour shapes cover most functions with no inverse. An **invariant** states what must always be true of the output - a sorted result is ordered and is a permutation of the input; a capped queue never exceeds its cap. **Idempotence** states that applying the function twice equals applying it once, which fits normalisers, deduplicators and retryable handlers. A **reference comparison** runs an obviously correct but slow or naive implementation beside the real one and asserts the two agree. A **metamorphic relation** ties two runs together without knowing either answer: reordering the input must not change the set of results. The rule for all four is that the property must be derived from the requirement, not from the implementation - a property that restates the code is a tautology that fails only when the code fails to compile.
code
pseudocode · 8 linesproperty "the next-up queue respects its stated rules":
for each generated (library, pinnedIds, playedIds):
q = buildQueue(library, pinnedIds, playedIds)
assert size(q) <= 43
assert every id in q is present in library
assert no id appears twice in q
assert every pinned id in q precedes every unpinned id in q
assert no id in q is present in playedIdsgo deeper
Learn the four names - invariant, idempotence, reference comparison, metamorphic relation - and be able to give one concrete example of each. Naming them confidently is most of what is expected before mid-level.
Be ready to take a function the interviewer describes, such as a ranking or a deduplicator, and state three or four clauses on the spot, saying for each which plausible defect it would catch.
Show that you can spot the tautology and the over-strong clause in someone else's property, and explain the cost of each: one never fails, the other fails on legitimate input and destroys trust in the results.
Own the standard: which behaviours in the codebase justify a written reference implementation, how properties get reviewed for provenance against the requirement, and how the team decides that a clause has earned its maintenance cost.
### The problem: no inverse means no free oracle A round trip is easy because the input is its own expected value. Most functions have no inverse. You cannot un-sort, un-deduplicate or un-rank. So the oracle - the thing that decides the observed behaviour is wrong - has to come from somewhere else. Four shapes supply it, and a good candidate can name all four and say which one fits a given function. ### 1. Invariants and postconditions State what must be true of the output for every input, without saying what the output is. Take a playlist service that builds the next-up queue: it removes tracks already played, keeps pinned tracks ahead of the rest, and caps the queue at 43 entries. Nobody can predict the exact queue for a generated library of 8,000 tracks, but every result must satisfy: - length is at most 43; - every returned track came from the input (no invention); - no track id appears twice; - every pinned track that survived appears before every unpinned one; - the relative order of two unpinned tracks with different added-at timestamps matches the input order. That last one is where an **ordering assumption** gets caught: the first version of the queue builder relied on a structure with no defined iteration order, and two tracks added in the same second came back in an unpredictable order. Invariants are **partial oracles** - they do not pin the answer, they fence it. A weak invariant that runs on every generated input is worth far more than a perfect oracle you never get around to writing. ### 2. Idempotence `f(f(x)) == f(x)`. It fits normalisation, deduplication, canonicalisation, and any handler that a client may retry. It is cheap to state and catches a specific family of defects: a normaliser that trims one layer of whitespace per call, a deduplicator that only removes adjacent duplicates, a handler that appends the same track twice when a request is replayed. Note that idempotence says nothing about correctness of the first application - the function that returns an empty queue for everything is perfectly idempotent - so it belongs with an invariant, never alone. ### 3. Comparison against a simpler reference Write the obviously correct version - the naive nested-loop deduplicator, the brute-force ranking, the specification's formula written out longhand - and assert the two agree on every generated input. This is the strongest oracle available when it exists, because it pins the exact answer. Three conditions make it honest: the reference must be **independently written** from the requirement, not extracted from the optimised code; it may be arbitrarily slow, since it only runs in tests; and where the requirement genuinely allows several correct answers, compare the property that matters (the resulting set, the total, the ordering key) rather than demanding byte equality. A previously released version of the same code is a legitimate reference when you are refactoring rather than changing behaviour. ### 4. Metamorphic relations Sometimes no reference exists and no invariant is sharp enough. A metamorphic relation ties **two runs** together: you do not know either answer, but you know how the answers must relate when the inputs are related in a known way. For the queue builder: - shuffling the unpinned part of the input must not change the *set* of returned ids, only their order; - appending a track that is already present must not change the output at all; - pinning one more track can never lower the number of pinned tracks in the result; - removing a track that never appears in the output must leave the output identical. Metamorphic relations are the workhorse for search, ranking, recommendation and numeric code, where the right answer is unknowable but relationships between answers are not. ### The tautology trap The single most common defect in a hand-written property is that it restates the implementation. If the property computes the expected value with the same formula the code uses - or worse, calls the function under test to build the expectation - it passes for every input including wrong ones. The guard is provenance: derive each clause from the requirement or the specification, and ask whether a plausible defect exists that the clause would catch. If you cannot name one, the clause is decoration. The second most common defect is the over-strong property: asserting something the requirement never promised, such as a total ordering where the specification permits ties. That produces failures on legitimate inputs, and a suite whose failures are not trusted is worse than no suite. ### Choosing between them In practice, start with invariants because they are always available and never wrong when derived from the requirement; add idempotence wherever repetition is meaningful; reach for a reference implementation when one is cheap to write and pins the answer exactly; and fall back to metamorphic relations when the answer itself is beyond reach. Most real functions end up with two or three of these stated side by side, each fencing a different way the code could go wrong.
- What makes a reference implementation a legitimate oracle rather than a second copy of the bug?Independence of derivation. The reference must be written from the requirement, in the most obvious way, without borrowing the optimised code's structure or its lookup tables. It is allowed to be far too slow for production, since it runs only in tests. If it was extracted by simplifying the implementation, any misreading of the requirement is now present in both, and the comparison proves only that the misreading is consistent.
- Give an example of an over-strong property and say what it costs you.Asserting a total ordering on results when the requirement permits ties: legitimate inputs then fail, and each failure costs triage time to conclude that nothing is wrong. Repeated a few times, the team stops trusting failures from that property, which is worse than not having it. The fix is to assert only the ordering key the requirement actually fixes, and to leave the tie-break unconstrained.
- Why is idempotence never enough on its own?Because it constrains repetition, not correctness. A function that discards its input and returns the same empty result every time satisfies idempotence perfectly. It is a cheap and genuinely useful clause for normalisers, deduplicators and retryable handlers, but it must sit beside an invariant that ties the output back to the input - every returned element came from the input, nothing required was dropped.
saying these in an interview costs you the question
- Builds the expected value using the function under test
- Says properties only work for functions with an inverse
- Asserts an ordering the requirement leaves unspecified
- Copies the implementation into the test as a reference
- Treats idempotence alone as proof of correctness
- Cannot name a defect a given property clause would catch