INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP
01
00/15
01 / COVER MODULE 27 · DESIGN
INVARIANT · MODULE 27 · DESIGN
PICK THE FIELDS, THEN EVERY CALL IS CHEAP

A design problem gives a list of calls and a cost for each. The work is choosing what the class keeps: an array and its index, two stacks, a list in expiry order, a bucket per count, a heap that tolerates stale entries. Twelve moves, fifteen problems.

15Problems
5Families
12Units
12Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 15 PROBLEMS

Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.

ARRAYS AND INDEX MAPS · 05
STACKS · 04
VERSIONS AND EXPIRY · 02
BUCKETS BY COUNT · 02
HEAPS · 02
SOLVED HAS A LEETCODE LINK
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
03 / MECHANISM UNIT 01 · AN ARRAY IS THE WHOLE DESIGN

A RUN OF FREE UNITS

The memory is the array itself, one mID per unit and 0 where it is free. allocate counts the free units ending at each index and fills the first run that reaches size.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
04 / DRILL UNIT 01 · An Array Is the Whole Design · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Allocator(5): allocate(2, 1), allocate(2, 2), freeMemory(1), allocate(3, 3)?

Units 0 and 1 go to mID 1, units 2 and 3 to mID 2. Freeing mID 1 clears two units, which leaves 0, 1 and 4 free, and no three of them are in a row.

DRILL 02 · RECALL

Why is a plain array enough for the allocator?

Each call scans at most 1000 units, so 1000 calls cost about 10⁶ steps. A free list or a tree of runs saves time the limits never ask for.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
05 / PROBLEM #01 · ARRAY · MED

Design Memory Allocator

MED array ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Memory is n units. Allocate the leftmost run of size free units to an id, or free every unit that id holds.

INTUITION

n and the number of calls are both at most 1000, so a plain array of owners is the whole design. To allocate, walk the array keeping run, the free units in a row ending here. The first time run reaches size, the block ends here and starts size − 1 units back, the leftmost block that fits. To free, clear every unit holding the id and count them.

STEPS
  1. mem[i] is the id in unit i, 0 if free
  2. Walk i, setting run to 0 on a used unit and to run + 1 on a free one
  3. When run reaches size, fill i − size + 1 to i and return the start
  4. freeMemory clears and counts every unit holding the id
BRUTEO(n · size) per allocate, testing every start for size free units
→
OPTIMALO(n) per call
↕ SCROLL
class Allocator {
    vector<int> mem;                           // the mID in each unit, 0 if free
public:
    Allocator(int n) : mem(n, 0) {}
    int allocate(int size, int mID) {
        int run = 0;                           // free units in a row, ending at i
        for (int i = 0; i < (int)mem.size(); i++) {
            run = mem[i] ? 0 : run + 1;
            if (run < size) continue;          // not long enough yet
            fill_n(mem.begin() + i - size + 1, size, mID);   // the leftmost block that fits
            return i - size + 1;
        }
        return -1;
    }
    int freeMemory(int mID) {
        int cnt = 0;
        for (int& x : mem)
            if (x == mID) { x = 0; cnt++; }
        return cnt;
    }
};
TIMEO(n) per callone walk of the units
SPACEO(n)the owners
TRAP

A run that is not reset. Counting free units without resetting at a used one adds up free units that are not next to each other. With units free, used, free, allocate(2) would claim a block of 2 that does not exist.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
06 / PROBLEM #02 · ARRAY · MED

Simple Bank System

MED array ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Accounts 1 to n hold balances. Run each transfer, deposit or withdrawal only if its accounts exist and the money is there.

INTUITION

Account a lives at index a − 1 of an array, so every call is O(1). The work is in the order. A transfer touches two accounts, and if it debits the first before checking the second, a bad account number leaves money gone. So every condition is checked first, and only then does anything change.

STEPS
  1. Account a is bal[a − 1]
  2. An account number is valid when 1 ≤ a ≤ n
  3. Check every account and the balance before changing anything
  4. Then debit, credit, and return true
↕ SCROLL
class Bank {
    vector<long long> bal;                     // account a is bal[a - 1]
    bool ok(int a) { return a >= 1 && a <= (int)bal.size(); }
public:
    Bank(vector<long long>& balance) : bal(balance) {}
    bool transfer(int account1, int account2, long long money) {
        if (!ok(account1) || !ok(account2) || bal[account1 - 1] < money)
            return false;                      // check everything before changing anything
        bal[account1 - 1] -= money;
        bal[account2 - 1] += money;
        return true;
    }
    bool deposit(int account, long long money) {
        if (!ok(account)) return false;
        bal[account - 1] += money;
        return true;
    }
    bool withdraw(int account, long long money) {
        if (!ok(account) || bal[account - 1] < money) return false;
        bal[account - 1] -= money;
        return true;
    }
};
TIMEO(1) per callan index into the array
SPACEO(n)the balances
TRAP

Checking the second account too late. In Python, an account number of 0 reads bal[−1], the last account, without an error. A transfer to account 0 that skips the check moves the money into account n.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
07 / DRILL UNIT 01 · An Array Is the Whole Design · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Bank([5, 10]): withdraw(1, 5), transfer(2, 3, 1), deposit(1, 3), transfer(1, 2, 4)?

Account 1 goes down to 0. There is no account 3, so that transfer fails. The deposit makes account 1 hold 3, which is less than 4.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
08 / MECHANISM UNIT 02 · BUCKETS AND CHAINS

BUCKETS AND CHAINS

A key goes to bucket key % B, and each bucket is a short list of (key, value) pairs. put looks for the key before it appends, and remove fills the hole with the bucket's last pair.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
09 / DRILL UNIT 02 · Buckets and Chains

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

With 5 buckets: put(1, 10), put(6, 60), put(11, 7), remove(1). What does bucket 1 hold now?

All three keys leave 1 over 5. remove(1) finds key 1 at the front of the chain and fills its slot with the last pair, (11, 7), so the order changes.

DRILL 02 · RECALL

Why is the number of buckets a prime such as 1009?

With B = 1000, keys that step by 10 land in only 100 buckets. A prime shares no factor with any step below it, so such keys spread over all B.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
10 / PROBLEM #03 · ARRAY · EASY

Design HashMap

EASY array ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Build put, get and remove for integer keys without a built-in hash table.

INTUITION

Keys go into B buckets by key % B, and each bucket keeps a short list of [key, value] pairs, its chain. Every call hashes once and then scans only that chain. With B a prime near 1000 and at most 10⁴ keys, a chain holds about ten pairs. To remove, the last pair of the chain fills the hole, so nothing shifts.

STEPS
  1. B buckets; key k lives in bucket k % B
  2. put scans the chain, updating the key if it is there and appending it if not
  3. get scans the chain and returns −1 if the key is missing
  4. remove moves the chain's last pair into the hole and pops
BRUTEO(1) with an array of 10⁶ + 1 slots, which works only because the keys are small
→
OPTIMALO(1 + n/B) per call
↕ SCROLL
class MyHashMap {
    static const int B = 1009;                 // a prime number of buckets
    vector<vector<pair<int, int>>> b;          // bucket h: the pairs with key % B == h
public:
    MyHashMap() : b(B) {}
    void put(int key, int value) {
        auto& ch = b[key % B];
        for (auto& p : ch)
            if (p.first == key) { p.second = value; return; }   // already there: update it
        ch.push_back({key, value});
    }
    int get(int key) {
        for (auto& p : b[key % B])
            if (p.first == key) return p.second;
        return -1;
    }
    void remove(int key) {
        auto& ch = b[key % B];
        for (size_t i = 0; i < ch.size(); i++)
            if (ch[i].first == key) {
                ch[i] = ch.back();             // the last pair fills the hole
                ch.pop_back();
                return;
            }
    }
};
TIMEO(1 + n/B) per callone chain, about n/B pairs
SPACEO(B + n)the buckets and pairs
TRAP

A put that always appends. Putting a key twice leaves two pairs in its chain, and get finds the old one first. Every put must look for the key before it adds one.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
11 / MECHANISM UNIT 03 · SWAP IT WITH THE LAST

SWAP IT WITH THE LAST

The array gives a random pick in O(1), and the map from value to index finds any value in O(1). To remove from the middle, move the last value into the hole, fix its index, and pop the end.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
12 / DRILL UNIT 03 · Swap It With the Last · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

insert(1), insert(2), insert(3), remove(1). What are a and pos[3] now?

1 sits at index 0, and the last value, 3, moves into the hole there. pos[3] becomes 0, and the end of the array is popped.

DRILL 02 · RECALL

In the duplicates version, what takes the place of pos[val]?

Any copy may be removed, and the value moved into the hole may be any of its copies. Each value keeps the set of its indices, so both updates stay O(1).

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
13 / PROBLEM #04 · ARRAY · MED

Insert Delete GetRandom O(1)

MED array ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

A set with insert, remove and getRandom, each in O(1), every element equally likely.

INTUITION

A random pick needs an array, since a random index is O(1). Insert appends. Removing from the middle of an array would shift everything after it, so the last value moves into the hole instead, and the array stays packed. A map from value to index finds the hole in O(1) and must be told where the last value went.

STEPS
  1. a holds the values; pos maps value → index in a
  2. insert appends and records its index
  3. remove moves the last value into the hole, records its new index in pos, and pops the end
  4. getRandom picks a random index of a
BRUTEO(n) per remove, deleting from the middle of the array
→
OPTIMALO(1) average per call
↕ SCROLL
class RandomizedSet {
    vector<int> a;                             // the values, in no order
    unordered_map<int, int> pos;               // value -> its index in a
public:
    RandomizedSet() {}
    bool insert(int val) {
        if (pos.count(val)) return false;
        pos[val] = a.size();
        a.push_back(val);
        return true;
    }
    bool remove(int val) {
        if (!pos.count(val)) return false;
        int i = pos[val], last = a.back();
        a[i] = last;                           // the last value fills the hole
        pos[last] = i;
        a.pop_back();
        pos.erase(val);
        return true;
    }
    int getRandom() { return a[rand() % a.size()]; }
};
TIMEO(1) average per callone map lookup and one array write
SPACEO(n)the array and the map
TRAP

Forgetting where the last value went. If pos still says the moved value sits at the end, removing it later writes into a slot that no longer exists. Update pos[last] before popping, and erase val after, so removing the last value itself still works.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
14 / PROBLEM #05 · ARRAY · HARD

Insert Delete GetRandom O(1) - Duplicates allowed

HARD array ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

The same with duplicates: insert says whether the value was new, remove takes one copy, and getRandom weighs each value by its copies.

INTUITION

It is unit 3's array with one change: a value can sit at several indices, so pos maps each value to a set of indices. Remove takes any index of the value, and the last copy in the array moves into it. That copy's set gains the hole and loses the last index. Every copy is one slot of the array, so a random index weighs values by their counts.

STEPS
  1. a holds every copy; idx maps value → the set of its indices
  2. insert adds its index; it was new if that set now has one index
  3. remove takes any index i of val and moves the last copy to i
  4. Add i to the last value's set, then drop the old last index
BRUTEO(n) per remove, searching the array for a copy
→
OPTIMALO(1) average per call
↕ SCROLL
class RandomizedCollection {
    vector<int> a;                             // every copy, in no order
    unordered_map<int, unordered_set<int>> idx;   // value -> the indices holding it
public:
    RandomizedCollection() {}
    bool insert(int val) {
        idx[val].insert(a.size());
        a.push_back(val);
        return idx[val].size() == 1;
    }
    bool remove(int val) {
        auto f = idx.find(val);
        if (f == idx.end() || f->second.empty()) return false;
        int i = *f->second.begin(), last = a.back();   // any copy of val; the last copy fills it
        f->second.erase(i);
        a[i] = last;
        idx[last].insert(i);                   // add the hole first,
        idx[last].erase(a.size() - 1);         // then drop the old last index
        a.pop_back();
        return true;
    }
    int getRandom() { return a[rand() % a.size()]; }
};
TIMEO(1) average per calla few set operations
SPACEO(n)the copies and their indices
TRAP

Dropping before adding. When the copy removed is itself the last one, i is the last index. Dropping the last index first and then adding i puts the dead index back. Add first, then drop, and that case cancels out.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
15 / DRILL UNIT 03 · Swap It With the Last · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

RandomizedCollection: insert(4), insert(4), insert(5), remove(4), remove(4), remove(4)?

insert returns true only when 4 was absent, so the second is false, yet both copies go in. Two removes take both copies, and the third finds none.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
16 / MECHANISM UNIT 04 · TWO STACKS AROUND A CURSOR

TWO STACKS AROUND A CURSOR

The pages up to the one on screen sit on one stack, and the pages ahead sit on the other. back and forward move pages across one at a time, and a visit empties the stack ahead.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
17 / DRILL UNIT 04 · Two Stacks Around a Cursor · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

BrowserHistory("h"): visit("x"), visit("y"), back(1), visit("z"), back(1), forward(1). What do the back and forward calls return?

back(1) leaves y on the stack ahead. Visiting z clears it, so the next back returns to x and forward comes back to z, not y.

DRILL 02 · RECALL

In the text editor, why two stacks rather than one string and a cursor index?

With the text split at the cursor, every edit and every move touches only the two tops. In one string, typing near the front of a long text moves all of it.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
18 / PROBLEM #06 · STACK · MED

Design Browser History

MED stack ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

One tab: visit a page, go back or forward up to steps pages, and return the page on screen.

INTUITION

The pages behind and the page on screen form one stack, past, with the current page on top. The pages forward() can reach form a second stack, ahead. Going back moves pages from past to ahead one at a time, keeping at least one page in past. Going forward moves them back. Visiting a page pushes it onto past and clears ahead, since a new page ends the forward history.

STEPS
  1. past holds the history; its top is on screen
  2. visit pushes the url and clears ahead
  3. back moves pages from past to ahead while steps remain and past keeps two or more
  4. forward moves them back while steps remain and ahead is not empty
BRUTEO(1) per move with one array, a current index and an end index; stacks are O(steps)
→
OPTIMALO(steps) per move
↕ SCROLL
class BrowserHistory {
    vector<string> past, ahead;                // past.back() is the page on screen
public:
    BrowserHistory(string homepage) { past.push_back(homepage); }
    void visit(string url) {
        past.push_back(url);
        ahead.clear();                         // a new page ends the forward history
    }
    string back(int steps) {
        for (; steps > 0 && past.size() > 1; steps -= 1) {
            ahead.push_back(past.back());
            past.pop_back();
        }
        return past.back();
    }
    string forward(int steps) {
        for (; steps > 0 && !ahead.empty(); steps -= 1) {
            past.push_back(ahead.back());
            ahead.pop_back();
        }
        return past.back();
    }
};
TIMEO(steps) per moveone page per step
SPACEO(n)the pages visited
TRAP

A visit that keeps the forward pages. After back from c to a, visiting d must make forward() a no-op. If ahead still holds b and c, forward(2) returns c, a page no longer in the history.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
19 / PROBLEM #07 · STACK · HARD

Design a Text Editor

HARD stack ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

A text editor with a cursor: add text, delete left of the cursor, move it, and return the last 10 characters left of the cursor.

INTUITION

It is unit 4's two stacks, with characters for pages. left holds the text before the cursor, in order; right holds the text after it, nearest character on top. Adding text pushes onto left, and deleting pops from it. Moving the cursor left pops a character off left and pushes it onto right, and moving right does the opposite. Each call costs only the k characters it touches.

STEPS
  1. left holds the text before the cursor, right the text after it, nearest on top
  2. addText pushes every character onto left
  3. deleteText pops min(k, len(left)) characters and returns that count
  4. A cursor move shifts characters between the stacks; return left's last 10
BRUTEO(n) per call, slicing one string at the cursor
→
OPTIMALO(k) per call
↕ SCROLL
class TextEditor {
    string left, right;                        // either side of the cursor; right.back() is nearest
    string tail() { return left.substr(left.size() - min<size_t>(10, left.size())); }
public:
    TextEditor() {}
    void addText(string text) { left += text; }
    int deleteText(int k) {
        k = min<int>(k, left.size());          // only what is there can be deleted
        left.resize(left.size() - k);
        return k;
    }
    string cursorLeft(int k) {
        for (; k > 0 && !left.empty(); k -= 1) {
            right.push_back(left.back());
            left.pop_back();
        }
        return tail();
    }
    string cursorRight(int k) {
        for (; k > 0 && !right.empty(); k -= 1) {
            left.push_back(right.back());
            right.pop_back();
        }
        return tail();
    }
};
TIMEO(k) per callthe k characters touched, plus 10 to return
SPACEO(n)the text
TRAP

Returning k from deleteText. The count is what was actually deleted. With 4 characters left of the cursor, deleteText(10) deletes 4 and returns 4.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
20 / DRILL UNIT 04 · Two Stacks Around a Cursor · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

TextEditor: addText("abcdef"), cursorLeft(2), deleteText(3), cursorRight(5)?

The cursor stops after d, and the characters to its left are abcd. Deleting three takes bcd, and moving right reaches the end of aef.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
21 / MECHANISM UNIT 05 · VERSIONS PER INDEX

VERSIONS PER INDEX

Copying the array at every snap costs n each time. Each index keeps a list of (snap id, value) instead, one pair per change, and get searches it for the last change at or before the snap.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
22 / DRILL UNIT 05 · Versions per Index

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

SnapshotArray(2): set(1, 4), snap(), set(1, 6), snap(), set(1, 8), get(1, 0), get(1, 1)?

Index 1 keeps (0, 4), (1, 6) and (2, 8). Snap 0 saw 4 and snap 1 saw 6. The 8 belongs to snap 2, which was never taken.

DRILL 02 · RECALL

Why does set overwrite the last pair when its snap id is the current one?

Two sets between the same snaps leave one value for that snap. One pair per snap id also keeps the ids in the list distinct for the search.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
23 / PROBLEM #08 · TIME · MED

Snapshot Array

MED time ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

An array whose snap() freezes a version; get(index, snap_id) reads index as it was then.

INTUITION

Copying the whole array at every snap costs O(length) per snap. Instead, each index keeps its own history, the snap ids at which it changed and its value from each one on. A set in the current snap either appends a change or, if this index changed already in this snap, overwrites it. get finds the last change at or before snap_id by binary search.

STEPS
  1. Each index keeps (snap id, value) pairs, starting with (0, 0)
  2. set overwrites the last pair if it is from this snap, else appends one
  3. snap returns the current id and moves to the next
  4. get binary-searches for the last pair with id ≤ snap_id
BRUTEO(length) per snap, copying the whole array
→
OPTIMALO(log S) per get
↕ SCROLL
class SnapshotArray {
    vector<vector<pair<int, int>>> h;          // index i: (snap id, value) at each change
    int snapId = 0;
public:
    SnapshotArray(int length) : h(length, vector<pair<int, int>>{{0, 0}}) {}
    void set(int index, int val) {
        auto& v = h[index];
        if (v.back().first == snapId) v.back().second = val;   // changed already in this snap
        else v.push_back({snapId, val});
    }
    int snap() { return snapId++; }
    int get(int index, int snap_id) {
        auto& v = h[index];
        auto it = upper_bound(v.begin(), v.end(), make_pair(snap_id, INT_MAX));
        return prev(it)->second;               // the last change at or before snap_id
    }
};
TIMEO(log S) per geta binary search over one index's changes
SPACEO(length + sets)one pair per change
TRAP

A search that stops one change short. If index 0 changed at snaps 0 and 1, get(0, 1) wants the change at 1. A lower bound on 1 lands on it and then steps back to snap 0's value. Search for the first id above snap_id and step back from that.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
24 / MECHANISM UNIT 06 · THE NEWEST EXPIRY GOES LAST

THE NEWEST EXPIRY GOES LAST

Every token lives the same time, so a token made or renewed later expires later. A list in expiry order drops expired tokens from its front, and a map into the list lets renew move one.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
25 / DRILL UNIT 06 · The Newest Expiry Goes Last

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

timeToLive 3: generate("a", 1), generate("b", 2), renew("a", 4), countUnexpiredTokens(5)?

a expires at 4, so at time 4 it is gone and the renew does nothing. b expires at 5, the moment of the count.

DRILL 02 · RECALL

Why are the expired tokens always at the front of the list?

A generate or renew at time t sets expiry t + ttl, and the times only rise. Each new expiry is the largest so far, so appending keeps the list in order.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
26 / PROBLEM #09 · TIME · MED

Design Authentication Manager

MED time ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Tokens expire timeToLive seconds after they are generated or renewed. Count the live ones; the times only grow.

INTUITION

Every call's time is later than the last, so every new expiry is later than every expiry already stored. Keep the tokens in expiry order and a new or renewed token always goes at the back. The expired ones are then always at the front, and each call first drops them. A token expiring at t is gone at t. A linked list with a map from token to node gives O(1) for every move.

STEPS
  1. Keep (token → expiry) in order of expiry, the soonest first
  2. Every call first drops the front while its expiry ≤ now
  3. generate puts the token at the back with now + ttl
  4. renew moves a live token to the back with now + ttl; count is the size
BRUTEO(n) per count, scanning every token's expiry
→
OPTIMALO(1) amortised per call
↕ SCROLL
class AuthenticationManager {
    int ttl;
    list<pair<string, int>> q;                 // (token, expiry), the soonest first
    unordered_map<string, list<pair<string, int>>::iterator> at;
    void drop(int t) {
        while (!q.empty() && q.front().second <= t) {   // expired by t: it leaves the front
            at.erase(q.front().first);
            q.pop_front();
        }
    }
public:
    AuthenticationManager(int timeToLive) : ttl(timeToLive) {}
    void generate(string tokenId, int currentTime) {
        drop(currentTime);
        at[tokenId] = q.insert(q.end(), {tokenId, currentTime + ttl});   // the times grow: it goes last
    }
    void renew(string tokenId, int currentTime) {
        drop(currentTime);
        auto f = at.find(tokenId);
        if (f == at.end()) return;             // expired, or never made
        q.erase(f->second);
        f->second = q.insert(q.end(), {tokenId, currentTime + ttl});
    }
    int countUnexpiredTokens(int currentTime) {
        drop(currentTime);
        return q.size();
    }
};
TIMEO(1) amortised per calleach token is dropped once
SPACEO(n)the live tokens
TRAP

A token alive at its own expiry. The statement says a token expiring at t expires before anything else happens at t. renew(t) on it is ignored, and count(t) leaves it out. The drop test is expiry ≤ now.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
27 / MECHANISM UNIT 07 · A STACK PER FREQUENCY

A STACK PER FREQUENCY

A value's k-th copy goes on stack k. The highest stack that is not empty holds the most frequent values, and its top is the latest of them, which is what pop returns.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
28 / DRILL UNIT 07 · A Stack per Frequency

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

push(1), push(2), push(1), push(2), push(3), then pop() three times?

Stack 2 holds 1 and 2, with 2 on top, so the pops give 2 and then 1. Stack 1 holds 1, 2 and 3, and 3 is its top.

DRILL 02 · RECALL

Why does a value stay on the lower stacks when it is pushed again?

After its top copy goes, the value has one copy fewer and belongs where it was before. Its copy on the stack below is that place, kept in push order.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
29 / PROBLEM #10 · STACK · HARD

Maximum Frequency Stack

HARD stack ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

A stack whose pop removes the most frequent value, the one nearest the top among ties.

INTUITION

Count each value's copies. The k-th copy of a value goes onto stack k, so stack k holds, in push order, every value that has reached k copies. The most frequent value is the top of the highest stack, and among ties it is the latest pushed, which is what the stack order gives. Popping it lowers its count by one, and when that stack empties the highest frequency drops by one.

STEPS
  1. freq[v] counts the copies of v in the stack
  2. push adds 1 to freq[v], then pushes v onto group[freq[v]]
  3. pop takes the top of group[top], the highest frequency
  4. freq[v] −= 1; if that group is now empty, top −= 1
BRUTEO(n) per pop, counting and scanning down from the top
→
OPTIMALO(1) per call
↕ SCROLL
class FreqStack {
    unordered_map<int, int> freq;              // value -> its copies in the stack
    unordered_map<int, vector<int>> group;     // f -> the values whose f-th copy came in, in order
    int top = 0;                               // the highest frequency held
public:
    FreqStack() {}
    void push(int val) {
        int f = ++freq[val];
        top = max(top, f);
        group[f].push_back(val);
    }
    int pop() {
        int val = group[top].back();           // the most frequent, and the latest of those
        group[top].pop_back();
        freq[val] -= 1;
        if (group[top].empty()) top -= 1;
        return val;
    }
};
TIMEO(1) per callone map update and one stack move
SPACEO(n)every copy, once
TRAP

Moving a value between stacks. After push 7, 5, 7, 5, 5 the value 5 sits on stacks 1, 2 and 3. Pop its third copy and 5 and 7 have two each, with 5's second copy nearer the top of stack 2, so the next pop is 5 again. Taking 5 off the lower stacks at its third push would lose that.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
30 / MECHANISM UNIT 08 · FEWEST USES, THEN OLDEST

FEWEST USES, THEN OLDEST

Each key keeps its use count, and the keys with one count share a list, least recently used first. A use moves a key to the end of the next list; eviction takes the front of the lowest.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
31 / DRILL UNIT 08 · Fewest Uses, Then Oldest

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

LFUCache(2): put(1, 1), put(2, 2), get(2), put(3, 3), get(1), get(2). What do the gets return?

get(2) gives key 2 a second use. Key 1 has one, the fewest, so put(3, 3) evicts it, and key 2 stays.

DRILL 02 · RECALL

Why can low be set to 1 once a new key goes in?

Every key in the cache has been used at least once. The new key has exactly one use, so the fewest uses is 1, wherever low stood.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
32 / PROBLEM #11 · COUNT · HARD

LFU Cache

HARD count ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

A cache of fixed capacity that evicts the least frequently used key, and the least recently used among those.

INTUITION

LRU kept one list in order of use. LFU keeps one such list per use count, so bucket c holds the keys used c times, oldest first. A get or a put on a key moves it from bucket c to the back of bucket c + 1. Evicting takes the front of the lowest bucket, low. low only rises when a key leaves the bucket at low and empties it, and it is 1 after every new key.

STEPS
  1. kv maps key → (value, uses), and used[c] lists the keys used c times, oldest first
  2. A touch moves the key from used[c] to the back of used[c + 1], and low rises if used[low] empties
  3. get returns −1 for a missing key, else touches it and returns the value
  4. A new key evicts the front of used[low] when full, goes in with 1 use, and sets low to 1
BRUTEO(capacity) per eviction, scanning every key for the fewest uses and the oldest time
→
OPTIMALO(1) average per call
↕ SCROLL
class LFUCache {
    int cap, low = 0;                          // low: the fewest uses of any key
    unordered_map<int, pair<int, int>> kv;     // key -> (value, uses)
    unordered_map<int, list<int>> used;        // uses -> the keys with that many, oldest first
    unordered_map<int, list<int>::iterator> at;   // key -> its node in used
public:
    LFUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        if (!kv.count(key)) return -1;
        int c = kv[key].second++;              // one more use: move it up a bucket
        used[c].erase(at[key]);
        if (used[c].empty() && low == c) low++;
        at[key] = used[c + 1].insert(used[c + 1].end(), key);
        return kv[key].first;
    }
    void put(int key, int value) {
        if (get(key) != -1) { kv[key].first = value; return; }   // there already: get() used it
        if ((int)kv.size() == cap) {           // evict the oldest of the least used
            int old = used[low].front();
            kv.erase(old);
            at.erase(old);
            used[low].pop_front();
        }
        kv[key] = {value, 1};
        at[key] = used[1].insert(used[1].end(), key);
        low = 1;
    }
};
TIMEO(1) average per calla few map and list operations
SPACEO(capacity)the keys held
TRAP

Leaving low on an empty bucket. If the only key used once is read, bucket 1 is empty and low must become 2. Without that, the next eviction looks for the oldest key in an empty bucket.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
33 / MECHANISM UNIT 09 · COUNTS IN A LINKED LIST

COUNTS IN A LINKED LIST

Keys sit in buckets by count, and the buckets form a list in rising order. inc and dec move a key one bucket over, so the two ends of the list are the max and the min.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
34 / DRILL UNIT 09 · Counts in a Linked List

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

inc("x"), inc("y"), inc("y"), dec("x"), getMinKey()?

dec takes x from 1 to 0, which removes it. y alone is left, at count 2, so it is the min and the max.

DRILL 02 · RECALL

Why does inc never search for the bucket a key moves to?

A count changes by one, so the target is the neighbour in the list or a bucket inserted beside it. The map from key to bucket gives the starting point.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
35 / PROBLEM #12 · COUNT · HARD

All O`one Data Structure

HARD count ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Count strings with inc and dec, and return a key with the largest or the smallest count, each in O(1).

INTUITION

A count changes by one at a time, so a key only ever moves to the next count up or down. Keep one bucket per count in use, as a doubly linked list in rising order. Each bucket holds the keys with that count, and a map gives each key its bucket. inc moves the key to the next bucket, making a new bucket if count + 1 is missing; dec moves it back. An empty bucket is unlinked. The smallest count is the first bucket and the largest the last.

STEPS
  1. Buckets of (count, keys) in a doubly linked list, counts rising
  2. inc moves the key to the bucket for count + 1, inserting that bucket after this one if missing
  3. dec moves it to count − 1, or drops it at 0, and a bucket that empties is unlinked
  4. getMinKey reads any key of the first bucket, and getMaxKey any key of the last
BRUTEO(n) per getMaxKey and getMinKey, scanning a map of counts
→
OPTIMALO(1) average per call
↕ SCROLL
class AllOne {
    struct Bucket { int cnt; unordered_set<string> keys; };
    list<Bucket> b;                            // one bucket per count in use, counts rising
    unordered_map<string, list<Bucket>::iterator> at;   // key -> its bucket
public:
    AllOne() {}
    void inc(string key) {
        if (!at.count(key)) {                  // a new key: count 1, at the front
            if (b.empty() || b.front().cnt != 1) b.push_front(Bucket{1, {}});
            b.front().keys.insert(key);
            at[key] = b.begin();
            return;
        }
        auto cur = at[key], nxt = next(cur);
        if (nxt == b.end() || nxt->cnt != cur->cnt + 1)
            nxt = b.insert(nxt, Bucket{cur->cnt + 1, {}});   // count + 1 is missing
        nxt->keys.insert(key);
        at[key] = nxt;
        cur->keys.erase(key);
        if (cur->keys.empty()) b.erase(cur);   // an empty bucket leaves the list
    }
    void dec(string key) {
        auto cur = at[key];
        if (cur->cnt == 1) at.erase(key);      // count 0: the key goes
        else {
            bool fits = cur != b.begin() && prev(cur)->cnt == cur->cnt - 1;
            auto prv = fits ? prev(cur) : b.insert(cur, Bucket{cur->cnt - 1, {}});
            prv->keys.insert(key);
            at[key] = prv;
        }
        cur->keys.erase(key);
        if (cur->keys.empty()) b.erase(cur);
    }
    string getMaxKey() { return b.empty() ? "" : *b.back().keys.begin(); }
    string getMinKey() { return b.empty() ? "" : *b.front().keys.begin(); }
};
TIMEO(1) average per calla few pointer and set operations
SPACEO(n)the keys and buckets
TRAP

Keeping empty buckets. If a bucket stays linked after its last key moves on, getMinKey reads a bucket with no keys. Unlink a bucket the moment it empties.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
36 / MECHANISM UNIT 10 · DELETE IT WHEN IT SURFACES

DELETE IT WHEN IT SURFACES

A correction leaves the old price inside both heaps, where nothing can find it cheaply. The heaps keep every pair, and a top whose price no longer matches its timestamp is popped.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
37 / DRILL UNIT 10 · Delete It When It Surfaces

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

update(3, 8), update(1, 5), update(3, 2), then current(), maximum(), minimum()?

Timestamp 3 is corrected from 8 to 2 and is the latest, so current is 2. The pair (8, 3) is stale and is popped from the max-heap, which leaves 5.

DRILL 02 · RECALL

Why is lazy deletion still fast over a whole run of calls?

Every update pushes one pair to each heap, and a pop removes one for good. Over all the calls there are no more pops than pushes.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
38 / PROBLEM #13 · HEAP · MED

Stock Price Fluctuation

MED heap ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Price records arrive out of order, and a later record can correct an earlier one. Report the latest, the highest and the lowest price.

INTUITION

A map from timestamp to price handles corrections and the latest price. For the highest and the lowest, push every record into a max-heap and a min-heap as (price, timestamp). A correction cannot reach inside a heap, so the old pair stays there, stale. It only matters when it reaches the top. At that point compare it with the map; if the price no longer matches, pop it and look again.

STEPS
  1. price maps a timestamp to its latest price, and last is the largest timestamp
  2. update writes the map and pushes (price, timestamp) into both heaps
  3. maximum pops the top while its price is not price[its timestamp]
  4. The top is then live; minimum is the same on the min-heap
BRUTEO(n) per maximum and minimum, scanning the map
→
OPTIMALO(log n) amortised per call
↕ SCROLL
class StockPrice {
    unordered_map<int, int> price;             // timestamp -> its latest price
    int last = 0;                              // the latest timestamp
    priority_queue<pair<int, int>> hi;         // (price, timestamp), stale ones included
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> lo;
public:
    StockPrice() {}
    void update(int timestamp, int price_) {
        price[timestamp] = price_;
        last = max(last, timestamp);
        hi.push({price_, timestamp});
        lo.push({price_, timestamp});
    }
    int current() { return price[last]; }
    int maximum() {
        while (hi.top().first != price[hi.top().second]) hi.pop();   // corrected since: drop it now
        return hi.top().first;
    }
    int minimum() {
        while (lo.top().first != price[lo.top().second]) lo.pop();
        return lo.top().first;
    }
};
TIMEO(log n) amortised per callevery stale pair is popped once
SPACEO(n)the records, twice
TRAP

Trusting the top of the heap. After update(1, 10) and update(1, 3), the max-heap still holds (10, 1). maximum() must see that timestamp 1 now says 3, pop the pair, and read the next one.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
39 / MECHANISM UNIT 11 · MERGE THE NEWEST OF EACH

MERGE THE NEWEST OF EACH

Each user's tweets are already in time order. The feed puts every user's newest tweet in a max-heap, pops the newest, and pushes that user's next one, ten times at most.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
40 / DRILL UNIT 11 · Merge the Newest of Each

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

postTweet(1, 7), postTweet(2, 8), follow(1, 2), postTweet(1, 9), unfollow(1, 2), getNewsFeed(1)?

After the unfollow, user 1's feed holds only user 1's own tweets, newest first. Tweet 8 left with user 2.

DRILL 02 · RECALL

Why does the heap hold one tweet per user, not all of them?

A user's tweets are in time order, so the next one cannot beat the one just popped. It can wait until then, and the heap stays the size of the followee list plus one.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
41 / PROBLEM #14 · HEAP · MED

Design Twitter

MED heap ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

Users post, follow and unfollow. A feed is the 10 most recent tweets by the user and everyone they follow, newest first.

INTUITION

Each user's tweets are already in time order, since a global clock stamps every post. A feed merges k sorted lists and stops after 10, which is unit 6 of the heaps deck. Push the newest tweet of each followed user and of the user, pop the newest of all, and push that user's next newest in its place. Ten pops and the feed is done, however many tweets the users have.

STEPS
  1. A clock stamps every tweet; tweets[u] keeps u's in time order
  2. Push the newest tweet of the user and of each followee into a max-heap
  3. Pop the newest; push the next newest of the same user
  4. Stop after 10 or when the heap is empty
BRUTEO(T log T) per feed, sorting every tweet of everyone followed
→
OPTIMALO(f + 10 log f) per feed
↕ SCROLL
class Twitter {
    int clock = 0;
    unordered_map<int, vector<pair<int, int>>> tweets;   // user -> (time, tweetId), oldest first
    unordered_map<int, unordered_set<int>> follows;
public:
    Twitter() {}
    void postTweet(int userId, int tweetId) { tweets[userId].push_back({++clock, tweetId}); }
    vector<int> getNewsFeed(int userId) {
        priority_queue<array<int, 3>> pq;      // (time, user, index): each user's newest unread
        auto add = [&](int u, int i) {         // user u's tweet i, if there is one
            if (i >= 0) pq.push({tweets[u][i].first, u, i});
        };
        add(userId, (int)tweets[userId].size() - 1);
        for (int u : follows[userId]) add(u, (int)tweets[u].size() - 1);
        vector<int> feed;
        while (!pq.empty() && feed.size() < 10) {
            array<int, 3> t = pq.top(); pq.pop();
            feed.push_back(tweets[t[1]][t[2]].second);
            add(t[1], t[2] - 1);               // that user's next newest goes in
        }
        return feed;
    }
    void follow(int followerId, int followeeId) { follows[followerId].insert(followeeId); }
    void unfollow(int followerId, int followeeId) { follows[followerId].erase(followeeId); }
};
TIMEO(f + 10 log f) per feedf followees, 10 pops
SPACEO(users + tweets)every tweet and follow
TRAP

A feed without the user's own tweets. The feed holds tweets by the people the user follows and by the user. Merging only the followees drops every tweet of their own.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
42 / MECHANISM UNIT 12 · A STACK OF OPEN LISTS

A STACK OF OPEN LISTS

The iterator keeps a stack of the lists it has opened, each with the next index to read. hasNext pops lists that are used up and steps into lists it meets, until the top is an integer.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
43 / DRILL UNIT 12 · A Stack of Open Lists

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

A NestedIterator on [[], [[3]], 4]. What do the next() calls return?

The empty list is opened and popped at once. [[3]] is stepped into twice to reach 3, both are popped after it, and 4 is read from the outer list.

DRILL 02 · RECALL

Why does hasNext do the stepping, not next?

In [1, [[]]], after 1 the iterator still holds a list with an empty list inside. hasNext must open both to answer false, and next then knows the top is an integer.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
44 / PROBLEM #15 · STACK · MED

Flatten Nested List Iterator

MED stack ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

An iterator over a nested list of integers that returns them in order, flattened.

INTUITION

Flattening everything up front works, but an iterator should do only the work each call needs. Keep a stack of the lists still open, each with the next position to read. hasNext() settles the top. A list that is used up is popped, and an inner list is stepped into by pushing it. It stops when the top sits on an integer, which next() then returns. Calling hasNext() twice does nothing the second time.

STEPS
  1. A stack of (list, next position), starting with the whole list
  2. hasNext pops a list that is used up
  3. On an inner list, hasNext moves past it and pushes it with position 0
  4. Stop on an integer; next() returns it and moves past it
BRUTEO(n) up front, flattening the whole list into an array
→
OPTIMALO(1) amortised per call
↕ SCROLL
class NestedIterator {
    using List = vector<NestedInteger>;
    vector<pair<const List*, int>> st;         // each open list, the next position in it
public:
    NestedIterator(List& nestedList) { st.push_back({&nestedList, 0}); }
    bool hasNext() {
        while (!st.empty()) {
            const List& l = *st.back().first;
            int& i = st.back().second;
            if (i == (int)l.size()) st.pop_back();          // this list is used up
            else if (l[i].isInteger()) return true;
            else st.push_back({&l[i++].getList(), 0});     // step past it, and into it
        }
        return false;
    }
    int next() {
        hasNext();                             // the top now sits on an integer
        return (*st.back().first)[st.back().second++].getInteger();
    }
};
TIMEO(1) amortised per calleach list is pushed and popped once
SPACEO(depth)one frame per open list
TRAP

An empty inner list. On [[], 3] a hasNext() that only checks whether the stack is empty says true at the start, and so it does on [[]], which holds no integer at all. hasNext() must step through the lists until it sits on an integer.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
45 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH DESIGN, AND WHAT GIVES IT AWAY

Twelve designs, and each has a phrase in the statement that gives it away.

SMALL LIMITS AND ONE ARRAY OF STATE

store the state as it is and scan it on each call

PLAIN ARRAYO(n) a call
A KEY-VALUE STORE WITHOUT A LIBRARY MAP

key % B picks a bucket, and each bucket is a short chain

BUCKETS AND CHAINSO(n / B)
INSERT, DELETE AND A UNIFORM RANDOM PICK

an array and a value-to-index map; the last fills a hole

SWAP WITH THE LASTO(1)
BACK AND FORWARD AROUND ONE CURSOR

one stack behind the cursor and one stack ahead of it

TWO STACKSO(steps)
READ A VALUE AS IT WAS AT AN EARLIER TIME

(version, value) pairs per index and a binary search

VERSIONS PER INDEXO(log s)
ITEMS THAT EXPIRE A FIXED TIME AFTER A CALL

a list in expiry order and a map into the list

EXPIRY ORDERO(1) amortised
POP THE MOST FREQUENT, THE LATEST ON A TIE

the k-th copy of a value goes on stack k

STACK PER FREQUENCYO(1)
EVICT THE LEAST USED, THE OLDEST ON A TIE

a list per use count, oldest first, and the lowest count

LIST PER COUNTO(1)
MAX AND MIN KEY AS COUNTS MOVE BY ONE

buckets by count in a linked list; a key moves next door

BUCKET LISTO(1)
A MAX OR MIN WHILE OLD VALUES ARE CORRECTED

the heaps keep stale pairs; pop a top that no longer matches

LAZY DELETIONO(log n) amortised
THE NEWEST TEN ACROSS MANY SORTED LISTS

a max-heap of each list's newest; pop it, push its next

K-WAY MERGEO(f log f)
WALK A NESTED LIST ONE ITEM AT A TIME

a stack of open lists, each with the next index to read

STACK OF ITERATORSO(1) amortised
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
46 / RECALL RETRIEVAL, NOT RECOGNITION · 1 OF 2

NAME THE DESIGN FROM THE STATEMENT

DRILL 01 · TRANSFER

LRU Cache: get and put in O(1), and a full cache evicts the key used least recently. Which move?

A use moves the key to the back of one list, and eviction takes the front. It is unit 6's renew, with a use in place of a renewal, or LFU with a single count. The problem is LRU Cache (linked-list-3).

DRILL 02 · TRANSFER

Time Based Key-Value Store: set(key, value, t) with t rising, and get(key, t) returns the value set last at or before t. Which move?

Each key keeps its (time, value) pairs, sorted already because the times rise, and get is an upper bound and a step back. It is Snapshot Array with a key in place of an index, and it sits in module 9.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
47 / RECALL RETRIEVAL, NOT RECOGNITION · 2 OF 2

NAME THE DESIGN FROM THE STATEMENT

DRILL 01 · TRANSFER

Number Container System: change(index, number) overwrites a slot, and find(number) returns the smallest index holding that number. Which move?

Keep index to number, and a min-heap of indices for each number. A change leaves the old index in its old heap, and find pops tops that now hold another number, as Stock Price does.

DRILL 02 · RECALL

Insert Delete GetRandom keeps an array beside the map. Why is the map alone not enough?

A hash map has no slot numbers to draw from. The array gives the values slots 0 to n − 1, so a random slot is a random value, and the map keeps every slot findable.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
48 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

None of these fail the samples. Each one fails a hidden test.

ONE FIELD UPDATED, ITS PARTNER NOT

Each design keeps two or three fields in step, such as an array and its index map, or a list and the map of its nodes. A call that updates one and not the other passes the samples and fails the first test that reads the stale one.

ERASING FROM THE MIDDLE OF A VECTOR

vector::erase shifts everything after the hole, O(n) a call. Where order does not matter, move the last item into the hole. Where it does, keep a list and a map to its nodes.

THE ITEM REMOVED IS THE ITEM MOVED

In both GetRandom problems and the HashMap's remove, the item removed can be the last one, which is the one being moved. Order the updates so that case cancels out, and try it with one item.

A TIE BROKEN THE WRONG WAY

Frequency Stack breaks ties by the latest push, LFU by the least recent use, and All O`one takes any key. Read which before choosing the order inside a bucket.

A SCAN WHERE A STRUCTURE WAS ASKED FOR

A min over the whole map, a search for the oldest key or a sort of every tweet passes the samples. LFU Cache makes 2 × 10⁵ calls, and an O(n) call there times out.

A MAP ENTRY THAT OUTLIVES ITS ITEM

When a token expires or a key is evicted, erase its map entry as well. A stale entry makes a missing item look present, and its iterator points at a node that is gone.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
49 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Twelve designs on one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Plain array
O(n) a call
O(n)
scan for a free run; fill it, or clear by mID
Buckets and chains
O(n / B)
O(n + B)
b[key % B]: update, append, or swap out
Swap with the last
O(1)
O(n)
a[i] = last, pos[last] = i, pop, erase val
Two stacks
O(steps)
O(n)
back moves past to ahead; a visit clears ahead
Versions per index
O(log s) a get
O(n + sets)
upper_bound(s, ∞), then one step back
Expiry order
O(1) amortised
O(n)
drop the front while expiry ≤ now
Stack per frequency
O(1)
O(n)
push on stack ++freq; pop the top stack
List per count
O(1)
O(cap)
a use moves it to count + 1; evict low's front
Bucket list
O(1)
O(n)
move to the bucket next door; unlink an empty one
Lazy deletion
O(log n) amortised
O(updates)
pop the top while price[t] ≠ p
K-way merge
O(f log f)
O(f)
push each newest; pop, push that user's next
Stack of iterators
O(1) amortised
O(depth)
pop used-up lists, step in, stop at an integer
INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
50 / CLOSE MODULE 27 · DESIGN

TAKE IT NOW

The allocator and the bank were arrays and nothing more; a prime number of buckets held the chains; the last value filled each hole; two stacks sat either side of a cursor; each index kept its versions; tokens queued in expiry order; each frequency got its own stack; keys moved between lists by use count, and between buckets by count; stale prices waited in the heaps until they surfaced; the feed merged the newest tweet of each user; and a stack of open lists flattened the nesting. LRU Cache, the same list and map with one count, is in linked-list-3.

00%
OF THIS DECK SOLVED
← ALL TOPICS← STACKS AND QUEUES← HEAPS

Module 27. Fifteen problems, all on LeetCode. Next in the sheet: maths and modular arithmetic.

INVARIANT · DESIGN · PICK THE FIELDS, THEN EVERY CALL IS CHEAP · DESIGN
■ TOO SMALL TO READ
1280×720
INVARIANT · MODULE 27 · DESIGN

This one needs a laptop

Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.

Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.