Coding interviews
Reveal answer and reasoning
A comparer returns a negative, zero or positive sign describing order; the magnitude is not a distance contract. Antisymmetry of signs and transitivity are necessary for sorting to behave coherently. The fixture checks these laws over five boundary-heavy integer values and demonstrates why subtracting two integers is an unsafe general comparer implementation. Separate the relation being tested from the algorithm that consumes it.
Sorting assumes a coherent order; it does not repair an inconsistent comparator. Sign reversal and transitivity checks deliberately include equal values and numeric extremes because both are common blind spots in comparers written as compact arithmetic expressions.
The explicit law harness takes O(k cubed) time for k selected values and constant auxiliary state, which is appropriate for a small diagnostic fixture rather than a sorting algorithm. Passing these finite tests is evidence, not a proof for every custom type or combination of nullable values. Finite law tests are most valuable when the selected values target distinct equivalence classes: equal objects, adjacent values, extremes and nullable cases if supported.
Exhaustively testing a bounded domain can prove that finite domain's relation, but these five integers do not prove every possible custom comparator or mutable object state.
What a strong answer covers
- A comparer returns a negative, zero or positive sign describing order; the magnitude is not a distance contract.
- The triple loop increments the check counter for every triple even when the implication's premises are false.
- The explicit law harness takes O(k cubed) time for k selected values and constant auxiliary state, which is appropriate for a small diagnostic fixture rather than a sorting algorithm.
Common pitfall
Using x minus y, inconsistent null placement or culture-dependent text rules can violate an intended ordering contract. A comparator must also agree with equality classes expected by the consuming collection. Random examples alone can miss boundary failures, so retain extremes and equal values.
Follow-up questions
- Create a nontransitive cyclic order for three named values and make the triple checks fail. Hint: a compares before b, b before c and c before a cannot form an ordinary total order.
- What fails if a key used by an ordered collection mutates after insertion?
Self-review
Choose what to revisit. These marks are your own assessment and are separate from lesson completion.