Skip to content
Hari KharelStudy

Class design and invariants

coreCommon atAnthropicStripeOpenAIGoogleAmazonRead firstHash mapsComplexity analysisPractise in the Sandbox →

Design a stateful class in three moves. List the operations and how fast each must be. Choose the representation (the private fields) that makes each one cheap; usually a primary map plus a few derived maps or counters. Write the invariants: the facts about those fields that must hold after every public call. Then make every method validate first, mutate second, and keep fields private so nothing else can break the invariants. That discipline is what makes level 2, 3 and 4 additions cheap instead of a rewrite.

The idea in plain words

Section titled “The idea in plain words”

A practical-coding round hands you a class with a few methods, then grows it: level 2 adds a query, level 3 adds time, level 4 adds backup or history. The code you write in the first 15 minutes either absorbs those changes or fights them.

Three ideas carry most of the weight:

  • Representation follows operations. Don’t start from “what is a library?” Start from “what must a library answer, and how fast?” If is a copy free? must be O(1), you need a count of copies and a count on loan, not a list you scan.
  • Invariants are the rules your fields obey between calls: “on-loan never exceeds copies”, “the index holds exactly the live ids”. Write them as a comment at the top of the class. They are your spec, your test oracle, and your debugging checklist.
  • Encapsulation means only the class’s own methods touch its fields. Then there are only a handful of places that can break an invariant, and you can check each one.

When two fields describe the same fact (a set of loans and a count of loans), they will drift apart the first time one method forgets to update both. Either update both in one place every time, or derive one from the other.

See it

Section titled “See it”

Check out and return books, add and remove copies. In validates first mode, illegal calls are rejected and all three invariants stay green. Switch to sloppy: it skips checks and forgets to decrement one counter. Try to break each invariant, and notice that the operation that breaks it is not the one where you’d see the wrong answer.

A library class and its invariants
sandbox

copies / on_loan (per book)

bookcopieson_loanfree
Dune202
Emma101
Ulysses101

loans (per member)

ana–ben–cy–

invariants, re-checked after every operation

✓ I10 ≤ on_loan[b] ≤ copies[b] for every book
✓ I2on_loan[b] = number of members holding b
✓ I3every member holds at most 2 books, no duplicates
Each method validates before it mutates, so a rejected call leaves every field unchanged and all three invariants hold after every operation. Switch to sloppy to see what that buys you.
invariant holdsinvariant brokenselected
Check out and return books. Try to break an invariant in each implementation.

When to reach for it

Section titled “When to reach for it”
The problem says… What it’s really asking
“implement class X with methods a, b, c” Pick fields so each method is cheap; list invariants.
“return False (or None) and change nothing if…” Validate every precondition before the first mutation.
“should not scan every…” / “aim for O(1) / O(log n)” Add a derived structure (index, counter, heap) and keep it in sync.
“Level 2 / 3 / 4” Expect new fields. Keep each concept in one place so additions don’t ripple.
“ids are "T-1", "T-2"…, never reused” A counter field that only ever increments: an invariant.
“sorted by X, then by Y” A tie-break rule. Encode it once, in one key function.

How it works

Section titled “How it works”
  1. List the operations with target costs. Write them in a comment: checkout O(1), holdings(member) O(k), free(book) O(1).
  2. Pick the primary representation: usually id → record in a hash map. That’s the source of truth.
  3. Add derived structures only for operations that need them: a counter, a reverse map, an index, a heap. Each one is a new invariant to maintain.
  4. Write the invariants at the top of the class. Each derived structure gets one (“on_loan[b] equals the number of members holding b”).
  5. Validate, then mutate. Every public method checks all its preconditions first; only then does it change fields, and it changes all related fields together.
  6. Write a _check() method that asserts every invariant by recomputing from the primary data. Call it after every operation in your tests. It finds bugs at the line that caused them.
library.py
class Library:
    """Invariants (checked by _check after every public call in tests):
    I1  0 <= on_loan[b] <= copies[b]
    I2  on_loan[b] == number of members holding b
    I3  each member holds at most `limit` distinct books
    """


    def __init__(self, limit: int = 2) -> None:
        self._limit = limit
        self._copies: dict[str, int] = {}  # 1. representation chosen from the operations:
        self._on_loan: dict[str, int] = {}  #    "is a copy free?" must be O(1)
        self._loans: dict[str, set[str]] = {}  #    "what does m hold?" must be O(1)


    def add_copy(self, book: str) -> None:
        self._copies[book] = self._copies.get(book, 0) + 1
        self._on_loan.setdefault(book, 0)


    def checkout(self, member: str, book: str) -> bool:
        held = self._loans.get(member, set())
        if book in held or len(held) >= self._limit:  # 2. validate everything first...
            return False
        if self._on_loan.get(book, 0) >= self._copies.get(book, 0):
            return False
        self._loans.setdefault(member, set()).add(book)  # 3. ...then mutate every field together
        self._on_loan[book] += 1
        return True


    def give_back(self, member: str, book: str) -> bool:
        held = self._loans.get(member)
        if not held or book not in held:
            return False
        held.remove(book)
        self._on_loan[book] -= 1  # 4. two fields describe one fact: update both, here, always
        return True


    def _check(self) -> None:
        for b, n in self._on_loan.items():
            assert 0 <= n <= self._copies[b], f"I1 broken for {b}"
            assert n == sum(b in h for h in self._loans.values()), f"I2 broken for {b}"
        assert all(len(h) <= self._limit for h in self._loans.values()), "I3 broken"




if __name__ == "__main__":
    lib = Library(limit=2)
    lib.add_copy("Dune")
    assert lib.checkout("ana", "Dune") and not lib.checkout("ben", "Dune")  # no free copy
    lib._check()
    assert lib.give_back("ana", "Dune") and lib.checkout("ben", "Dune")
    assert not lib.give_back("ana", "Dune")  # ana no longer holds it
    lib._check()
    print("ok")

Small immutable values

Section titled “Small immutable values”

Not every class is a store. Small value objects (a date range, a money amount, a coordinate) are best made immutable, with the invariant checked once in the constructor. Every instance that exists is valid, forever, and methods return new instances instead of changing fields.

date_range.py
from dataclasses import dataclass
from datetime import date, timedelta




@dataclass(frozen=True)  # 1. immutable: once valid, always valid
class DateRange:
    """Half-open [start, end). The invariant start <= end is enforced at construction."""


    start: date
    end: date


    def __post_init__(self) -> None:
        if self.start > self.end:  # 2. the only door in checks the invariant
            raise ValueError(f"start {self.start} is after end {self.end}")


    @property
    def days(self) -> int:
        return (self.end - self.start).days


    def overlaps(self, other: "DateRange") -> bool:
        return self.start < other.end and other.start < self.end  # 3. methods may rely on it


    def shifted(self, days: int) -> "DateRange":
        d = timedelta(days=days)
        return DateRange(self.start + d, self.end + d)  # 4. "changes" return new valid values




if __name__ == "__main__":
    a = DateRange(date(2026, 3, 1), date(2026, 3, 5))
    b = DateRange(date(2026, 3, 5), date(2026, 3, 9))
    assert a.days == 4 and not a.overlaps(b)  # touching ends don't overlap
    assert a.shifted(2).overlaps(b)
    try:
        DateRange(date(2026, 3, 9), date(2026, 3, 1))
        raise AssertionError("expected ValueError")
    except ValueError:
        pass
    print("ok")

What it costs

Section titled “What it costs”

The trade-off in class design is read speed vs write cost vs bug surface:

Representation for “free copies of a book” free(book) checkout / return Invariants to maintain
Only a list of loans; count on demand O(loans) O(1) none beyond the list
Loans + an on_loan counter per book O(1) O(1), two fields on_loan matches the loans
Loans + counter + per-member sets O(1) O(1), three fields two cross-structure invariants

Each derived field turns an O(n) read into O(1) and adds one place where writes can go wrong. Add them when an operation’s target cost demands it, not “just in case”. And when the interviewer asks for the complexity of each method, answer per method, including the write cost of keeping derived data current.

Variations you’ll meet

Section titled “Variations you’ll meet”
  • Ids and counters. “Ids are T-1, T-2… and never reused” is a monotonic counter; deleting must not decrement it.
  • Soft delete. Keep the record with a deleted flag (or a tombstone) when history or id reuse rules require it. Every query must then skip deleted records: another invariant.
  • Derived vs stored. A user’s total can be computed from their transactions each time (always correct, O(n)) or stored and updated (O(1), can drift). Interviewers love asking which you chose and why.
  • Time as an input. Methods that take ts let the class compute “expired” or “overdue” lazily. See TTL and expiry.
  • Lifecycle fields. A status that moves through fixed stages is a state machine. Use an enum, not several booleans.
  • Design by contract. Bertrand Meyer’s term for preconditions (what a caller must ensure), postconditions (what the method guarantees) and class invariants (what holds between calls).

Pitfalls

Section titled “Pitfalls”
  • Mutate, then validate. Half the fields change, then a check fails and the method returns False. The object is now inconsistent. Always check everything first.
  • Two sources of truth. A list and a count, a map and a reverse map. Update both in the same method, every time, or derive one.
  • Leaking internals. get_items() returns the internal list; the caller sorts it in place and your order invariant is gone.
  • Mutable keys. Using a list or a mutable object as a dict key (or in a set), then changing it. The entry becomes unreachable.
  • Constructors that skip validation. Python’s dataclasses.replace, C#’s with expressions on records (they copy fields, then run only init setters, not the constructor body) and default(T) for structs can all create objects that never went through your check.
  • Order-dependent output from a hash map. Python and JS maps keep insertion order; C# Dictionary doesn’t promise any order. Sort explicitly whenever the spec says “sorted”.

In the interview

Section titled “In the interview”
  • Before coding, say the operations and the target costs, then: “So I’ll store a map from id to record, plus a counter per book so free is O(1).”
  • State the invariants out loud and write them as a comment. It takes 30 seconds and interviewers notice.
  • Ask about the edges of each method: “What should checkout return if the member doesn’t exist? Is that an error or False?” (see API design).
  • After each level, re-read your invariants: does the new feature add a field? Does any existing method now need to update it?
  • Test with a _check() after every call. Mention it even if you run out of time to write it.

Check yourself

Section titled “Check yourself”
Check yourself
pick one
checkout(member, book) increments on_loan[book], then discovers the member is over their limit and returns False. What's wrong?
Check yourself
pick one
A class keeps both items: list[Item] and count: int. Which change removes a whole class of bugs?
Check yourself
pick one
get_members() returns self._members (the internal list). A caller does .sort(key=age). What happens?

Practice on your own

Section titled “Practice on your own”

These are classic exercises, not gym questions:

  • A parking garage with spots of three sizes: park, leave, free spots per size in O(1). Write the invariants first.
  • An inventory of products with stock levels and reservations: reserve, release, ship. What must always hold between stock and reserved?
  • A course enrolment system with capacity and waitlists: enrol, drop (promotes from the waitlist), list.
  • An immutable Fraction value type that is always stored in lowest terms with a positive denominator.

Go deeper

Section titled “Go deeper”
  • Bertrand Meyer, Object-Oriented Software Construction, 2nd ed. (1997): design by contract and class invariants.
  • Joshua Bloch, Effective Java, 3rd ed.: “Minimize mutability” and “Make defensive copies when needed” apply in every language.
  • Python docs, dataclasses (frozen=True, __post_init__); MDN, private class features.
  • Microsoft Learn, Records: value equality, immutability and with expressions.
Section titled “Related”
API design and evolutionWhat the class looks like from outside.
Designing for the next requirementRepresentation choices that survive level 3.
Secondary indexesDerived structures kept in sync.
State machinesLifecycles as one field, not many booleans.