Object-oriented design

Build a class that survives new requirements: clear state, rules checked in one place, one method per operation.

what

Write down the state first, guard its invariants in one helper, and give each operation its own small method that validates first and changes state last.

use when

A multi-level OA or design round: a game, a shop, a bank, a booking system, where each level adds rules to the class you already wrote.

time

O(1) to O(log n) per call

space

O(n)

You’ll recognise it when

The task is a small world to model: a library, a parking garage, a card game, a task manager, a shop’s stock.
You get a class name and a list of methods, and the tests call them in sequences.
The problem comes in levels, and each level adds rules or methods to the class you already wrote.
Methods return False or None for a request that breaks a rule, instead of crashing.
There’s a query at the end that lists or ranks things, with a tie-break spelled out.

It’s often confused with a pure algorithm question. Here the hard part is rarely the algorithm. It’s keeping the state correct while the rules keep changing.

Think of a small shop’s ledger. Every page has the same columns, and the owner follows a few rules: never sell stock you don’t have, write every sale down. A new rule (“no more than 3 per customer”) adds one line to the rulebook. It doesn’t mean rewriting the ledger.

A design round tests the same thing. You pick the state (the ledger’s columns), you write down the invariants (the rules that must hold after every call), and you give each operation one method that checks the rules and then changes the state. Two habits make later levels cheap: keep every rule in one place, and pick a data model that can answer the questions you’ll probably be asked next (who holds what, in what order, since when).

How it works

Here’s a lending desk for a small library, built the way a four-level OA grows it. Each level only adds code.

Level 1: copies, borrow, return. Before writing methods, write the state. copies[book] is how many copies the library owns. A plain count of copies on the shelf would be enough for level 1, but it can’t say who has a book. So store loans[book], the set of members holding one, plus held[member] for the other direction. The invariant: len(loans[book]) <= copies[book], and nobody holds two copies of one book.
One method per operation, validate first. borrow asks a helper, _can_take, whether the request is allowed. Only after a yes does it touch any state. A failed call changes nothing, so you never need to undo half an update.
Level 2: a per-member limit. A member may hold at most limit books. That’s one new line in _can_take. Because every rule lives there, borrow itself doesn’t change.
Level 3: a waitlist. Members can queue for a book. When copies come back, people already waiting get them first. In _can_take, count how many waiting members are ahead of this one: the request is allowed only if fewer than the number of free copies are ahead. Someone not on the list counts as behind everyone on it.
Level 4: a ranking. most_lent(k) lists the most borrowed books. It needs one new counter, updated in borrow, and a sort key with an explicit tie-break: most loans first, then by title.

Walk through it with limit = 2, one copy of dune and two of emma:

call	result	why
`borrow(ann, dune)`	true	one free copy, nobody waiting
`borrow(bo, dune)`	false	no free copy
`join_waitlist(bo, dune)`, then `(cy, dune)`	true, true	the `waitlist` is `[bo, cy]`
`give_back(ann, dune)`	true	one free copy again
`borrow(cy, dune)`	false	bo is ahead of cy, and only one copy is free
`borrow(bo, dune)`	true	first in line; bo leaves the `waitlist`
`borrow(bo, emma)`, `borrow(bo, heidi)`	true, false	the library has no `heidi`
`most_lent(5)`	`dune:2 emma:1`	`dune` was lent twice

Why it stays correct: the only methods that change loans are borrow and give_back, and borrow only does so after _can_take has checked every rule. So the invariants hold after every call, whatever order the tests use.

class Library:
    def __init__(self, limit):
        self.limit = limit            # most books one member may hold at once
        self.copies = {}              # book -> copies the library owns
        self.loans = {}               # book -> members holding a copy
        self.held = {}                # member -> books they hold
        self.waitlist = {}            # book -> waiting members, oldest first
        self.times_lent = {}          # book -> successful borrows so far

    # Level 1: one method per operation
    def add_copies(self, book, n):
        if book not in self.copies:
            self.copies[book] = 0
            self.loans[book] = set()
            self.waitlist[book] = []
            self.times_lent[book] = 0
        self.copies[book] += n
        return self.copies[book]

    def borrow(self, member, book):
        if not self._can_take(member, book):   # validate first...
            return False
        self.loans[book].add(member)           # ...then change state
        self.held.setdefault(member, set()).add(book)
        if member in self.waitlist[book]:
            self.waitlist[book].remove(member)
        self.times_lent[book] += 1
        return True

    def give_back(self, member, book):
        if member not in self.loans.get(book, ()):
            return False
        self.loans[book].remove(member)
        self.held[member].remove(book)
        return True

    # Level 3: a waitlist per book
    def join_waitlist(self, member, book):
        if book not in self.copies:
            return False
        if member in self.loans[book] or member in self.waitlist[book]:
            return False
        self.waitlist[book].append(member)
        return True

    def books_of(self, member):
        return sorted(self.held.get(member, ()))

    # Level 4: a ranking with an explicit tie-break
    def most_lent(self, k):
        ranked = sorted(self.times_lent.items(), key=lambda kv: (-kv[1], kv[0]))
        return [(book, n) for book, n in ranked if n > 0][:k]

    # Every borrowing rule lives here, so each level edits one place.
    def _can_take(self, member, book):
        if book not in self.copies or member in self.loans[book]:
            return False
        if len(self.held.get(member, ())) >= self.limit:       # level 2
            return False
        free = self.copies[book] - len(self.loans[book])
        queue = self.waitlist[book]                             # level 3
        ahead = queue.index(member) if member in queue else len(queue)
        return ahead < free

#include <algorithm>
#include <map>
#include <set>
#include <string>
#include <vector>
using namespace std;

class Library {
    int limit;                              // most books one member may hold at once
    map<string, int> copies;                // book -> copies the library owns
    map<string, set<string>> loans;         // book -> members holding a copy
    map<string, set<string>> held;          // member -> books they hold
    map<string, vector<string>> waitlist;   // book -> waiting members, oldest first
    map<string, int> times_lent;            // book -> successful borrows so far

public:
    explicit Library(int limit) : limit(limit) {}

    // Level 1: one method per operation
    int add_copies(const string& book, int n) {
        if (!copies.count(book)) {
            copies[book] = 0;
            loans[book];
            waitlist[book];
            times_lent[book] = 0;
        }
        return copies[book] += n;
    }

    bool borrow(const string& member, const string& book) {
        if (!can_take(member, book)) return false;   // validate first...
        loans[book].insert(member);                  // ...then change state
        held[member].insert(book);
        auto& queue = waitlist[book];
        queue.erase(remove(queue.begin(), queue.end(), member), queue.end());
        times_lent[book]++;
        return true;
    }

    bool give_back(const string& member, const string& book) {
        auto it = loans.find(book);
        if (it == loans.end() || !it->second.count(member)) return false;
        it->second.erase(member);
        held[member].erase(book);
        return true;
    }

    // Level 3: a waitlist per book
    bool join_waitlist(const string& member, const string& book) {
        if (!copies.count(book)) return false;
        auto& queue = waitlist[book];
        if (loans[book].count(member) || find(queue.begin(), queue.end(), member) != queue.end())
            return false;
        queue.push_back(member);
        return true;
    }

    vector<string> books_of(const string& member) {
        auto it = held.find(member);
        if (it == held.end()) return {};
        return vector<string>(it->second.begin(), it->second.end());   // a set is already sorted
    }

    // Level 4: a ranking with an explicit tie-break
    vector<pair<string, int>> most_lent(int k) {
        vector<pair<string, int>> ranked;
        for (auto& [book, n] : times_lent)
            if (n > 0) ranked.push_back({book, n});
        sort(ranked.begin(), ranked.end(), [](auto& a, auto& b) {
            return a.second != b.second ? a.second > b.second : a.first < b.first;
        });
        if ((int)ranked.size() > k) ranked.resize(k);
        return ranked;
    }

private:
    // Every borrowing rule lives here, so each level edits one place.
    bool can_take(const string& member, const string& book) {
        if (!copies.count(book) || loans[book].count(member)) return false;
        if ((int)held[member].size() >= limit) return false;            // level 2
        int free_copies = copies[book] - (int)loans[book].size();
        auto& queue = waitlist[book];                                    // level 3
        int ahead = find(queue.begin(), queue.end(), member) - queue.begin();
        return ahead < free_copies;
    }
};

import java.util.*;

class Library {
    private final int limit;                                     // most books one member may hold at once
    private final Map<String, Integer> copies = new HashMap<>(); // book -> copies the library owns
    private final Map<String, Set<String>> loans = new HashMap<>();      // book -> members holding a copy
    private final Map<String, Set<String>> held = new HashMap<>();       // member -> books they hold
    private final Map<String, List<String>> waitlist = new HashMap<>();  // book -> waiting members, oldest first
    private final Map<String, Integer> timesLent = new HashMap<>();      // book -> successful borrows so far

    Library(int limit) { this.limit = limit; }

    // Level 1: one method per operation
    int addCopies(String book, int n) {
        if (!copies.containsKey(book)) {
            copies.put(book, 0);
            loans.put(book, new HashSet<>());
            waitlist.put(book, new ArrayList<>());
            timesLent.put(book, 0);
        }
        copies.merge(book, n, Integer::sum);
        return copies.get(book);
    }

    boolean borrow(String member, String book) {
        if (!canTake(member, book)) return false;     // validate first...
        loans.get(book).add(member);                  // ...then change state
        held.computeIfAbsent(member, m -> new TreeSet<>()).add(book);
        waitlist.get(book).remove(member);
        timesLent.merge(book, 1, Integer::sum);
        return true;
    }

    boolean giveBack(String member, String book) {
        Set<String> holders = loans.get(book);
        if (holders == null || !holders.remove(member)) return false;
        held.get(member).remove(book);
        return true;
    }

    // Level 3: a waitlist per book
    boolean joinWaitlist(String member, String book) {
        if (!copies.containsKey(book)) return false;
        List<String> queue = waitlist.get(book);
        if (loans.get(book).contains(member) || queue.contains(member)) return false;
        queue.add(member);
        return true;
    }

    List<String> booksOf(String member) {
        return new ArrayList<>(held.getOrDefault(member, new TreeSet<>()));   // a TreeSet is already sorted
    }

    // Level 4: a ranking with an explicit tie-break
    List<Map.Entry<String, Integer>> mostLent(int k) {
        List<Map.Entry<String, Integer>> ranked = new ArrayList<>();
        for (Map.Entry<String, Integer> e : timesLent.entrySet())
            if (e.getValue() > 0) ranked.add(e);
        ranked.sort((a, b) -> !a.getValue().equals(b.getValue())
                ? b.getValue() - a.getValue() : a.getKey().compareTo(b.getKey()));
        return ranked.subList(0, Math.min(k, ranked.size()));
    }

    // Every borrowing rule lives here, so each level edits one place.
    private boolean canTake(String member, String book) {
        if (!copies.containsKey(book) || loans.get(book).contains(member)) return false;
        if (held.getOrDefault(member, Set.of()).size() >= limit) return false;   // level 2
        int free = copies.get(book) - loans.get(book).size();
        List<String> queue = waitlist.get(book);                                 // level 3
        int ahead = queue.contains(member) ? queue.indexOf(member) : queue.size();
        return ahead < free;
    }
}

The code keeps the two directions of the loans (loans by book, held by member) in step inside the same two methods. Duplicated state is fine when it makes a query fast, as long as exactly one place updates both copies.

How OA levels grow, and models that stretch

Multi-level OAs show you one level at a time, and the later tests call earlier methods too. Some extensions come up again and again, so it pays to leave room for them on level 1:

later level asks for	model that stretches
“who has X”, “list Y’s items”	maps in both directions, not a bare count
“as of time t”, “history of X”	an append-only list of `(time, value)` per key
“in the order they arrived”	a queue, or a sequence number on every record
“top k by …”	a counter per key, sorted with an explicit tie-break key
new kinds of things (refund, tip)	a `handlers[kind]` table or a small class per kind
timers that fire later	a heap of `(due_time, seq, event)` drained at the start of every call

Write the obvious level 1 quickly and pass it: early levels are where you bank time. But choose its data model with this table in mind, and keep the rule checks in one helper.

What each call costs

With hash maps, borrow, give_back and add_copies take O(1) on average, plus the waitlist scan, which is O(w) for w waiting members. That’s fine at OA sizes. If waitlists could be long, keep a position index per member alongside the queue. books_of sorts the member’s books, O(b log b). most_lent sorts every title, O(n log n); a heap gives O(n log k) when k is small.

Space is O(books + loans + waiting members). In OA rounds the tests are small, so correctness and clear code matter far more than shaving constants. Mention the cheaper structure out loud and move on.

Common mistakes

Changing state before every check passes

If borrow adds the loan and then finds the member is over their limit, it has to undo the change, and the undo is easy to get wrong.

self.loans[book].add(member)               # ✗ changed first
if len(self.held[member]) > self.limit: ...
if not self._can_take(member, book):       # ✓ check everything first
    return False

Copying a rule into every method

Level 2’s limit check pasted into borrow, renew and transfer means level 3 must find and edit all three. Miss one and a test fails far from the cause.

if len(self.held[m]) >= self.limit: ...    # ✗ the same rule in three methods
if not self._can_take(m, book): ...        # ✓ one helper owns every rule

A data model that only answers level 1

A single number of free copies passes level 1, then can’t say who holds a book or who returned it. Rebuilding the model under time pressure on level 3 is how OAs run out of time.

self.free[book] -= 1                       # ✗ a count forgets who
self.loans[book].add(member)               # ✓ keeps who, so later levels can ask

Leaving ties to chance

“Most borrowed first” with no tie-break gives an order that depends on insertion order or hashing. The tests expect the tie-break in the statement, usually by name or id.

sorted(items, key=lambda kv: -kv[1])          # ✗ equal counts in any order
sorted(items, key=lambda kv: (-kv[1], kv[0]))  # ✓ count, then title

Variations

Refactor rounds. You get working but messy code. Pin the current behaviour with a few tests first, then extract helpers, remove duplication and replace flag arguments, running the tests after each step.
Strategies and registries. When levels add new kinds of things (a new card rule, a new payment type), map each kind to a function or small class: handlers[kind](state, event). A new kind then adds a line instead of another elif.
History and time travel. Store an append-only list of (time, value) per key and answer “as of time t” with a binary search. The time-travel key-value store guide covers it.
Timed events. Holds that expire, payments that land later: keep a heap of (due_time, seq, event) and process everything due at the start of each call. The bank system guide shows it.
Value objects. Small records like a card or a move are easiest as frozen dataclasses (@dataclass(frozen=True)): they compare by value and can be dict keys.

Climb the ladder

Our oop-design problems in ladder order. The first two are warm-ups; from the note-taking system on, they’re multi-level OAs.

A bank account class with invariants: validate first, mutate last.
Greenhouse watering rota: one class, clear state, simple queries.
Note-taking system with timestamps and search: ids, timestamps and a ranked query with tie-breaks.
Food delivery system: a second level that changes data you already store.
Monster team battle: a turn-based rule engine that grows types, then strategy.
Retriable function: pluggable backoff strategies and hooks.
Parking garage with fees and reservations: resources, fees, then reservations that run out.
File finder with saved, combinable search rules: filters as objects that combine.

After those, the rest of the topic goes harder in the same order: card games, circuit breakers, a follow graph with snapshots, a recipe manager with versions, a task manager with quotas and history, and a text editor with undo. See all oop-design problems.

Check yourself

5 quick questions. Pick an answer to see why it's right or wrong.

1
Level 1 of a parking garage OA only asks park(plate) and leave(plate), returning whether they worked. You know later levels exist but can’t see them yet. Which state is the safest start?
Later levels nearly always ask who is where: fees per car, “find my car”, reservations. A map from spot to plate answers level 1 and those questions. A count or a boolean array passes level 1 but forgets which car is in which spot, so a later level forces a rewrite under time pressure.

What does this print?

class Wallet:
    def __init__(self):
        self.balance = 10
        self.log = []

    def spend(self, amount):
        self.log.append(amount)
        if amount > self.balance:
            raise ValueError("too much")
        self.balance -= amount

w = Wallet()
for a in [4, 9, 3]:
    try:
        w.spend(a)
    except ValueError:
        pass
print(w.balance, w.log)

3
A level asks for the three most borrowed books, most loans first, ties by title. What does this print?
```
counts = {"emma": 2, "dune": 3, "anna": 2, "cats": 1}
ranked = sorted(counts.items(), key=lambda kv: (-kv[1], kv[0]))
print([book for book, n in ranked][:3])
```
The key sorts by -count first, so 3 comes before 2, then by title among equal counts, so anna comes before emma. Without the second part of the key, emma would come first only because it was inserted first, which is the kind of accident tests catch.
4
Level 3 adds a rule: a member with an overdue book can’t take another. Your borrow, renew and reserve methods each check the earlier rules inline. What’s the most robust change?
Rules copied into several methods drift apart: the next level edits two copies and forgets the third. One helper that owns every rule means each new level edits one place. A subclass or a global flag changes who the rule applies to, and checking borrow alone leaves renew as a way around it.
5
You suspect a later OA level will ask for a key’s value “as of time t”. Which level-1 storage makes that level easiest?
An append-only list per key keeps every version in time order, so “as of t” is a binary search for the last write at or before t, and “latest” is the last element. Keeping only the latest value loses the past. A full snapshot per write also works, but costs O(n) memory per write.

Practice problems

Solve these right here, in Python, C++ or Java. Tests run as you go.

All 31 problems on this topic