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.
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.
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.
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.
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.
Memory is n units. Allocate the leftmost run of size free units to an id, or free every unit that id holds.
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.
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; } };
class Allocator { private final int[] mem; // the mID in each unit, 0 if free public Allocator(int n) { mem = new int[n]; } public int allocate(int size, int mID) { int run = 0; // free units in a row, ending at i for (int i = 0; i < mem.length; i++) { run = mem[i] != 0 ? 0 : run + 1; if (run == size) { // the leftmost block that fits Arrays.fill(mem, i - size + 1, i + 1, mID); return i - size + 1; } } return -1; } public int freeMemory(int mID) { int cnt = 0; for (int i = 0; i < mem.length; i++) if (mem[i] == mID) { mem[i] = 0; cnt++; } return cnt; } }
class Allocator: def __init__(self, n): self.mem = [0] * n # the mID in each unit, 0 if free def allocate(self, size, mID): run = 0 # free units in a row, ending at i for i, x in enumerate(self.mem): run = 0 if x else run + 1 if run == size: # the leftmost block that fits self.mem[i - size + 1:i + 1] = [mID] * size return i - size + 1 return -1 def freeMemory(self, mID): cnt = 0 for i, x in enumerate(self.mem): if x == mID: self.mem[i] = 0 cnt += 1 return cnt
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.
Accounts 1 to n hold balances. Run each transfer, deposit or withdrawal only if its accounts exist and the money is there.
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.
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; } };
class Bank { private final long[] bal; // account a is bal[a - 1] public Bank(long[] balance) { bal = balance; } private boolean ok(int a) { return a >= 1 && a <= bal.length; } public boolean transfer(int account1, int account2, 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; } public boolean deposit(int account, long money) { if (!ok(account)) return false; bal[account - 1] += money; return true; } public boolean withdraw(int account, long money) { if (!ok(account) || bal[account - 1] < money) return false; bal[account - 1] -= money; return true; } }
class Bank: def __init__(self, balance): self.bal = balance # account a is bal[a - 1] def ok(self, a): return 1 <= a <= len(self.bal) def transfer(self, account1, account2, money): if not self.ok(account1) or not self.ok(account2) or self.bal[account1 - 1] < money: return False # check everything before changing anything self.bal[account1 - 1] -= money self.bal[account2 - 1] += money return True def deposit(self, account, money): if not self.ok(account): return False self.bal[account - 1] += money return True def withdraw(self, account, money): if not self.ok(account) or self.bal[account - 1] < money: return False self.bal[account - 1] -= money return True
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.
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.
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.
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.
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.
Build put, get and remove for integer keys without a built-in hash table.
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.
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; } } };
class MyHashMap { private static final int B = 1009; // a prime number of buckets private final List<int[]>[] b = new List[B]; // bucket h: the {key, value} pairs with key % B == h public MyHashMap() { for (int h = 0; h < B; h++) b[h] = new ArrayList<>(); } public void put(int key, int value) { for (int[] p : b[key % B]) if (p[0] == key) { p[1] = value; return; } // already there: update it b[key % B].add(new int[]{key, value}); } public int get(int key) { for (int[] p : b[key % B]) if (p[0] == key) return p[1]; return -1; } public void remove(int key) { List<int[]> ch = b[key % B]; for (int i = 0; i < ch.size(); i++) if (ch.get(i)[0] == key) { ch.set(i, ch.get(ch.size() - 1)); // the last pair fills the hole ch.remove(ch.size() - 1); return; } } }
class MyHashMap: B = 1009 # a prime number of buckets def __init__(self): self.b = [[] for _ in range(self.B)] # bucket h: the [key, value] pairs with key % B == h def put(self, key, value): ch = self.b[key % self.B] for p in ch: if p[0] == key: # already there: update it p[1] = value return ch.append([key, value]) def get(self, key): for k, v in self.b[key % self.B]: if k == key: return v return -1 def remove(self, key): ch = self.b[key % self.B] for i, p in enumerate(ch): if p[0] == key: ch[i] = ch[-1] # the last pair fills the hole ch.pop() return
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.
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.
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.
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).
A set with insert, remove and getRandom, each in O(1), every element equally likely.
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.
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()]; } };
class RandomizedSet { private final List<Integer> a = new ArrayList<>(); // the values, in no order private final Map<Integer, Integer> pos = new HashMap<>(); // value -> its index in a private final Random rnd = new Random(); public RandomizedSet() {} public boolean insert(int val) { if (pos.containsKey(val)) return false; pos.put(val, a.size()); a.add(val); return true; } public boolean remove(int val) { if (!pos.containsKey(val)) return false; int i = pos.get(val), last = a.get(a.size() - 1); a.set(i, last); // the last value fills the hole pos.put(last, i); a.remove(a.size() - 1); pos.remove(val); return true; } public int getRandom() { return a.get(rnd.nextInt(a.size())); } }
import random class RandomizedSet: def __init__(self): self.a = [] # the values, in no order self.pos = {} # value -> its index in a def insert(self, val): if val in self.pos: return False self.pos[val] = len(self.a) self.a.append(val) return True def remove(self, val): if val not in self.pos: return False i, last = self.pos[val], self.a[-1] self.a[i] = last # the last value fills the hole self.pos[last] = i self.a.pop() del self.pos[val] return True def getRandom(self): return random.choice(self.a)
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.
The same with duplicates: insert says whether the value was new, remove takes one copy, and getRandom weighs each value by its copies.
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.
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()]; } };
class RandomizedCollection { private final List<Integer> a = new ArrayList<>(); // every copy, in no order private final Map<Integer, Set<Integer>> idx = new HashMap<>(); // value -> the indices holding it private final Random rnd = new Random(); public RandomizedCollection() {} public boolean insert(int val) { idx.computeIfAbsent(val, x -> new HashSet<>()).add(a.size()); a.add(val); return idx.get(val).size() == 1; } public boolean remove(int val) { Set<Integer> s = idx.get(val); if (s == null || s.isEmpty()) return false; int i = s.iterator().next(), last = a.get(a.size() - 1); // any copy; the last copy fills it s.remove(i); a.set(i, last); idx.get(last).add(i); // add the hole first, idx.get(last).remove(a.size() - 1); // then drop the old last index a.remove(a.size() - 1); return true; } public int getRandom() { return a.get(rnd.nextInt(a.size())); } }
import random from collections import defaultdict class RandomizedCollection: def __init__(self): self.a = [] # every copy, in no order self.idx = defaultdict(set) # value -> the indices holding it def insert(self, val): self.idx[val].add(len(self.a)) self.a.append(val) return len(self.idx[val]) == 1 def remove(self, val): if not self.idx[val]: return False i, last = self.idx[val].pop(), self.a[-1] # any copy of val; the last copy fills it self.a[i] = last self.idx[last].add(i) # add the hole first, self.idx[last].discard(len(self.a) - 1) # then drop the old last index self.a.pop() return True def getRandom(self): return random.choice(self.a)
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.
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.
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.
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.
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.
One tab: visit a page, go back or forward up to steps pages, and return the page on screen.
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.
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(); } };
class BrowserHistory { private final Deque<String> past = new ArrayDeque<>(); // its top is the page on screen private final Deque<String> ahead = new ArrayDeque<>(); // forward() pages, nearest on top public BrowserHistory(String homepage) { past.push(homepage); } public void visit(String url) { past.push(url); ahead.clear(); // a new page ends the forward history } public String back(int steps) { for (; steps > 0 && past.size() > 1; steps -= 1) ahead.push(past.pop()); return past.peek(); } public String forward(int steps) { for (; steps > 0 && !ahead.isEmpty(); steps -= 1) past.push(ahead.pop()); return past.peek(); } }
class BrowserHistory: def __init__(self, homepage): self.past = [homepage] # its top is the page on screen self.ahead = [] # the pages forward() can reach, nearest on top def visit(self, url): self.past.append(url) self.ahead.clear() # a new page ends the forward history def back(self, steps): while steps > 0 and len(self.past) > 1: self.ahead.append(self.past.pop()) steps -= 1 return self.past[-1] def forward(self, steps): while steps > 0 and self.ahead: self.past.append(self.ahead.pop()) steps -= 1 return self.past[-1]
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.
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.
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.
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(); } };
class TextEditor { private final StringBuilder left = new StringBuilder(); // the characters before the cursor private final StringBuilder right = new StringBuilder(); // those after it, nearest at the end public TextEditor() {} private String tail() { return left.substring(Math.max(0, left.length() - 10)); } public void addText(String text) { left.append(text); } public int deleteText(int k) { k = Math.min(k, left.length()); // only what is there can be deleted left.setLength(left.length() - k); return k; } public String cursorLeft(int k) { for (; k > 0 && left.length() > 0; k -= 1) { right.append(left.charAt(left.length() - 1)); left.setLength(left.length() - 1); } return tail(); } public String cursorRight(int k) { for (; k > 0 && right.length() > 0; k -= 1) { left.append(right.charAt(right.length() - 1)); right.setLength(right.length() - 1); } return tail(); } }
class TextEditor: def __init__(self): self.left = [] # the characters before the cursor self.right = [] # those after it, nearest on top def addText(self, text): self.left.extend(text) def deleteText(self, k): k = min(k, len(self.left)) # only what is there can be deleted del self.left[len(self.left) - k:] return k def cursorLeft(self, k): while k > 0 and self.left: self.right.append(self.left.pop()) k -= 1 return "".join(self.left[-10:]) def cursorRight(self, k): while k > 0 and self.right: self.left.append(self.right.pop()) k -= 1 return "".join(self.left[-10:])
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.
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.
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.
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.
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.
An array whose snap() freezes a version; get(index, snap_id) reads index as it was then.
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.
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 } };
class SnapshotArray { private final List<int[]>[] h; // index i: {snap id, value} at each change private int snapId = 0; public SnapshotArray(int length) { h = new List[length]; for (int i = 0; i < length; i++) { h[i] = new ArrayList<>(); h[i].add(new int[]{0, 0}); } } public void set(int index, int val) { List<int[]> v = h[index]; int[] last = v.get(v.size() - 1); if (last[0] == snapId) last[1] = val; // changed already in this snap else v.add(new int[]{snapId, val}); } public int snap() { return snapId++; } public int get(int index, int snap_id) { List<int[]> v = h[index]; int lo = 0, hi = v.size() - 1; // the last change at or before snap_id while (lo < hi) { int mid = (lo + hi + 1) / 2; if (v.get(mid)[0] <= snap_id) lo = mid; else hi = mid - 1; } return v.get(lo)[1]; } }
import bisect class SnapshotArray: def __init__(self, length): self.ids = [[0] for _ in range(length)] # index i: the snap ids where it changed self.vals = [[0] for _ in range(length)] # and its value from each one on self.snap_id = 0 def set(self, index, val): if self.ids[index][-1] == self.snap_id: # changed already in this snap self.vals[index][-1] = val else: self.ids[index].append(self.snap_id) self.vals[index].append(val) def snap(self): self.snap_id += 1 return self.snap_id - 1 def get(self, index, snap_id): j = bisect.bisect_right(self.ids[index], snap_id) - 1 # the last change at or before it return self.vals[index][j]
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.
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.
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.
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.
Tokens expire timeToLive seconds after they are generated or renewed. Count the live ones; the times only grow.
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.
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(); } };
class AuthenticationManager { private final int ttl; private final LinkedHashMap<String, Integer> exp = new LinkedHashMap<>(); // token -> expiry, soonest first public AuthenticationManager(int timeToLive) { ttl = timeToLive; } private void drop(int t) { Iterator<Map.Entry<String, Integer>> it = exp.entrySet().iterator(); while (it.hasNext() && it.next().getValue() <= t) it.remove(); // expired by t: it leaves the front } public void generate(String tokenId, int currentTime) { drop(currentTime); exp.put(tokenId, currentTime + ttl); // the times grow, so it goes last } public void renew(String tokenId, int currentTime) { drop(currentTime); if (exp.remove(tokenId) != null) // live: put it back at the end exp.put(tokenId, currentTime + ttl); } public int countUnexpiredTokens(int currentTime) { drop(currentTime); return exp.size(); } }
from collections import OrderedDict class AuthenticationManager: def __init__(self, timeToLive): self.ttl = timeToLive self.exp = OrderedDict() # token -> expiry, the soonest first def drop(self, t): while self.exp and next(iter(self.exp.values())) <= t: self.exp.popitem(last=False) # expired by t: it leaves the front def generate(self, tokenId, currentTime): self.drop(currentTime) self.exp[tokenId] = currentTime + self.ttl # the times grow, so it goes last def renew(self, tokenId, currentTime): self.drop(currentTime) if tokenId in self.exp: # live: move it to the back self.exp.move_to_end(tokenId) self.exp[tokenId] = currentTime + self.ttl def countUnexpiredTokens(self, currentTime): self.drop(currentTime) return len(self.exp)
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.
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.
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.
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.
A stack whose pop removes the most frequent value, the one nearest the top among ties.
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.
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; } };
class FreqStack { private final Map<Integer, Integer> freq = new HashMap<>(); // value -> its copies private final Map<Integer, Deque<Integer>> group = new HashMap<>(); // f -> values whose f-th copy came in private int top = 0; // the highest frequency held public FreqStack() {} public void push(int val) { int f = freq.merge(val, 1, Integer::sum); top = Math.max(top, f); group.computeIfAbsent(f, x -> new ArrayDeque<>()).push(val); } public int pop() { int val = group.get(top).pop(); // the most frequent, and the latest of those freq.merge(val, -1, Integer::sum); if (group.get(top).isEmpty()) top -= 1; return val; } }
from collections import defaultdict class FreqStack: def __init__(self): self.freq = defaultdict(int) # value -> its copies in the stack self.group = defaultdict(list) # f -> the values whose f-th copy came in, in order self.top = 0 # the highest frequency held def push(self, val): self.freq[val] += 1 f = self.freq[val] self.top = max(self.top, f) self.group[f].append(val) def pop(self): val = self.group[self.top].pop() # the most frequent, and the latest of those self.freq[val] -= 1 if not self.group[self.top]: self.top -= 1 return val
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.
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.
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.
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.
A cache of fixed capacity that evicts the least frequently used key, and the least recently used among those.
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.
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; } };
class LFUCache { private final int cap; private int low = 0; // the fewest uses of any key private final Map<Integer, int[]> kv = new HashMap<>(); // key -> {value, uses} private final Map<Integer, LinkedHashSet<Integer>> used = new HashMap<>(); // uses -> keys, oldest first public LFUCache(int capacity) { cap = capacity; } public int get(int key) { if (!kv.containsKey(key)) return -1; int c = kv.get(key)[1]++; // one more use: move it up a bucket used.get(c).remove(key); if (used.get(c).isEmpty() && low == c) low++; used.computeIfAbsent(c + 1, x -> new LinkedHashSet<>()).add(key); return kv.get(key)[0]; } public void put(int key, int value) { if (get(key) != -1) { kv.get(key)[0] = value; return; } // there already: get() used it if (kv.size() == cap) { // evict the oldest of the least used int old = used.get(low).iterator().next(); used.get(low).remove(old); kv.remove(old); } kv.put(key, new int[]{value, 1}); used.computeIfAbsent(1, x -> new LinkedHashSet<>()).add(key); low = 1; } }
from collections import defaultdict, OrderedDict class LFUCache: def __init__(self, capacity): self.cap = capacity self.val, self.cnt = {}, {} # key -> value, key -> uses self.used = defaultdict(OrderedDict) # uses -> the keys with that many, oldest first self.low = 0 # the fewest uses of any key def get(self, key): if key not in self.val: return -1 c = self.cnt[key] # one more use: move it up a bucket del self.used[c][key] if not self.used[c] and self.low == c: self.low += 1 self.cnt[key] = c + 1 self.used[c + 1][key] = None return self.val[key] def put(self, key, value): if self.get(key) != -1: # there already: get() counted the use self.val[key] = value return if len(self.val) == self.cap: # evict the oldest of the least used old, _ = self.used[self.low].popitem(last=False) del self.val[old], self.cnt[old] self.val[key], self.cnt[key] = value, 1 self.used[1][key] = None self.low = 1
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.
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.
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.
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.
Count strings with inc and dec, and return a key with the largest or the smallest count, each in O(1).
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.
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(); } };
class AllOne { private static class Node { int cnt; Set<String> keys = new HashSet<>(); Node prev, next; Node(int c) { cnt = c; } } private final Node head = new Node(0), tail = new Node(0); // sentinels; counts rise head to tail private final Map<String, Node> at = new HashMap<>(); // key -> its bucket public AllOne() { head.next = tail; tail.prev = head; } private Node after(Node nd, int cnt) { // a new bucket for cnt, right after nd Node x = new Node(cnt); x.prev = nd; x.next = nd.next; nd.next.prev = x; nd.next = x; return x; } private void drop(Node nd, String key) { // take key out; an empty bucket leaves the list nd.keys.remove(key); if (nd.keys.isEmpty()) { nd.prev.next = nd.next; nd.next.prev = nd.prev; } } public void inc(String key) { Node nd = at.getOrDefault(key, head), nxt = nd.next; if (nxt.cnt != nd.cnt + 1) nxt = after(nd, nd.cnt + 1); nxt.keys.add(key); at.put(key, nxt); if (nd != head) drop(nd, key); } public void dec(String key) { Node nd = at.get(key); if (nd.cnt == 1) at.remove(key); // count 0: the key goes else { Node prv = nd.prev; if (prv.cnt != nd.cnt - 1) prv = after(prv, nd.cnt - 1); prv.keys.add(key); at.put(key, prv); } drop(nd, key); } public String getMaxKey() { return tail.prev == head ? "" : tail.prev.keys.iterator().next(); } public String getMinKey() { return head.next == tail ? "" : head.next.keys.iterator().next(); } }
class Node: def __init__(self, cnt): self.cnt, self.keys = cnt, set() self.prev = self.next = None class AllOne: def __init__(self): self.head, self.tail = Node(0), Node(0) # sentinels; counts rise from head to tail self.head.next, self.tail.prev = self.tail, self.head self.node = {} # key -> its bucket def after(self, nd, cnt): # a new bucket for cnt, right after nd x = Node(cnt) x.prev, x.next = nd, nd.next nd.next.prev = x nd.next = x return x def drop(self, nd, key): # take key out; an empty bucket leaves the list nd.keys.discard(key) if not nd.keys: nd.prev.next, nd.next.prev = nd.next, nd.prev def inc(self, key): nd = self.node.get(key, self.head) nxt = nd.next if nxt.cnt != nd.cnt + 1: nxt = self.after(nd, nd.cnt + 1) nxt.keys.add(key) self.node[key] = nxt if nd is not self.head: self.drop(nd, key) def dec(self, key): nd = self.node[key] if nd.cnt == 1: # count 0: the key goes del self.node[key] else: prv = nd.prev if prv.cnt != nd.cnt - 1: prv = self.after(prv, nd.cnt - 1) prv.keys.add(key) self.node[key] = prv self.drop(nd, key) def getMaxKey(self): # any key of the last bucket if self.tail.prev is self.head: return "" return next(iter(self.tail.prev.keys)) def getMinKey(self): # any key of the first bucket if self.head.next is self.tail: return "" return next(iter(self.head.next.keys))
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.
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.
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.
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.
Price records arrive out of order, and a later record can correct an earlier one. Report the latest, the highest and the lowest price.
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.
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; } };
class StockPrice { private final Map<Integer, Integer> price = new HashMap<>(); // timestamp -> its latest price private int last = 0; // the latest timestamp private final PriorityQueue<int[]> hi = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0])); private final PriorityQueue<int[]> lo = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); public StockPrice() {} public void update(int timestamp, int p) { price.put(timestamp, p); last = Math.max(last, timestamp); hi.add(new int[]{p, timestamp}); // {price, timestamp}, stale ones included lo.add(new int[]{p, timestamp}); } public int current() { return price.get(last); } public int maximum() { while (hi.peek()[0] != price.get(hi.peek()[1])) hi.poll(); // corrected since: drop it now return hi.peek()[0]; } public int minimum() { while (lo.peek()[0] != price.get(lo.peek()[1])) lo.poll(); return lo.peek()[0]; } }
import heapq class StockPrice: def __init__(self): self.price = {} # timestamp -> its latest price self.last = 0 # the latest timestamp self.hi, self.lo = [], [] # (-price, t) and (price, t), stale ones included def update(self, timestamp, price): self.price[timestamp] = price self.last = max(self.last, timestamp) heapq.heappush(self.hi, (-price, timestamp)) heapq.heappush(self.lo, (price, timestamp)) def current(self): return self.price[self.last] def maximum(self): while -self.hi[0][0] != self.price[self.hi[0][1]]: # corrected since: drop it now heapq.heappop(self.hi) return -self.hi[0][0] def minimum(self): while self.lo[0][0] != self.price[self.lo[0][1]]: heapq.heappop(self.lo) return self.lo[0][0]
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.
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.
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.
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.
Users post, follow and unfollow. A feed is the 10 most recent tweets by the user and everyone they follow, newest first.
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.
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); } };
class Twitter { private int clock = 0; private final Map<Integer, List<int[]>> tweets = new HashMap<>(); // user -> {time, tweetId}, oldest first private final Map<Integer, Set<Integer>> follows = new HashMap<>(); public Twitter() {} public void postTweet(int userId, int tweetId) { tweets.computeIfAbsent(userId, x -> new ArrayList<>()).add(new int[]{++clock, tweetId}); } public List<Integer> getNewsFeed(int userId) { PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(b[0], a[0])); // {time, user, index} Set<Integer> who = new HashSet<>(follows.getOrDefault(userId, Collections.emptySet())); who.add(userId); for (int u : who) { List<int[]> t = tweets.get(u); if (t != null && !t.isEmpty()) pq.add(new int[]{t.get(t.size() - 1)[0], u, t.size() - 1}); } List<Integer> feed = new ArrayList<>(); while (!pq.isEmpty() && feed.size() < 10) { int[] top = pq.poll(); List<int[]> t = tweets.get(top[1]); feed.add(t.get(top[2])[1]); if (top[2] > 0) pq.add(new int[]{t.get(top[2] - 1)[0], top[1], top[2] - 1}); // next newest } return feed; } public void follow(int followerId, int followeeId) { follows.computeIfAbsent(followerId, x -> new HashSet<>()).add(followeeId); } public void unfollow(int followerId, int followeeId) { Set<Integer> s = follows.get(followerId); if (s != null) s.remove(followeeId); } }
import heapq from collections import defaultdict class Twitter: def __init__(self): self.clock = 0 self.tweets = defaultdict(list) # user -> [(time, tweetId)], oldest first self.follows = defaultdict(set) def postTweet(self, userId, tweetId): self.clock += 1 self.tweets[userId].append((self.clock, tweetId)) def getNewsFeed(self, userId): heap = [] # (-time, user, index): each user's newest unread for u in self.follows[userId] | {userId}: if self.tweets[u]: i = len(self.tweets[u]) - 1 heap.append((-self.tweets[u][i][0], u, i)) heapq.heapify(heap) feed = [] while heap and len(feed) < 10: _, u, i = heapq.heappop(heap) feed.append(self.tweets[u][i][1]) if i > 0: # that user's next newest goes in heapq.heappush(heap, (-self.tweets[u][i - 1][0], u, i - 1)) return feed def follow(self, followerId, followeeId): self.follows[followerId].add(followeeId) def unfollow(self, followerId, followeeId): self.follows[followerId].discard(followeeId)
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.
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.
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.
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.
An iterator over a nested list of integers that returns them in order, flattened.
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.
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(); } };
public class NestedIterator implements Iterator<Integer> { private final Deque<Iterator<NestedInteger>> st = new ArrayDeque<>(); // each open list's iterator private Integer nxt = null; // an integer already read, waiting for next() public NestedIterator(List<NestedInteger> nestedList) { st.push(nestedList.iterator()); } @Override public boolean hasNext() { while (nxt == null && !st.isEmpty()) { if (!st.peek().hasNext()) st.pop(); // this list is used up else { NestedInteger x = st.peek().next(); if (x.isInteger()) nxt = x.getInteger(); else st.push(x.getList().iterator()); // step into the inner list } } return nxt != null; } @Override public Integer next() { hasNext(); // the read now waits in nxt Integer v = nxt; nxt = null; return v; } }
class NestedIterator: def __init__(self, nestedList): self.stack = [[nestedList, 0]] # each open list, the next position in it def hasNext(self): while self.stack: lst, i = self.stack[-1] if i == len(lst): # this list is used up self.stack.pop() elif lst[i].isInteger(): return True else: # step into the inner list self.stack[-1][1] += 1 self.stack.append([lst[i].getList(), 0]) return False def next(self): self.hasNext() # the top now sits on an integer lst, i = self.stack[-1] self.stack[-1][1] += 1 return lst[i].getInteger()
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.
Twelve designs, and each has a phrase in the statement that gives it away.
store the state as it is and scan it on each call
PLAIN ARRAYO(n) a callkey % B picks a bucket, and each bucket is a short chain
BUCKETS AND CHAINSO(n / B)an array and a value-to-index map; the last fills a hole
SWAP WITH THE LASTO(1)one stack behind the cursor and one stack ahead of it
TWO STACKSO(steps)(version, value) pairs per index and a binary search
VERSIONS PER INDEXO(log s)a list in expiry order and a map into the list
EXPIRY ORDERO(1) amortisedthe k-th copy of a value goes on stack k
STACK PER FREQUENCYO(1)a list per use count, oldest first, and the lowest count
LIST PER COUNTO(1)buckets by count in a linked list; a key moves next door
BUCKET LISTO(1)the heaps keep stale pairs; pop a top that no longer matches
LAZY DELETIONO(log n) amortiseda max-heap of each list's newest; pop it, push its next
K-WAY MERGEO(f log f)a stack of open lists, each with the next index to read
STACK OF ITERATORSO(1) amortisedLRU 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).
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.
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.
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.
None of these fail the samples. Each one fails a hidden test.
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.
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.
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.
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 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.
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.
Twelve designs on one page. The right column is the cue for each.
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.
Module 27. Fifteen problems, all on LeetCode. Next in the sheet: maths and modular arithmetic.
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.