Coding Interview Patterns Module 29 – Design-a-data-structure problems
Design-a-data-structure problems: a method
How to solve design-a-data-structure problems: a cost for every operation, combined structures, an invariant, and tests that replay sequences of calls.
What you will learn
- Write the API and a target cost for every operation before choosing any structure
- Combine two structures, such as flags and a stack, so that every operation meets its cost
- State the invariant that keeps the structures in agreement, and check it in tests
- Test a design with sequences of calls, replayed and checked against a model
- Change the structures when a cost target changes, such as a heap for the lowest free number
Before you start
What you’ll learn · Before you start
What you will learn
- Write the API and a target cost for every operation before choosing any structure
- Combine two structures, such as flags and a stack, so that every operation meets its cost
- State the invariant that keeps the structures in agreement, and check it in tests
- Test a design with sequences of calls, replayed and checked against a model
- Change the structures when a cost target changes, such as a heap for the lowest free number
Before you start
On this page
A design-a-data-structure problem asks for a class instead of a function. The statement lists its methods, such as
put, get and remove, and often the cost each one must meet; a test then creates one object and calls its
methods thousands of times in a row. Four steps solve most of these problems. Write the API with a target cost for
every operation. Give each operation a structure that answers it quickly, and combine two structures when no single
one meets every cost. Write down the invariant that keeps the structures in agreement. Then test with sequences of
calls, and check every answer against a slow model that is plainly right.
This lesson explains the four steps and then solves one problem in full: a pool of lockers that hands out any free locker in O(1), from the brute force to code in five languages, a bug that only a repeated call exposes, and random tests that shrink that bug to two calls. The rest of this module uses the same steps for caches, sets with random picks, queues made of stacks, versioned stores, iterators and frequency counters.
What a design problem gives you
The statement has three parts. The API is a class with a constructor and a few methods, each with the value it returns. The costs are either stated outright, as in “each call in O(1) on average”, or implied by the limits, as in “n ≤ 10⁵ and at most 2 × 10⁵ calls”. The examples are written as sequences of calls, with the answer of every call.
A test is the same kind of sequence, only longer. The grader creates a fresh object, makes the calls in order and compares every answer, so a method’s cost is paid once per call. A method that takes O(n) time on 10⁵ items, called 2 × 10⁵ times, costs about 2 × 10¹⁰ steps, far beyond the budgets of the lesson on reading constraints. The object’s state also carries over from call to call, which is where these problems hide their bugs: a method can be right on a fresh object and wrong after one particular earlier call.
The words that point to the pattern are “design”, “implement the class”, “each call”, “on average”, “amortised”, and a limit on the number of calls rather than on the size of one input. These problems are not low-level design rounds. Those, covered in the low-level design track, judge classes, responsibilities and how easily a design can be extended. Here the class is small and fixed, and what counts is that every call meets its cost and every answer is right after any sequence of calls. The structures themselves, arrays, hash maps, linked lists and heaps, are the subject of the DSA track; this module is about combining them.
The four steps
The four steps of a design problem, and the way back
Text description of the diagram
The diagram shows four steps from top to bottom.
- The API and its costs: every method, what it answers in the edge cases, and the cost it must meet.
- The structures: one for each need, combined when no single structure meets every cost.
- The invariant: how the structures agree, a statement that every method keeps true.
- Operation-sequence tests: sequences of calls replayed on a fresh object, with every answer checked against a model.
One arrow leads back from step 4 to step 2: a wrong answer, or a cost the design does not meet, means changing the structures, and then the invariant and the tests with them.
- The API and its costs. Write every method down with its answer in each edge case the statement allows: an empty structure, a missing key, a repeated call, a call that changes nothing. Then write the cost each method must meet, taken from the statement or from the limits. With up to 2 × 10⁵ calls, O(log n) per call is safe and O(n) per call is not.
- The structures. For each operation, ask which structure answers it quickly: an array by position, a hash map by key, a stack or a queue at its ends, a heap for the smallest item, a linked list for unlinking a node you already hold. When no single structure meets every cost, keep two, and let each operation use the one it needs.
- The invariant. Two structures that describe the same items must agree after every call. Write one sentence that says how they agree, and check every method against it: whatever a method changes, it must change in both.
- Operation-sequence tests. Replay sequences of calls on a fresh object and check every answer. Write the short sequences of the statement by hand, then generate thousands of random ones on a tiny size, and judge them with a model: a slow class that is plainly right.
A problem solved in full: lockers at a station
The problem
A station’s left-luggage room has n lockers, numbered 0 to n − 1, all free when it opens. Write a class
LockerPool(n) with four methods. rent() rents out any free locker and returns its number, or returns −1 when
every locker is rented. give_back(k) frees locker k and returns true, or returns false and changes nothing when
k is already free. is_free(k) says whether locker k is free, and free_count() returns how many lockers are
free. Every k is a number from 0 to n − 1. Limits: 1 ≤ n ≤ 100,000, and a test makes up to 200,000 calls. Every
call must take O(1) time.
Two examples, written as tests are written: the operations, their arguments, and one correct list of answers, with
null as the constructor’s answer. Because rent() may return any free locker, another correct pool may rent other
lockers.
LockerPool(3), thenrent(),rent(),give_back(0),give_back(0),is_free(0),rent(),free_count(),rent(),rent(), gives[null, 0, 1, true, false, true, 0, 1, 2, -1]. The secondgive_back(0)returns false because locker 0 is already free, and the lastrent()returns −1 because all three lockers are rented.LockerPool(1), thenis_free(0),rent(),rent(),is_free(0),give_back(0),free_count(), gives[null, true, 0, -1, false, true, 1].
Step 1: the API and its costs
The statement already settles the questions that change the code. rent() returns −1 when nothing is free;
give_back(k) on a free locker returns false and changes nothing; every k is valid, so no method checks its range.
If a statement left one of these open, you would ask, because each answer becomes a line of a test. The costs are
given as well: O(1) for all four methods. That is the contract the design has to meet.
The brute force: flags alone
The simplest correct pool keeps one flag per locker, rented[k], and a count of free lockers. is_free,
give_back and free_count are then O(1), but rent() has to search the flags for a free locker, which takes up
to n steps. The worst test fills the pool and then keeps giving back and renting the last locker, so that every
rent() reads all n flags. Here are the flags read on that test for growing n:
"""The brute force keeps only the flags, so rent() searches them for a free locker. Count the flags it reads."""
from locker_pool import LockerPool
class ScanPool:
def __init__(self, n):
self.rented = [False] * n
self.free = n
self.reads = 0 # flags read by rent(), to measure its work
def rent(self):
for k, taken in enumerate(self.rented):
self.reads += 1
if not taken:
self.rented[k] = True
self.free -= 1
return k
return -1
def give_back(self, k):
if not self.rented[k]:
return False
self.rented[k] = False
self.free += 1
return True
def is_free(self, k):
return not self.rented[k]
def free_count(self):
return self.free
def worst_case(n):
"""Rent every locker, then n / 2 times give the last one back and rent again: 2n calls in all."""
return [("rent",)] * n + [("give_back", n - 1), ("rent",)] * (n // 2)
print(f"{'n':>8}{'calls':>9}{'flags read':>16}{'per call':>10}")
for n in (250, 500, 1000, 2000):
calls = worst_case(n)
scan, pool = ScanPool(n), LockerPool(n)
for op, *args in calls:
assert getattr(scan, op)(*args) == getattr(pool, op)(*args)
print(f"{n:>8,}{len(calls):>9,}{scan.reads:>16,}{scan.reads // len(calls):>10,}")
print("ScanPool and LockerPool gave the same answers to every call")
n = 100_000
reads = n * (n + 1) // 2 + (n // 2) * n # the same count, from the formula
print(f"{n:>8,}{2 * n:>9,}{reads:>16,}{reads // (2 * n):>10,} (from the formula)")Output
n calls flags read per call
250 500 62,625 125
500 1,000 250,250 250
1,000 2,000 1,000,500 500
2,000 4,000 4,001,000 1,000
ScanPool and LockerPool gave the same answers to every call
100,000 200,000 10,000,050,000 50,000 (from the formula)
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 scan_cost.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Each doubling of n doubles the calls and multiplies the flags read by four. On this test the brute force reads
about n / 2 flags per call, n² in all, so at the full limits it reads 10,000,050,000 flags for 200,000 calls: about
1,000 seconds of CPython at the ten million simple steps a second that the constraints lesson plans with. Its
answers are right, though, which keeps it useful. The same program checks that the design below, LockerPool, gives
the same answer as the brute force on every call of these tests.
What to notice
rent() does not need a particular locker, only some free one, and no order among the free lockers matters. So
the free lockers can sit in any container that hands one out in O(1), and a stack, where the last item in is the
first out, is the simplest. is_free(k) needs the opposite: a lookup by number, which the flags already give.
Each operation has a structure that answers it in O(1), and neither structure answers both.
Step 2: flags and a stack
Keep both: the flags rented[k] from the brute force, and a stack holding the numbers of the free lockers. Each
method reads the structure that answers it and changes both when it changes the state, and each takes O(1) time:
rent()pops the top of the stack and sets that locker’s flag, or returns −1 when the stack is empty.give_back(k)reads flag k and, if it says rented, clears it and pushes k.is_free(k)reads flag k.free_count()returns the length of the stack.
The two structures take O(n) memory together: n flags and at most n numbers on the stack. In Python, append and
pop at the end of a list are O(1) amortised: now and then a call resizes the list’s storage and moves every item,
a cost that the documentation spreads over the many calls around it. The Java, C++ and Go versions below reserve
room for n numbers once and never resize the stack, so their costs are O(1) in the worst case.
LockerPool(6) after four rentals and two returns: the stack and the flags agree
Text description of the diagram
The state of a pool of six lockers after rent() was called four times, which rented lockers 0, 1, 2 and 3, and then give_back(1) and give_back(3).
At the top is the stack of free lockers, from the bottom on the left to the top on the right: 5, 4, 1 and 3. Locker 3 was given back last, so it is on top and is the next one rent() hands out.
Below are the six flags, one per locker: locker 0 rented, 1 free, 2 rented, 3 free, 4 free and 5 free.
An arrow from the stack to the flags states the invariant: the stack holds exactly the lockers whose flag says free, 1, 3, 4 and 5, each of them once. rent() takes the top of the stack, give_back(k) puts a rented locker back on top, and is_free(k) reads one flag, so no call ever has to search.
Step 3: the invariant, and why every method keeps it
With two structures holding the same facts, every method must keep them in agreement, and the agreement fits in one sentence: the stack holds exactly the lockers whose flag says free, each of them once. It is true at the start, when every flag says free and the stack holds 0 to n − 1. Each method keeps it true:
rent()pops a locker and sets its flag, so one free locker leaves both structures together.give_back(k)acts only when k is rented: it clears the flag and pushes k, so one locker joins both. When k is already free, it changes nothing, and that is what keeps the words “each of them once” true.is_free(k)andfree_count()change nothing.
The invariant also proves the answers right. free_count() may return the length of the stack because the stack
holds each free locker exactly once, and rent() may hand out the top of the stack because only free lockers are
in it. It even bounds the memory: a stack without repeats never holds more than n numbers, which is why the
compiled versions below can allocate it once.
A dry run
The first example of the statement, one call per row, with the invariant asserted after every call:
"""A dry run of LockerPool: the state after every call, with the invariant checked on every row."""
from locker_pool import LockerPool
from model import invariant_holds
pool = LockerPool(3)
calls = [("rent",), ("rent",), ("give_back", 0), ("give_back", 0), ("is_free", 0), ("rent",), ("free_count",), ("rent",), ("rent",)]
print(f"{'call':<14}{'answer':<8}{'stack (top on the right)':<26}rented")
print(f"{'LockerPool(3)':<14}{'':<8}{str(pool.stack):<26}none")
for op, *args in calls:
answer = getattr(pool, op)(*args)
assert invariant_holds(pool), f"the invariant broke at {op}{tuple(args)}"
rented = " ".join(str(k) for k, taken in enumerate(pool.rented) if taken) or "none"
print(f"{op + '(' + ', '.join(map(str, args)) + ')':<14}{str(answer):<8}{str(pool.stack):<26}{rented}")
print("the invariant held after every call")Output
call answer stack (top on the right) rented LockerPool(3) [2, 1, 0] none rent() 0 [2, 1] 0 rent() 1 [2] 0 1 give_back(0) True [2, 0] 1 give_back(0) False [2, 0] 1 is_free(0) True [2, 0] 1 rent() 0 [2] 0 1 free_count() 1 [2] 0 1 rent() 2 [] 0 1 2 rent() -1 [] 0 1 2 the invariant held after every call
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 trace_pool.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The two structures change together on every row. When locker 0 is given back, it joins the stack and leaves the
rented list, and the second give_back(0) changes neither. The stack is printed with its top on the right, so the
locker given back last is the next one out: rent() hands out 0 again before it reaches 2. Had any call broken the
invariant, the assertion would have stopped the program at that call. Before you read on, work out what this short
program prints:
"""Work out what this prints before you run it: which locker is on top of the stack at each call?"""
from locker_pool import LockerPool
pool = LockerPool(2)
print([pool.rent(), pool.give_back(1), pool.give_back(0), pool.rent(), pool.free_count()])Output
[0, False, True, 0, 1]
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 predict.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The code in five languages
Each file below replays the two examples of the statement in the format tests use: a list of operation names and a list of their arguments. You can run the first two on this page; the other three were built and run by the session that follows them.
Python · pool/locker_pool.py
"""Lockers 0 to n - 1: rent any free one, give one back, ask about one, count the free ones. Every call is O(1)."""
class LockerPool:
def __init__(self, n):
self.rented = [False] * n # rented[k]: is locker k rented?
self.stack = list(range(n - 1, -1, -1)) # the free lockers; locker 0 is on top, at the end
# Invariant: the stack holds exactly the lockers k with rented[k] False, each of them once.
def rent(self):
"""Rent any free locker and return its number, or -1 when every locker is rented."""
if not self.stack:
return -1
k = self.stack.pop()
self.rented[k] = True
return k
def give_back(self, k):
"""Free locker k and return True; return False, and change nothing, if it is already free."""
if not self.rented[k]:
return False # pushing k again would put it in the stack twice
self.rented[k] = False
self.stack.append(k)
return True
def is_free(self, k):
return not self.rented[k]
def free_count(self):
return len(self.stack)
def replay(ops, args):
"""Runs one test: ops[0] creates the pool from args[0], then each method is called with its arguments."""
pool = LockerPool(*args[0])
answers = [None]
for op, a in zip(ops[1:], args[1:]):
answers.append(getattr(pool, op)(*a))
return answers
def show(answers):
"""The answers in the format of the expected outputs: null, true and false, numbers."""
words = {None: "null", True: "true", False: "false"}
return "[" + ", ".join(words[a] if a is None or isinstance(a, bool) else str(a) for a in answers) + "]"
if __name__ == "__main__":
print(show(replay(
["LockerPool", "rent", "rent", "give_back", "give_back", "is_free", "rent", "free_count", "rent", "rent"],
[[3], [], [], [0], [0], [0], [], [], [], []],
)))
print(show(replay(
["LockerPool", "is_free", "rent", "rent", "is_free", "give_back", "free_count"],
[[1], [0], [], [], [0], [0], []],
)))Output
[null, 0, 1, true, false, true, 0, 1, 2, -1] [null, true, 0, -1, false, true, 1]
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 locker_pool.py
JavaScript · pool/locker_pool.mjs
// Lockers 0 to n - 1: rent any free one, give one back, ask about one, count the free ones. Every call is O(1).
class LockerPool {
constructor(n) {
this.rented = new Array(n).fill(false); // rented[k]: is locker k rented?
this.stack = []; // the free lockers; locker 0 is on top, at the end
for (let k = n - 1; k >= 0; k--) this.stack.push(k);
// Invariant: the stack holds exactly the lockers k with rented[k] false, each of them once.
}
/** Rent any free locker and return its number, or -1 when every locker is rented. */
rent() {
if (this.stack.length === 0) return -1;
const k = this.stack.pop();
this.rented[k] = true;
return k;
}
/** Free locker k and return true; return false, and change nothing, if it is already free. */
giveBack(k) {
if (!this.rented[k]) return false; // pushing k again would put it in the stack twice
this.rented[k] = false;
this.stack.push(k);
return true;
}
isFree(k) {
return !this.rented[k];
}
freeCount() {
return this.stack.length;
}
}
// The tests name the operations as the statement does; each one maps to a method.
const METHODS = { rent: 'rent', give_back: 'giveBack', is_free: 'isFree', free_count: 'freeCount' };
/** Runs one test: ops[0] creates the pool from args[0], then each method is called with its arguments. */
function replay(ops, args) {
const pool = new LockerPool(...args[0]);
const answers = [null];
for (let i = 1; i < ops.length; i++) answers.push(pool[METHODS[ops[i]]](...args[i]));
return answers;
}
const show = (answers) => `[${answers.map((a) => (a === null ? 'null' : String(a))).join(', ')}]`;
console.log(show(replay(
['LockerPool', 'rent', 'rent', 'give_back', 'give_back', 'is_free', 'rent', 'free_count', 'rent', 'rent'],
[[3], [], [], [0], [0], [0], [], [], [], []],
)));
console.log(show(replay(
['LockerPool', 'is_free', 'rent', 'rent', 'is_free', 'give_back', 'free_count'],
[[1], [0], [], [], [0], [0], []],
)));Output
[null, 0, 1, true, false, true, 0, 1, 2, -1] [null, true, 0, -1, false, true, 1]
Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node locker_pool.mjs
Runs on this device, in your browser. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs.
Your run, in this browser
Java · compiled/LockerPool.java
import java.util.ArrayList;
import java.util.List;
// Lockers 0 to n - 1: rent any free one, give one back, ask about one, count the free ones. Every call is O(1).
public class LockerPool {
private final boolean[] rented; // rented[k]: is locker k rented? A new boolean array starts all false.
private final int[] stack; // stack[0..top) are the free lockers, never more than n of them
private int top;
// Invariant: stack[0..top) holds exactly the lockers k with rented[k] false, each of them once.
public LockerPool(int n) {
rented = new boolean[n];
stack = new int[n];
for (int i = 0; i < n; i++) stack[i] = n - 1 - i; // locker 0 is on top
top = n;
}
/** Rent any free locker and return its number, or -1 when every locker is rented. */
public int rent() {
if (top == 0) return -1;
int k = stack[--top];
rented[k] = true;
return k;
}
/** Free locker k and return true; return false, and change nothing, if it is already free. */
public boolean giveBack(int k) {
if (!rented[k]) return false; // pushing k again would put it in the stack twice
rented[k] = false;
stack[top++] = k;
return true;
}
public boolean isFree(int k) {
return !rented[k];
}
public int freeCount() {
return top;
}
/** Runs one test: ops[0] creates the pool from args[0], then each method is called with its arguments. */
static List<String> replay(String[] ops, int[][] args) {
LockerPool pool = new LockerPool(args[0][0]);
List<String> answers = new ArrayList<>(List.of("null"));
for (int i = 1; i < ops.length; i++) {
Object answer = switch (ops[i]) {
case "rent" -> pool.rent();
case "give_back" -> pool.giveBack(args[i][0]);
case "is_free" -> pool.isFree(args[i][0]);
case "free_count" -> pool.freeCount();
default -> throw new IllegalArgumentException("unknown operation " + ops[i]);
};
answers.add(String.valueOf(answer));
}
return answers;
}
public static void main(String[] args) {
System.out.println(replay(
new String[] {"LockerPool", "rent", "rent", "give_back", "give_back", "is_free", "rent", "free_count", "rent", "rent"},
new int[][] {{3}, {}, {}, {0}, {0}, {0}, {}, {}, {}, {}}));
System.out.println(replay(
new String[] {"LockerPool", "is_free", "rent", "rent", "is_free", "give_back", "free_count"},
new int[][] {{1}, {0}, {}, {}, {0}, {0}, {}}));
}
}C++ · compiled/locker_pool.cpp
// Lockers 0 to n - 1: rent any free one, give one back, ask about one, count the free ones. Every call is O(1).
#include <print>
#include <stdexcept>
#include <string>
#include <vector>
class LockerPool {
public:
explicit LockerPool(int n) : rented_(n, false) {
stack_.reserve(n); // the stack never holds more than n lockers, so it never reallocates
for (int k = n - 1; k >= 0; --k) stack_.push_back(k); // locker 0 is on top, at the back
}
// Rent any free locker and return its number, or -1 when every locker is rented.
int rent() {
if (stack_.empty()) return -1;
int k = stack_.back();
stack_.pop_back();
rented_[k] = true;
return k;
}
// Free locker k and return true; return false, and change nothing, if it is already free.
bool give_back(int k) {
if (!rented_[k]) return false; // pushing k again would put it in the stack twice
rented_[k] = false;
stack_.push_back(k);
return true;
}
bool is_free(int k) const { return !rented_[k]; }
int free_count() const { return static_cast<int>(stack_.size()); }
private:
std::vector<bool> rented_; // rented_[k]: is locker k rented?
std::vector<int> stack_; // the free lockers
// Invariant: stack_ holds exactly the lockers k with rented_[k] false, each of them once.
};
// Runs one test: ops[0] creates the pool from args[0], then each method is called with its arguments.
std::vector<std::string> replay(const std::vector<std::string>& ops, const std::vector<std::vector<int>>& args) {
LockerPool pool(args[0][0]);
std::vector<std::string> answers{"null"};
auto text = [](bool b) { return std::string(b ? "true" : "false"); };
for (std::size_t i = 1; i < ops.size(); ++i) {
if (ops[i] == "rent") answers.push_back(std::to_string(pool.rent()));
else if (ops[i] == "give_back") answers.push_back(text(pool.give_back(args[i][0])));
else if (ops[i] == "is_free") answers.push_back(text(pool.is_free(args[i][0])));
else if (ops[i] == "free_count") answers.push_back(std::to_string(pool.free_count()));
else throw std::invalid_argument("unknown operation " + ops[i]);
}
return answers;
}
void show(const std::vector<std::string>& answers) {
std::string line = "[";
for (std::size_t i = 0; i < answers.size(); ++i) line += (i ? ", " : "") + answers[i];
std::println("{}]", line);
}
int main() {
show(replay({"LockerPool", "rent", "rent", "give_back", "give_back", "is_free", "rent", "free_count", "rent", "rent"},
{{3}, {}, {}, {0}, {0}, {0}, {}, {}, {}, {}}));
show(replay({"LockerPool", "is_free", "rent", "rent", "is_free", "give_back", "free_count"},
{{1}, {0}, {}, {}, {0}, {0}, {}}));
}Go · compiled/locker_pool.go
// Lockers 0 to n - 1: rent any free one, give one back, ask about one, count the free ones. Every call is O(1).
package main
import (
"fmt"
"strconv"
"strings"
)
type LockerPool struct {
rented []bool // rented[k]: is locker k rented? make starts every element at false
stack []int // the free lockers; locker 0 is on top, at the end
// Invariant: stack holds exactly the lockers k with rented[k] false, each of them once.
}
func NewLockerPool(n int) *LockerPool {
stack := make([]int, n) // capacity n: the stack never holds more, so append never reallocates
for i := range stack {
stack[i] = n - 1 - i
}
return &LockerPool{rented: make([]bool, n), stack: stack}
}
// Rent rents any free locker and returns its number, or -1 when every locker is rented.
func (p *LockerPool) Rent() int {
if len(p.stack) == 0 {
return -1
}
k := p.stack[len(p.stack)-1]
p.stack = p.stack[:len(p.stack)-1]
p.rented[k] = true
return k
}
// GiveBack frees locker k and returns true; it returns false, and changes nothing, if k is already free.
func (p *LockerPool) GiveBack(k int) bool {
if !p.rented[k] {
return false // pushing k again would put it in the stack twice
}
p.rented[k] = false
p.stack = append(p.stack, k)
return true
}
func (p *LockerPool) IsFree(k int) bool { return !p.rented[k] }
func (p *LockerPool) FreeCount() int { return len(p.stack) }
// replay runs one test: ops[0] creates the pool from args[0], then each method is called with its arguments.
func replay(ops []string, args [][]int) []string {
pool := NewLockerPool(args[0][0])
answers := []string{"null"}
for i := 1; i < len(ops); i++ {
switch ops[i] {
case "rent":
answers = append(answers, strconv.Itoa(pool.Rent()))
case "give_back":
answers = append(answers, strconv.FormatBool(pool.GiveBack(args[i][0])))
case "is_free":
answers = append(answers, strconv.FormatBool(pool.IsFree(args[i][0])))
case "free_count":
answers = append(answers, strconv.Itoa(pool.FreeCount()))
default:
panic("unknown operation " + ops[i])
}
}
return answers
}
func main() {
fmt.Println("[" + strings.Join(replay(
[]string{"LockerPool", "rent", "rent", "give_back", "give_back", "is_free", "rent", "free_count", "rent", "rent"},
[][]int{{3}, {}, {}, {0}, {0}, {0}, {}, {}, {}, {}}), ", ") + "]")
fmt.Println("[" + strings.Join(replay(
[]string{"LockerPool", "is_free", "rent", "rent", "is_free", "give_back", "free_count"},
[][]int{{1}, {0}, {}, {}, {0}, {0}, {}}), ", ") + "]")
}compiled/run_pool.py
"""Builds and runs the Java, C++ and Go versions of LockerPool on the two tests of the statement."""
from session import run, versions
versions("java -version", "clang++ --version", "go version")
run("""
java LockerPool.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined locker_pool.cpp -o locker_pool && ./locker_pool
go run locker_pool.go
""")Output
# openjdk version "25.0.4.1" LTS # Apple clang version 21.0.0 (clang-2100.3.34.2) # go version go1.27.1 darwin/arm64 $ java LockerPool.java [null, 0, 1, true, false, true, 0, 1, 2, -1] [null, true, 0, -1, false, true, 1] $ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined locker_pool.cpp -o locker_pool && ./locker_pool [null, 0, 1, true, false, true, 0, 1, 2, -1] [null, true, 0, -1, false, true, 1] $ go run locker_pool.go [null, 0, 1, true, false, true, 0, 1, 2, -1] [null, true, 0, -1, false, true, 1]
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 run_pool.py
compiled/session.py
"""Runs commands one by one, as you would type them in a terminal, and prints the whole session.
Each command is printed after "$ ", followed by everything it wrote (standard output and standard error together).
A command that fails adds "[exit status N]", and the script then exits with status 1, so that a session in which a
program could not be built or run is never recorded as if it had worked.
The commands use the toolchains this track pins: Java 25 (Temurin 25.0.4) and Go 1.27.1 from the mise installation
that also holds the Python running this file, and the system's clang++ (the Command Line Tools copy when it is
installed, which is the compiler that /usr/bin/clang++ would start). Everything the tools write goes into this
folder: HOME, TMPDIR and Go's caches point here, and Java is started with -XX:-UsePerfData through
JDK_JAVA_OPTIONS, so that the JVM keeps no performance-data file in the system's temporary folder; the java
launcher announces such an option with a "NOTE: Picked up JDK_JAVA_OPTIONS" line, which the session leaves out.
"""
import os
import re
import subprocess
import sys
from pathlib import Path
# .../installs/python/3.14.8/bin/python3 -> .../installs
INSTALLS = Path(sys.executable).resolve().parents[3]
TOOLS = [INSTALLS / "java" / "temurin-25.0.4+101.0.LTS" / "bin", INSTALLS / "go" / "1.27.1" / "bin"]
COMMAND_LINE_TOOLS = Path("/Library/Developer/CommandLineTools")
# A version line may carry a release date; the pages show no dates, so it is left out.
DATE = re.compile(r"\s+\d{4}-\d{2}-\d{2}")
JAVA_NOTE = "NOTE: Picked up JDK_JAVA_OPTIONS"
def environment():
here = Path.cwd()
for folder in ("home", "tmp", "go-cache", "go-path"):
(here / folder).mkdir(exist_ok=True)
path = [str(p) for p in TOOLS]
env = dict(os.environ)
if (COMMAND_LINE_TOOLS / "usr" / "bin").is_dir() and (COMMAND_LINE_TOOLS / "SDKs" / "MacOSX.sdk").is_dir():
path.append(str(COMMAND_LINE_TOOLS / "usr" / "bin"))
env.setdefault("SDKROOT", str(COMMAND_LINE_TOOLS / "SDKs" / "MacOSX.sdk"))
env.update(
PATH=os.pathsep.join([*path, env.get("PATH", "")]),
HOME=str(here / "home"),
TMPDIR=str(here / "tmp"),
GOCACHE=str(here / "go-cache"),
GOPATH=str(here / "go-path"),
GOTOOLCHAIN="local", # never download another Go
GOTELEMETRY="off",
JDK_JAVA_OPTIONS="-XX:-UsePerfData",
ASAN_OPTIONS="color=never",
UBSAN_OPTIONS="color=never",
)
return env
def shell(command):
return subprocess.run(command, shell=True, env=environment(), stdout=subprocess.PIPE, stderr=subprocess.STDOUT, text=True)
def versions(*commands):
"""Prints the first line that each command prints about its version, as a comment."""
for command in commands:
result = shell(command)
lines = [line for line in result.stdout.splitlines() if not line.startswith(JAVA_NOTE)]
if result.returncode != 0 or not lines:
sys.exit(f"{command} did not run: the pinned toolchain is missing here")
print(f"# {DATE.sub('', lines[0])}")
def run(script):
"""Runs each line of script, printing it after "$ " and then what it wrote; exits with 1 if a command failed."""
failed = 0
for command in script.strip().splitlines():
command = command.strip()
print(f"$ {command}")
result = shell(command)
for line in result.stdout.splitlines():
if not line.startswith(JAVA_NOTE):
print(line)
if result.returncode != 0:
print(f"[exit status {result.returncode}]")
failed += 1
if failed:
sys.exit(1)All five print the same two lists. What differs between the languages is small:
- Python keeps the stack in a list and works only at its end, with
appendandpop. - JavaScript does the same with
pushandpop. Its methods are namedgiveBack,isFreeandfreeCount, so the replayer maps the names the test uses to the methods. - Java starts every element of a new
boolean[]atfalse, as its language specification requires, so a new pool has every locker free without a loop. The stack is a plainint[]of n slots with a count,top, because the invariant says it never needs more. A single command,java LockerPool.java, compiles the file in memory and starts it: the source-file mode that JEP 330 added to the launcher in JDK 11. - C++ calls
reserve(n)once. The standard promises that no later insertion reallocates the vector until its size would pass that capacity, and the invariant keeps the size at n or below. The program was built with AddressSanitizer and UndefinedBehaviorSanitizer, which report an out-of-bounds access or undefined arithmetic when it happens; both stayed silent. - Go makes the stack with
make([]int, n), a slice whose length and capacity are both n. After a pop shortens the slice,appendreuses the same array whenever the capacity is enough, which the invariant guarantees. A new[]boolstarts with every elementfalse, Go’s zero value.
Step 4: tests that replay calls
A test of a class is a sequence of calls, and the examples of the statement are already written that way. A test can check such a sequence in two ways, and only one of them suits this problem:
Python · pool/replay_check.py
"""One test, checked two ways: against fixed expected answers, and against the model of the rules."""
from locker_pool import LockerPool, show
from model import first_wrong
OPS = ["LockerPool", "rent", "rent", "give_back", "give_back", "is_free", "rent", "free_count", "rent", "rent"]
ARGS = [[3], [], [], [0], [0], [0], [], [], [], []]
EXPECTED = [None, 0, 1, True, False, True, 0, 1, 2, -1] # written for a pool that rents locker 0 first
class HighFirstPool(LockerPool):
"""Also correct: the statement allows any free locker, and this pool rents the highest-numbered one first."""
def __init__(self, n):
super().__init__(n)
self.stack.reverse()
def replay(pool_class, ops, args):
"""ops[0] creates the pool from args[0]; then each method is called with its arguments. Returns every answer."""
pool = pool_class(*args[0])
return [None] + [getattr(pool, op)(*a) for op, a in zip(ops[1:], args[1:])]
calls = [(op, *a) for op, a in zip(OPS[1:], ARGS[1:])]
print(f"{'expected':<15}{show(EXPECTED)}")
for pool_class in (LockerPool, HighFirstPool):
answers = replay(pool_class, OPS, ARGS)
strict = next((i for i, (got, want) in enumerate(zip(answers, EXPECTED)) if got != want), None)
model = first_wrong(ARGS[0][0], calls, answers[1:])
print(f"{pool_class.__name__:<15}{show(answers)}")
print(f"{'':<15}strict: {'pass' if strict is None else f'fails at call {strict}'}, model: {'pass' if model is None else f'fails at call {model}'}")Output
expected [null, 0, 1, true, false, true, 0, 1, 2, -1]
LockerPool [null, 0, 1, true, false, true, 0, 1, 2, -1]
strict: pass, model: pass
HighFirstPool [null, 2, 1, false, false, true, 0, 0, -1, -1]
strict: fails at call 1, model: pass
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 replay_check.py
pool/model.py
"""Test helpers for the locker pool: a model of the rules, and the invariant of LockerPool."""
def first_wrong(n, calls, answers):
"""The number of the first call whose answer the rules forbid (calls count from 1), or None.
calls are tuples such as ("rent",) or ("give_back", 2); answers are what a pool of n lockers returned. The model
is the set of free lockers, so it accepts any free locker as an answer of rent(), as the statement does.
"""
free = set(range(n))
for i, ((op, *args), got) in enumerate(zip(calls, answers), start=1):
if op == "rent":
allowed = got in free if free else got == -1
free.discard(got)
elif op == "give_back":
allowed = got == (args[0] not in free)
free.add(args[0])
elif op == "is_free":
allowed = got == (args[0] in free)
else: # free_count
allowed = got == len(free)
if not allowed:
return i
return None
def invariant_holds(pool):
"""The stack holds exactly the lockers whose flag says free, each of them once (O(n): for tests only)."""
return sorted(pool.stack) == [k for k, taken in enumerate(pool.rented) if not taken]Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The strict check compares each answer with the expected list, and it fails HighFirstPool, a pool that rents the
highest-numbered free locker first. That pool is correct, because the statement allows any free locker. Its answers
also show what a hand-written test quietly assumes: give_back(0) returns false here because this pool never rented
locker 0, so the line meant to test giving back a rented locker now tests something else. The model check judges
each answer by the rules instead. first_wrong in model.py keeps the set of free lockers and accepts any member
of it from rent(), so it passes both pools, and it is what the random tests below use.
A bug that only a repeated call exposes
Here is the mistake this problem invites: a give_back that frees the locker and pushes it without checking that
it was rented. Its answers stay right, but a second give_back(k) puts k on the stack twice, and from then on two
travellers can be handed the same locker. The examples of the statement miss it, because none of their calls depends
on the copy. Random tests find it, as long as they are small: with one to four lockers and at most twelve calls,
repeated calls on the same locker are common.
"""Random tests checked by the model: LockerPool, and a copy whose give_back() leaves out one check."""
import random
from locker_pool import LockerPool
from model import first_wrong, invariant_holds
class PushTwicePool(LockerPool):
"""The bug: give_back() answers correctly, but it pushes k even when k is already free."""
def give_back(self, k):
was_rented = self.rented[k]
self.rented[k] = False
self.stack.append(k)
return was_rented
def answers_of(pool_class, n, calls):
pool = pool_class(n)
return [getattr(pool, op)(*args) for op, *args in calls]
def fails(pool_class, n, calls):
return first_wrong(n, calls, answers_of(pool_class, n, calls)) is not None
def random_test(rng, ops):
"""A few lockers and a dozen calls at most, so that repeated calls on the same locker are common."""
n = rng.randint(1, 4)
calls = []
for _ in range(rng.randint(1, 12)):
op = rng.choice(ops)
calls.append((op, rng.randrange(n)) if op in ("give_back", "is_free") else (op,))
return n, calls
def shrink(pool_class, n, calls):
"""Drops one call at a time, and then the highest locker, for as long as the test still fails."""
changed = True
while changed:
changed = False
for i in range(len(calls)):
shorter = calls[:i] + calls[i + 1:]
if fails(pool_class, n, shorter):
calls, changed = shorter, True
break
if n > 1 and all(len(c) == 1 or c[1] < n - 1 for c in calls) and fails(pool_class, n - 1, calls):
n, changed = n - 1, True
return n, calls
def text(call):
op, *args = call
return f"{op}({', '.join(map(str, args))})"
def first_broken_invariant(pool_class, n, calls):
"""The number of the first call after which the invariant no longer holds, or None."""
pool = pool_class(n)
for i, (op, *args) in enumerate(calls, start=1):
getattr(pool, op)(*args)
if not invariant_holds(pool):
return i
return None
def report(title, pool_class, tests):
failing = next((t for t, (n, calls) in enumerate(tests, start=1) if fails(pool_class, n, calls)), None)
if failing is None:
print(f"{title}: {len(tests):,} random tests, every answer allowed")
return
n, calls = tests[failing - 1]
answers = answers_of(pool_class, n, calls)
at = first_wrong(n, calls, answers)
print(f"{title}: test {failing} (n = {n}, {len(calls)} calls) fails at call {at}: {text(calls[at - 1])} -> {answers[at - 1]}")
n, calls = shrink(pool_class, n, calls)
answers = answers_of(pool_class, n, calls)
print(f" shrunk to n = {n}: " + ", ".join(f"{text(c)} -> {a}" for c, a in zip(calls, answers)))
print(f" the invariant breaks at call {first_broken_invariant(pool_class, n, calls)}, the first wrong answer is call {first_wrong(n, calls, answers)}")
ALL = ["rent", "rent", "give_back", "give_back", "is_free", "free_count"]
NO_COUNT = ["rent", "rent", "give_back", "give_back", "is_free"]
for mix, label in ((ALL, ""), (NO_COUNT, ", tests without free_count()")):
rng = random.Random(13)
tests = [random_test(rng, mix) for _ in range(2000)]
report(f"LockerPool{label}", LockerPool, tests)
report(f"PushTwicePool{label}", PushTwicePool, tests)Output
LockerPool: 2,000 random tests, every answer allowed PushTwicePool: test 3 (n = 1, 9 calls) fails at call 5: free_count() -> 2 shrunk to n = 1: give_back(0) -> False, free_count() -> 2 the invariant breaks at call 1, the first wrong answer is call 2 LockerPool, tests without free_count(): 2,000 random tests, every answer allowed PushTwicePool, tests without free_count(): test 7 (n = 2, 12 calls) fails at call 7: rent() -> 0 shrunk to n = 1: give_back(0) -> False, rent() -> 0, rent() -> 0 the invariant breaks at call 1, the first wrong answer is call 3
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 stress_pool.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
LockerPool passes every test of both mixes. PushTwicePool fails the third random test, at its fifth call, where
free_count() reports 2 free lockers in a pool of one. Shrinking drops calls, then lockers, while the test still
fails, and it ends with two calls: give_back(0) on a free locker, then free_count(). In the tests without
free_count(), the shrunk failure is the one a traveller would meet: after one give_back(0) on a free locker, two
rent() calls both return locker 0. Every run draws the same tests, because the generator starts from a fixed
seed, and the shrunk sequences are short enough to keep as regression tests. The
stress-testing lesson builds this kind of harness step by step.
The last line of each failure is the reason to write the invariant as code. Checked after every call, it breaks at
call 1, the give_back(0) that causes the bug, while the first wrong answer comes one or two calls later. The
check is O(n), too slow for the class itself, but in a test it points at the call to fix.
When the cost target changes, the structures change
Suppose the station wants the lowest-numbered free locker rented first, so that travellers walk less. The methods
and their answers stay the same apart from that one promise, but the stack no longer works, because the lowest free
locker can be anywhere in it. A binary heap keeps the smallest item at its root, and Python’s heapq maintains one
in a plain list:
"""A new cost target: rent() must give the lowest-numbered free locker. A heap takes the place of the stack."""
import heapq
import random
from locker_pool import LockerPool
class LowestFreePool:
def __init__(self, n):
self.rented = [False] * n
self.heap = list(range(n)) # a sorted list already meets the heap rule heap[k] <= heap[2k + 1], heap[2k + 2]
# Invariant: the heap holds exactly the lockers k with rented[k] False, each of them once.
def rent(self):
"""Rent the lowest-numbered free locker: O(log n)."""
if not self.heap:
return -1
k = heapq.heappop(self.heap)
self.rented[k] = True
return k
def give_back(self, k):
"""O(log n): the locker goes back into the heap, which moves it to its place."""
if not self.rented[k]:
return False
self.rented[k] = False
heapq.heappush(self.heap, k)
return True
def is_free(self, k):
return not self.rented[k]
def free_count(self):
return len(self.heap)
calls = [("rent",), ("rent",), ("rent",), ("give_back", 0), ("give_back", 2), ("rent",), ("rent",)]
print("calls:".ljust(16) + ", ".join(op + (f"({args[0]})" if args else "()") for op, *args in calls))
for pool_class in (LockerPool, LowestFreePool):
pool = pool_class(4)
print(f"{pool_class.__name__ + ':':<16}" + ", ".join(str(getattr(pool, op)(*args)) for op, *args in calls))
# Checked against the plainest model: the lowest free locker is min() of the set of free lockers.
rng = random.Random(7)
for test in range(2000):
n = rng.randint(1, 6)
pool, free = LowestFreePool(n), set(range(n))
for _ in range(rng.randint(1, 15)):
if rng.random() < 0.5:
want = min(free) if free else -1
assert pool.rent() == want, f"test {test}"
free.discard(want)
else:
k = rng.randrange(n)
assert pool.give_back(k) == (k not in free), f"test {test}"
free.add(k)
assert pool.free_count() == len(free)
print("LowestFreePool: 2,000 random tests, every rent() gave the lowest free locker")Output
calls: rent(), rent(), rent(), give_back(0), give_back(2), rent(), rent() LockerPool: 0, 1, 2, True, True, 2, 0 LowestFreePool: 0, 1, 2, True, True, 0, 2 LowestFreePool: 2,000 random tests, every rent() gave the lowest free locker
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 lowest_free.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
The two pools agree until the sixth call. After lockers 0 and 2 go back, LockerPool rents 2, the last one in, and
LowestFreePool rents 0. The invariant is the same sentence with “heap” in place of “stack”, and the flags stay as
they were, so is_free(k) is still O(1). The price is paid by the other methods: heappop and heappush each move
one item along a path between the root and a leaf, about log₂ n steps, so rent() and give_back(k) become
O(log n), about 17 steps for 100,000 lockers. Starting from list(range(n)) needs no heapify, because a sorted
list already meets the heap rule of the heapq documentation: every item is at most the two items below it.
| Criterion | Any free locker | The lowest free locker |
|---|---|---|
| Free lockers kept in | A stack | A min-heap |
| Renting | O(1) | O(log n) |
| Giving back | O(1) | O(log n) |
| Lookups and counts | O(1) | O(1) |
| Order of rentals | Last in, first out | Smallest number first |
| When to choose | Any free locker will do | The statement names the locker |
The lesson generalises: when an operation must return a particular item, the smallest, the oldest or the most frequent, it usually costs more than one that may return any item, so read that promise in the statement closely.
The combinations this module builds
Most design problems use one of a few pairs of structures, and the next lessons of this module build them one at a time. In each pair, both structures describe the same items and serve different operations:
- Flags and a stack, this lesson’s pool: a lookup by number, and some free item in O(1).
- A hash map and a doubly linked list: a lookup by key, and the items in order of their last use, which is what an LRU cache needs.
- Counts per key and keys grouped by count: lookups that also know the most or the least frequent key, behind LFU caches and frequency stacks.
- A hash map and an array: inserting, removing and picking a uniformly random item, each in O(1) on average.
- Two stacks: a first-in, first-out queue built from two last-in, first-out stacks.
- A list of versions for each key: the value a key had at any moment, for time-versioned stores.
- A position kept between calls: iterators that flatten, peek or interleave without copying their input.
- A hash map and a heap: the best item on demand while the priorities of items keep changing; the heaps module builds it.
Practise: drivers in each zone
The exercise is a new design for the same four steps. A cab app needs move, leave, zone_of and count, each
in O(1) on average, and no single map gives all four; the moves of the
hash map lesson are the parts to combine. The sample tests
include random sequences checked against a slow model, and one test of 90,000 calls with up to 30,000 drivers on
duty, which a count() that searches the drivers would not finish within the time limit. Write the invariant as a
comment before the first method.
Exercise · Easy · Python, JavaScript
Count the drivers in each zone in O(1)
A cab app shows how many of its drivers are in each zone of a city right now. Write the class ZoneBoard with four methods (in JavaScript: move, leave, zoneOf and count, with null for None):
move(driver, zone)puts the driver inzone, whatever was true before: the driver was in another zone, in the same zone, or off duty. It returns nothing.leave(driver)takes the driver off duty and returnsTrue, or returnsFalseif the driver was already off duty or has never been seen.zone_of(driver)returns the driver's zone, orNonewhile the driver is off duty.count(zone)returns how many drivers are inzonenow, and0for a zone that nobody is in.
Drivers and zones are non-empty strings. Every call must take O(1) time on average, so count() may not look at every driver: one sample test makes 90,000 calls with up to 30,000 drivers on duty.
board = ZoneBoard()
board.move("asha", "north")
board.move("bala", "north")
board.count("north") # 2
board.move("asha", "south")
board.count("north") # 1
board.leave("bala") # True
board.leave("bala") # False
board.zone_of("bala") # NoneWork the way this lesson does. Write the cost of each method, then, as a comment above the class, the invariant that keeps your structures in agreement. Check every method against it before you run the sample tests.
Python · Starter code · zones.py
class ZoneBoard:
"""How many drivers are in each zone. Every call is O(1) on average."""
def __init__(self):
# Replace this line with your structures, and write the invariant that ties them together.
pass
def move(self, driver, zone):
"""The driver is now in zone: from another zone, from the same zone or from off duty."""
def leave(self, driver):
"""The driver goes off duty: True, or False if the driver was off duty already."""
return False
def zone_of(self, driver):
"""The driver's zone, or None while the driver is off duty."""
return None
def count(self, zone):
"""How many drivers are in zone now (0 if nobody is)."""
return 0The sample tests · test_zones.py
import random
from zones import ZoneBoard
def test_example():
"""the example of the prompt"""
board = ZoneBoard()
board.move("asha", "north")
board.move("bala", "north")
board.move("chen", "south")
assert board.count("north") == 2
assert board.zone_of("chen") == "south"
board.move("asha", "south")
assert (board.count("north"), board.count("south")) == (1, 2)
assert board.leave("bala") is True
assert board.leave("bala") is False
assert board.count("north") == 0
assert board.zone_of("bala") is None
def test_same_zone_twice():
"""moving a driver to the zone they are already in changes nothing"""
board = ZoneBoard()
board.move("dev", "east")
board.move("dev", "east")
assert board.count("east") == 1
assert board.zone_of("dev") == "east"
def test_never_seen():
"""a driver and a zone that nobody has mentioned yet"""
board = ZoneBoard()
assert board.count("west") == 0
assert board.zone_of("esha") is None
assert board.leave("esha") is False
assert board.count("west") == 0
def test_back_on_duty():
"""a driver who left and comes back is counted once, in the new zone"""
board = ZoneBoard()
board.move("farid", "west")
assert board.leave("farid") is True
board.move("farid", "east")
assert (board.count("west"), board.count("east")) == (0, 1)
assert board.zone_of("farid") == "east"
def test_random_sequences():
"""500 random sequences of calls on 4 drivers and 3 zones, checked against a slow model that scans the drivers"""
rng = random.Random(29)
drivers, zones = ["d0", "d1", "d2", "d3"], ["z0", "z1", "z2"]
for trial in range(500):
board, where = ZoneBoard(), {} # where: the model, driver -> zone for the drivers on duty
for step in range(rng.randint(1, 20)):
d, z, kind = rng.choice(drivers), rng.choice(zones), rng.randrange(4)
if kind == 0:
board.move(d, z)
where[d] = z
elif kind == 1:
was_on_duty = where.pop(d, None) is not None
assert board.leave(d) is was_on_duty, f"trial {trial}, call {step + 1}: leave({d!r})"
elif kind == 2:
assert board.zone_of(d) == where.get(d), f"trial {trial}, call {step + 1}: zone_of({d!r})"
else:
want = sum(1 for zone in where.values() if zone == z)
assert board.count(z) == want, f"trial {trial}, call {step + 1}: count({z!r})"
def test_many_calls():
"""90,000 calls with 30,000 drivers: count() must not look at every driver"""
board = ZoneBoard()
for i in range(30_000):
board.move(f"driver{i}", f"zone{i % 100}") # 300 drivers in each of 100 zones
total = sum(board.count(f"zone{i % 100}") for i in range(30_000))
for i in range(0, 30_000, 2):
board.leave(f"driver{i}") # the even zones empty, the odd zones keep their 300
total += sum(board.count(f"zone{i % 100}") for i in range(15_000))
assert total == 30_000 * 300 + 7_500 * 300JavaScript · Starter code · zones.mjs
/** How many drivers are in each zone. Every call is O(1) on average. */
export class ZoneBoard {
constructor() {
// Replace this line with your structures, and write the invariant that ties them together.
}
/** The driver is now in zone: from another zone, from the same zone or from off duty. */
move(driver, zone) {}
/** The driver goes off duty: true, or false if the driver was off duty already. */
leave(driver) {
return false;
}
/** The driver's zone, or null while the driver is off duty. */
zoneOf(driver) {
return null;
}
/** How many drivers are in zone now (0 if nobody is). */
count(zone) {
return 0;
}
}The sample tests · zones.test.mjs
import { test, assert } from 'mysmartcopilot:test';
import { ZoneBoard } from './zones.mjs';
let seed = 29;
const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
const pick = (items) => items[Math.floor(random() * items.length)];
test('the example of the prompt', () => {
const board = new ZoneBoard();
board.move('asha', 'north');
board.move('bala', 'north');
board.move('chen', 'south');
assert.equal(board.count('north'), 2);
assert.equal(board.zoneOf('chen'), 'south');
board.move('asha', 'south');
assert.deepEqual([board.count('north'), board.count('south')], [1, 2]);
assert.equal(board.leave('bala'), true);
assert.equal(board.leave('bala'), false);
assert.equal(board.count('north'), 0);
assert.equal(board.zoneOf('bala'), null);
});
test('moving a driver to the zone they are already in changes nothing', () => {
const board = new ZoneBoard();
board.move('dev', 'east');
board.move('dev', 'east');
assert.equal(board.count('east'), 1);
assert.equal(board.zoneOf('dev'), 'east');
});
test('a driver and a zone that nobody has mentioned yet', () => {
const board = new ZoneBoard();
assert.equal(board.count('west'), 0);
assert.equal(board.zoneOf('esha'), null);
assert.equal(board.leave('esha'), false);
assert.equal(board.count('west'), 0);
});
test('a driver who left and comes back is counted once, in the new zone', () => {
const board = new ZoneBoard();
board.move('farid', 'west');
assert.equal(board.leave('farid'), true);
board.move('farid', 'east');
assert.deepEqual([board.count('west'), board.count('east')], [0, 1]);
assert.equal(board.zoneOf('farid'), 'east');
});
test('500 random sequences of calls, checked against a slow model that scans the drivers', () => {
const drivers = ['d0', 'd1', 'd2', 'd3'];
const zones = ['z0', 'z1', 'z2'];
for (let trial = 0; trial < 500; trial++) {
const board = new ZoneBoard();
const where = new Map(); // the model: driver -> zone for the drivers on duty
const calls = 1 + Math.floor(random() * 20);
for (let step = 1; step <= calls; step++) {
const d = pick(drivers);
const z = pick(zones);
const kind = Math.floor(random() * 4);
if (kind === 0) {
board.move(d, z);
where.set(d, z);
} else if (kind === 1) {
const wasOnDuty = where.delete(d);
assert.equal(board.leave(d), wasOnDuty, `trial ${trial}, call ${step}: leave("${d}")`);
} else if (kind === 2) {
assert.equal(board.zoneOf(d), where.has(d) ? where.get(d) : null, `trial ${trial}, call ${step}: zoneOf("${d}")`);
} else {
const want = [...where.values()].filter((zone) => zone === z).length;
assert.equal(board.count(z), want, `trial ${trial}, call ${step}: count("${z}")`);
}
}
}
});
test('90,000 calls with 30,000 drivers: count() must not look at every driver', () => {
const board = new ZoneBoard();
for (let i = 0; i < 30000; i++) board.move(`driver${i}`, `zone${i % 100}`); // 300 drivers in each of 100 zones
let total = 0;
for (let i = 0; i < 30000; i++) total += board.count(`zone${i % 100}`);
for (let i = 0; i < 30000; i += 2) board.leave(`driver${i}`); // the even zones empty, the odd zones keep their 300
for (let i = 0; i < 15000; i++) total += board.count(`zone${i % 100}`);
assert.equal(total, 30000 * 300 + 7500 * 300);
});A hint
count() cannot search the drivers, so the answer has to be ready before anyone asks: keep one number per zone and change it in move() and leave(). Then work through the case that is easy to miss: a driver who is already in north moves to south. Which numbers change, and what do you need to know about the driver to change them?
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide, QuickJS): nothing is sent to mysmartcopilot.com. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Check yourself
6 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
Interview questions
Fresher · Why do design-a-data-structure problems often need two structures for one set of items?
Because every operation has its own cost target, and one structure is rarely fast at all of them. In a locker pool,
is_free(k) needs a lookup by number, which an array of flags answers in O(1), while rent() needs some free
locker without a search, which a stack of free numbers answers in O(1). The flags alone make rent() search, and
the stack alone makes is_free(k) search, so you keep both and let each operation use the one that answers it. The
price is that every change must update both structures, and the invariant says how they agree: the stack holds
exactly the lockers whose flag says free, each of them once. Write that sentence down, check every method against
it, and check it in your tests.
Fresher · How do you test a class whose answers depend on the calls made before?
With operation sequences: lists of calls and their arguments, replayed on a fresh object with every answer checked, which is also how these problems are graded. Write short sequences by hand for the cases the statement defines, such as an empty structure, a repeated call and a missing key. Then generate thousands of random sequences on a tiny size, so that repeated calls on the same item are common, and judge every answer with a model, a slow class that is plainly right. A model also accepts answers that are not unique, such as any free locker, where a fixed list of expected answers would fail a correct solution. Shrink a failing sequence by dropping calls while it still fails, and keep the short version as a regression test.
Key takeaways
- Write the API first, with every method’s answer in the edge cases and the cost it must meet; that table decides the structures.
- When no single structure meets every cost, keep two that describe the same items, and let each operation use the one that answers it: here flags for lookups by number and a stack for any free locker.
- State the invariant in one sentence and check every method against it. It proves answers such as
free_count()right, and a test that checks it after every call stops at the call that breaks it. - Test with sequences of calls replayed on a fresh object. When several answers are allowed, judge them with a model instead of a fixed list, and shrink random failures to a few calls.
- A changed promise changes the structures: “the lowest free locker” turns an O(1) stack into an O(log n) heap.
References
- Time complexity of operations on built-in types (Python Software Foundation)
- heapq: Heap queue algorithm (Python Software Foundation)
- random: Notes on reproducibility (Python Software Foundation)
- The Java Language Specification, Java SE 25: 4.12.5 Initial Values of Variables (Oracle)
- JEP 330: Launch Single-File Source-Code Programs (OpenJDK)
- Working Draft, Programming Languages: C++ (N4950), [vector.overview] and [vector.capacity] (ISO/IEC JTC1/SC22/WG21)
- The Go Programming Language Specification: Appending to and copying slices (The Go Authors)
- The Go Programming Language Specification: The zero value (The Go Authors)
- AddressSanitizer (Clang documentation) (LLVM Project)
- UndefinedBehaviorSanitizer (Clang documentation) (LLVM Project)
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress