Designing with a map
Use it when a question lists operations and asks that each one cost constant time. Signal words: design a structure, every operation in constant time, insert and delete and pick, in the last minute, a running average, the first one that appears once.
the whole pattern cardfold it
Start list the operations. For each one, name the cost you need and the structure that gives it. A map finds by key, an array picks by position, and a queue gives the oldest. Then write one invariant that says how the structures agree.
Step for each operation, change every structure that holds the fact, in an order that keeps the invariant true at the end. Check the odd cases: remove the last item, add an item that is already there, remove one that is not.
Stop when the commands run out. Each answer is read from one structure, in one step.
It does not give the least recently used item, or any order that changes on a read. A queue knows only the order of insertion.
Cost: each table step is O(1) on average, and each array or queue step is O(1). One open can drop many times, but each time is dropped once, so n commands cost O(n) in all: O(1) amortised for each. Say both words, average and amortised, when you give the cost.
In this lesson you build structures where every operation takes constant time. You combine a hash map with a queue or with an array, and you keep the two in step.
1. Scenario: opens in the last minute#
A social app shows, under every post, how many times it was opened in the last 60 seconds. The number updates on every open.
Your team lead says: The count must be live. Do not recount the log on every open.
The log of one busy stretch holds 100,000 opens, and the opens arrive in time order.
Here is a short test with a window of 60 seconds. The opens, as (post, time), are (7, 1), (7, 2), (3, 3), (7, 40), (7, 62), (3, 64) and (7, 65). An open at time s counts for an open at time t when t − s is less than 60. The counts are 1, 2, 1, 3, 2, 1 and 3.
So the task is this: for each open, report how many opens of the same post fall inside the window, itself included, in constant time.
Think about the ticket window of a small theatre that serves each customer a numbered slip. The clerk keeps one spike of slips for each show, with the oldest slip at the bottom.
When a customer arrives, the clerk first throws away the slips that are too old, from the bottom. Then the clerk puts the new slip on top, and reads the height of the pile.
The spike for a show is the queue of one post, and the height is the count. The clerk never counts slips one by one, and never looks at another show's pile.
Like a ticket window with a spike of slips for each show: drop old slips from the bottom, add one on top, read the height.
2. Struggle: solve it by hand first#
Before you write code, solve the test by hand.
Solve it by hand: Opens of three posts, counted over the last 60 seconds. The hand-solve sheet loads in your browser.
You write the opens in a row. For each open, you look back over all earlier opens. You count the ones of the same post that are less than 60 seconds old, and add one for the open itself.
Opens: (7, 1), (7, 2), (3, 3), (7, 40), (7, 62), (3, 64), (7, 65), with a window of 60.
| Open | Earlier opens looked at | Same post and less than 60 old | Count |
|---|---|---|---|
| (7, 1) | none | none | 1 |
| (7, 2) | 1 open | time 1 | 2 |
| (3, 3) | 2 opens | none | 1 |
| (7, 40) | 3 opens | times 1 and 2 | 3 |
| (7, 62) | 4 opens | time 40 (62 − 2 = 60 is too old) | 2 |
| (3, 64) | 5 opens | none (64 − 3 = 61) | 1 |
| (7, 65) | 6 opens | times 40 and 62 (65 − 2 = 63 is too old) | 3 |
The look-back read 0 + 1 + 2 + 3 + 4 + 5 + 6 = 21 earlier opens for these 7 opens.
Look at what grows. Every open reads all the opens before it. A log of n opens costs n × (n − 1) / 2 reads.
The first attempt#
You turn the hand method into code.
Start with a correct version. For each open, scan every earlier open of the log.
def recent_counts(posts, times, window):
answers = []
for i in range(len(posts)):
count = 1 # this open
for j in range(i): # every earlier open
if posts[j] == posts[i] and times[i] - times[j] < window:
count += 1
answers.append(count)
return answersThis is correct. It reads n × (n − 1) / 2 earlier opens in all: O(n^2).
The scale check#
Now check the real log.
The log holds 100,000 opens, and each open must be answered as it arrives.
Here is the count:
- Reads: 100,000 × 99,999 / 2, which is about 5 × 10^9.
- Time: at about 10^8 simple steps a second, that is about 50 seconds for the whole log.
- The last open alone reads 99,999 earlier opens before it can answer.
So the work for one open grows with the size of the log. A live count cannot wait that long.
Predict the cost
Q A log holds 100,000 opens. About how many earlier opens does the last open read, and about how many do all opens read together?
Answer & explanation
Answer: C
The last open reads all 99,999 earlier opens. The total is 99,999 + 99,998 + ... + 0, which is 4,999,950,000.
The first attempt is correct, but each open re-reads work that earlier opens already did. Now the team looks for a way to keep that work.
3. See: a queue for each key#
Can we do better?#
Look at two neighbouring opens of the same post. The second open sees almost the same earlier opens as the first one did. Only two things differ: the new open joins, and the opens that are now too old leave.
Opens arrive in time order. So the oldest open of a post is also the first one to become too old. That is the shape of a queue: new times join at the back, and old times leave from the front.
Keep a hash map from each post to its own queue of open times. For each open:
- Find the queue of the post. A new post starts an empty queue.
- Drop times from the front while they are a full window old or older.
- Add the time of this open at the back.
- The length of the queue is the answer.
| Position | Open | Queue of the post before | Dropped | Queue after | Count |
|---|---|---|---|---|---|
| 0 | (7, 1) | empty | none | 1 | 1 |
| 1 | (7, 2) | 1 | none | 1, 2 | 2 |
| 2 | (3, 3) | empty | none | 3 | 1 |
| 3 | (7, 40) | 1, 2 | none | 1, 2, 40 | 3 |
| 4 | (7, 62) | 1, 2, 40 | 1 and 2 | 40, 62 | 2 |
| 5 | (3, 64) | 3 | 3 | 64 | 1 |
| 6 | (7, 65) | 40, 62 | none | 40, 62, 65 | 3 |
Each time is pushed once, and popped at most once. So all the drops together cost at most one step for each open, and each open costs constant time on average.
Race: Scan every earlier open, against a queue for each post. The operation counter loads in your browser.
The race counts the real pushes and pops for opens of one post, one second apart, with a window of 50 seconds. At 10,000 opens the scan reads 49,995,000 earlier opens. The queue makes about 20,000 operations. That is about 2,500 times less, and the gap grows with n.
Each post has its own queue of open times: drop old ones from the front, add the new one at the back, read the length.
The opens are (7, 0), (7, 5), (3, 6), (7, 10) and (7, 11), with a window of 10. The open at time 10 is exactly 10 after the open at time 0. The player stops at four steps and asks you to predict.
Dry run: Predict each step: opens that expire from the front. The step-by-step player loads in your browser.
Reading without the player? Cover the last column and predict it row by row.
| Position | Open | Queue of the post before | Dropped | Queue after | Count |
|---|---|---|---|---|---|
| 0 | (7, 0) | empty | none | 0 | 1 |
| 1 | (7, 5) | 0 | none | 0, 5 | 2 |
| 2 | (3, 6) | empty | none | 6 | 1 |
| 3 | (7, 10) | 0, 5 | 0 (10 − 0 = 10) | 5, 10 | 2 |
| 4 | (7, 11) | 5, 10 | none (11 − 5 = 6) | 5, 10, 11 | 3 |
Look at position 3. The open at time 0 is exactly one window old, so it no longer counts. The rule is "a full window old or older", and the test is >=. At position 2, the queue of post 3 is separate from the queue of post 7.
4. Shape: the pattern#
Here is the rule that keeps the design correct. Every line exists to protect it.
After each open, the queue of its post holds exactly the times of that post's opens that are inside the window of this open, oldest first.
At the start every queue is empty. Now take an open of a post at time t, and say the rule held after the post's last open, at an earlier time t'. Then the queue holds every open of the post that was inside the window of t'.
Every earlier open that is inside the window of t was also inside the window of t', because t' is not later than t. So the queue holds all of them, oldest first, and perhaps a few older times at the front. The steps drop from the front every time that is a full window old or older. Because the times are in order, the times that remain are exactly the ones inside the window of t.
Then the open joins at the back, so the queue holds the opens inside the window, this one included, and its length is the count. The queue of any other post is untouched, and its rule is about its own last open, so it still holds.
The pattern behind this one is a recipe for any design question.
Use it when a question lists operations and asks that each one cost constant time. Signal words: design a structure, every operation in constant time, insert and delete and pick, in the last minute, a running average, the first one that appears once.
Start: list the operations. For each one, name the cost you need and the structure that gives it. A map finds by key, an array picks by position, and a queue gives the oldest. Then write one invariant that says how the structures agree.
Step: for each operation, change every structure that holds the fact, in an order that keeps the invariant true at the end. Check the odd cases: remove the last item, add an item that is already there, remove one that is not.
Stop: when the commands run out. Each answer is read from one structure, in one step.
It does not give the least recently used item, or any order that changes on a read. A queue knows only the order of insertion.
Cost: each table step is O(1) on average, and each array or queue step is O(1). One open can drop many times, but each time is dropped once, so n commands cost O(n) in all: O(1) amortised for each. Say both words, average and amortised, when you give the cost.
Template 1: a queue for each key#
from collections import deque
def recent_counts(posts, times, window):
# [1] A table from each post to a queue of the times it was opened, oldest at the front.
queues = {}
answers = []
for i in range(len(posts)):
# [2] Read the opens in time order. A post seen for the first time starts an empty queue.
queue = queues.setdefault(posts[i], deque())
# [3] Drop the opens that are a full window old or older. They are at the front.
while queue and times[i] - queue[0] >= window:
queue.popleft()
# [4] This open joins the back of the queue.
queue.append(times[i])
# [5] The queue holds exactly the opens in the window, so its length is the answer.
answers.append(len(queue))
# [6] One answer for each open.
return answerspublic int[] recentCounts(int[] posts, int[] times, int window) {
// [1] A table from each post to a queue of the times it was opened, oldest at the front.
java.util.HashMap<Integer, java.util.ArrayDeque<Integer>> queues = new java.util.HashMap<>();
int[] answers = new int[posts.length];
for (int i = 0; i < posts.length; i++) {
// [2] Read the opens in time order. A post seen for the first time starts an empty queue.
java.util.ArrayDeque<Integer> queue = queues.computeIfAbsent(posts[i], k -> new java.util.ArrayDeque<>());
// [3] Drop the opens that are a full window old or older. They are at the front.
while (!queue.isEmpty() && times[i] - queue.peekFirst() >= window) {
queue.pollFirst();
}
// [4] This open joins the back of the queue.
queue.addLast(times[i]);
// [5] The queue holds exactly the opens in the window, so its length is the answer.
answers[i] = queue.size();
}
// [6] One answer for each open.
return answers;
}vector<int> recentCounts(vector<int>& posts, vector<int>& times, int window) {
// [1] A table from each post to a queue of the times it was opened, oldest at the front.
unordered_map<int, deque<int>> queues;
vector<int> answers;
for (size_t i = 0; i < posts.size(); i++) {
// [2] Read the opens in time order. A post seen for the first time starts an empty queue.
deque<int>& queue = queues[posts[i]];
// [3] Drop the opens that are a full window old or older. They are at the front.
while (!queue.empty() && times[i] - queue.front() >= window) {
queue.pop_front();
}
// [4] This open joins the back of the queue.
queue.push_back(times[i]);
// [5] The queue holds exactly the opens in the window, so its length is the answer.
answers.push_back((int)queue.size());
}
// [6] One answer for each open.
return answers;
}function recentCounts(posts, times, window) {
// [1] A table from each post to a queue of the times it was opened, oldest at the front.
const queues = new Map();
const answers = [];
for (let i = 0; i < posts.length; i++) {
// [2] Read the opens in time order. A post seen for the first time starts an empty queue.
// JavaScript has no deque, so the queue is an array and a head index.
if (!queues.has(posts[i])) queues.set(posts[i], { items: [], head: 0 });
const queue = queues.get(posts[i]);
// [3] Drop the opens that are a full window old or older. They are at the front.
// Moving the head index drops an open in one step.
while (queue.head < queue.items.length && times[i] - queue.items[queue.head] >= window) {
queue.head++;
}
// [4] This open joins the back of the queue.
queue.items.push(times[i]);
// [5] The queue holds exactly the opens in the window, so its length is the answer.
answers.push(queue.items.length - queue.head);
}
// [6] One answer for each open.
return answers;
}Template 2: a table and an array, with a swap#
A cache holds at most capacity keys. A put adds a key with its value, and a full cache first evicts a key at random. A get reads a value, and a del removes a key on request, for example when its data changes. The random draw comes with each put as a number r, so that every run gives the same answers.
Both removals use one move. A del finds the position of its key in the table, and an eviction takes position r mod size. Then the last key moves into that place, the table learns its new position, and the array becomes one shorter.
def run_cache(capacity, commands, args):
# [1] An array of the keys, a table from each key to its position, and a table from each key to its value.
keys = []
slot = {}
value = {}
answers = []
for i in range(len(commands)):
command, a = commands[i], args[i]
if command == "get":
# [2] A get reads the value by key in one step, or gives minus one.
answers.append(value.get(a[0], -1))
continue
# [3] Find the place to free: the position of the key to delete, or r mod size when a new key finds the cache full.
place = -1
if command == "del" and a[0] in slot:
place = slot[a[0]]
elif command == "put" and a[0] not in slot and len(keys) == capacity:
place = a[2] % len(keys)
if place >= 0:
# [4] The last key moves into the place, and its position is updated. Then the array shrinks, and the removed key leaves both tables last.
victim = keys[place]
last = keys[-1]
keys[place] = last
slot[last] = place
keys.pop()
del slot[victim]
del value[victim]
if command == "put":
# [5] A new key goes to the end of the array. A key that is already there only gets its new value.
if a[0] not in slot:
slot[a[0]] = len(keys)
keys.append(a[0])
value[a[0]] = a[1]
# [6] One answer for each get.
return answerspublic int[] runCache(int capacity, String[] commands, int[][] args) {
// [1] An array of the keys, a table from each key to its position, and a table from each key to its value.
java.util.List<Integer> keys = new java.util.ArrayList<>();
java.util.HashMap<Integer, Integer> slot = new java.util.HashMap<>();
java.util.HashMap<Integer, Integer> value = new java.util.HashMap<>();
java.util.List<Integer> answers = new java.util.ArrayList<>();
for (int i = 0; i < commands.length; i++) {
String command = commands[i];
int[] a = args[i];
if (command.equals("get")) {
// [2] A get reads the value by key in one step, or gives minus one.
answers.add(value.getOrDefault(a[0], -1));
continue;
}
// [3] Find the place to free: the position of the key to delete, or r mod size when a new key finds the cache full.
int place = -1;
if (command.equals("del") && slot.containsKey(a[0])) {
place = slot.get(a[0]);
} else if (command.equals("put") && !slot.containsKey(a[0]) && keys.size() == capacity) {
place = a[2] % keys.size();
}
if (place >= 0) {
// [4] The last key moves into the place, and its position is updated. Then the array shrinks, and the removed key leaves both tables last.
int victim = keys.get(place);
int last = keys.get(keys.size() - 1);
keys.set(place, last);
slot.put(last, place);
keys.remove(keys.size() - 1);
slot.remove(victim);
value.remove(victim);
}
if (command.equals("put")) {
// [5] A new key goes to the end of the array. A key that is already there only gets its new value.
if (!slot.containsKey(a[0])) {
slot.put(a[0], keys.size());
keys.add(a[0]);
}
value.put(a[0], a[1]);
}
}
// [6] One answer for each get.
int[] result = new int[answers.size()];
for (int k = 0; k < result.length; k++) {
result[k] = answers.get(k);
}
return result;
}vector<int> runCache(int capacity, vector<string>& commands, vector<vector<int>>& args) {
// [1] An array of the keys, a table from each key to its position, and a table from each key to its value.
vector<int> keys;
unordered_map<int, int> slot;
unordered_map<int, int> value;
vector<int> answers;
for (size_t i = 0; i < commands.size(); i++) {
const string& command = commands[i];
const vector<int>& a = args[i];
if (command == "get") {
// [2] A get reads the value by key in one step, or gives minus one.
auto it = value.find(a[0]);
answers.push_back(it == value.end() ? -1 : it->second);
continue;
}
// [3] Find the place to free: the position of the key to delete, or r mod size when a new key finds the cache full.
int place = -1;
if (command == "del" && slot.count(a[0])) {
place = slot[a[0]];
} else if (command == "put" && !slot.count(a[0]) && (int)keys.size() == capacity) {
place = a[2] % (int)keys.size();
}
if (place >= 0) {
// [4] The last key moves into the place, and its position is updated. Then the array shrinks, and the removed key leaves both tables last.
int victim = keys[place];
int last = keys.back();
keys[place] = last;
slot[last] = place;
keys.pop_back();
slot.erase(victim);
value.erase(victim);
}
if (command == "put") {
// [5] A new key goes to the end of the array. A key that is already there only gets its new value.
if (!slot.count(a[0])) {
slot[a[0]] = (int)keys.size();
keys.push_back(a[0]);
}
value[a[0]] = a[1];
}
}
// [6] One answer for each get.
return answers;
}function runCache(capacity, commands, args) {
// [1] An array of the keys, a table from each key to its position, and a table from each key to its value.
const keys = [];
const slot = new Map();
const value = new Map();
const answers = [];
for (let i = 0; i < commands.length; i++) {
const command = commands[i];
const a = args[i];
if (command === "get") {
// [2] A get reads the value by key in one step, or gives minus one.
answers.push(value.has(a[0]) ? value.get(a[0]) : -1);
continue;
}
// [3] Find the place to free: the position of the key to delete, or r mod size when a new key finds the cache full.
let place = -1;
if (command === "del" && slot.has(a[0])) {
place = slot.get(a[0]);
} else if (command === "put" && !slot.has(a[0]) && keys.length === capacity) {
place = a[2] % keys.length;
}
if (place >= 0) {
// [4] The last key moves into the place, and its position is updated. Then the array shrinks, and the removed key leaves both tables last.
const victim = keys[place];
const last = keys[keys.length - 1];
keys[place] = last;
slot.set(last, place);
keys.pop();
slot.delete(victim);
value.delete(victim);
}
if (command === "put") {
// [5] A new key goes to the end of the array. A key that is already there only gets its new value.
if (!slot.has(a[0])) {
slot.set(a[0], keys.length);
keys.push(a[0]);
}
value.set(a[0], a[1]);
}
}
// [6] One answer for each get.
return answers;
}Rebuild the template: put its lines back in order. Loads in your browser.
To remove from the middle of an array in one step, move the last item into the hole, update its position in the table, and shorten the array.
An app runs a prize raffle. A person can enter, can withdraw, and a draw picks one entrant at random and removes the winner. Each draw comes with a number r. The winner is the entrant at position r mod n of the array.
This is Template 2 with no values. An enter is a put of a new key, and a withdraw is a del. A draw removes the entrant at position r mod n, the same move as an eviction. The commands are enter 10, enter 20, enter 30, withdraw 10, draw 1 and draw 0.
| Command | Array after | Table of positions | Answer |
|---|---|---|---|
| enter 10 | 10 | 10: 0 | |
| enter 20 | 10, 20 | 10: 0, 20: 1 | |
| enter 30 | 10, 20, 30 | 10: 0, 20: 1, 30: 2 | |
| withdraw 10 | 30, 20: the last item moved into place 0 | 30: 0, 20: 1 | |
| draw 1 | 30: position 1 mod 2 is 1, which is 20, and it is swapped out | 30: 0 | 20 |
| draw 0 | empty: position 0 mod 1 is 0, which is 30 | none | 30 |
The winners are 20 and then 30. A swap with the last item removed an entrant from the middle in one step.
Complexity in plain words#
- Time. Each open costs one table step, one push and some drops. One open can drop many times, but a drop is paid for by the push that added the time, so n opens cost O(n) in all. That is O(1) amortised for each open: averaged over the whole log, not promised for every single open.
- At scale. For 100,000 opens, the queue makes about 200,000 operations. The scan makes about 5 × 10^9.
- Worst case. The queue of a post holds all its opens inside the window. If every open falls in one window, one queue holds n times, so the space is O(n).
- Space. The table has one queue for each post, and the queues together hold at most one time for each open. For the cache, the array and the two tables each hold at most one entry for each key, so that space is O(capacity).
- Trade. The scan keeps nothing except the log. The queues keep a second copy of the recent times. That memory buys the drop from billions of reads to a few hundred thousand steps.
- Stale entries. A queue entry that no longer counts is a stale entry. A design may leave it in place and drop it when it reaches the front, because each entry then leaves once.
The cache of Template 2 has its own costs, operation by operation. A table step is O(1) on average, and O(n) in the worst case if many keys share a hash, as the last lesson showed.
| Operation | Cost | Why |
|---|---|---|
get |
O(1) on average | one table lookup |
put of a key that is there |
O(1) on average | one table write |
put of a new key |
O(1) on average, amortised | an append, and the array sometimes grows by copying itself, which costs O(1) when spread over all the appends |
del, or an eviction |
O(1) on average | one lookup, one write into the hole, one update and one removal from the end |
| a random pick | O(1), even in the worst case | one array read at a position |
Without the swap, a removal from the middle shifts every key behind the hole, which is O(n). Without the array, a random pick has to walk the table to the r-th key, which is O(n) too.
5. Stretch: edges, mistakes and variations#
Edge cases#
Real production data brings edge cases.
For posts = [] and times = [], the answer is []. For posts = [5] and times = [0] with a window of 60, the answer is [1], the open itself.
For posts = [4, 4, 4], times = [5, 5, 5] and a window of 1, the answer is [1, 2, 3]. An open at the same second is 0 old, which is less than the window, so it counts. Opens at one time are not duplicates.
For posts = [1, 1], times = [0, 60] and a window of 60, the answer is [1, 1]. The first open is 60 old, which is a full window, so it has left. For times = [0, 59] the answer is [1, 2].
With a capacity of 1, every new key evicts the only key. For put 1, then put 2 with r = 9, a get of 1 gives -1 and a get of 2 gives the value of 2. Updating the key that is there evicts nothing.
The mistake museum#
This version drops a time only when it is more than a window old, with > instead of >=. Then an open that is exactly a window old still counts.
Counterexample: posts = [1, 1], times = [0, 60], window 60. The bug returns [1, 2], and the right answer is [1, 1].
Decide the boundary from the words of the task, and test it with a time exactly one window apart.
This version keeps one queue of times for all posts, so every post counts the opens of every other post.
Counterexample: posts = [1, 2, 1], times = [0, 1, 2], window 10. The bug returns [1, 2, 3], and the right answer is [1, 1, 2].
The table from key to queue is the point of the design. One queue for each key.
After the last item moves into the hole, its position in the table must change too, or the next removal reads past the end of the array.
This version swaps the last item into the hole and forgets to update the table. The moved item still has its old position, which is now past the end of the array.
Counterexample: enter 1, enter 2, enter 3, withdraw 1, withdraw 3, then draw 0. After the first withdrawal the array is [3, 2], and the table still says 3 is at position 2. The second withdrawal writes to position 2 of an array of length 2.
Python raises an IndexError there, and Java an IndexOutOfBoundsException. JavaScript is worse: the write silently grows the array to [3, 2, 2], the removal shrinks it to [3, 2], and the draw returns 3, an entrant who has withdrawn. The right winner is 2.
After every swap, write the new position of the item that moved.
This version removes the item from the table first, and then records the position of the last item. When the item removed is the last one, the second step puts it back into the table.
Counterexample: enter 1, enter 2, withdraw 2, enter 2. The ghost entry for 2 is still in the table, so the second enter returns "already there" and the item is never added. The right answer lets 2 enter again.
Do the move first, and delete the removed item from the table last. Test with the removal of the last item.
This version uses a Python list or a JavaScript array as the queue, and removes the oldest time with pop(0) or shift(). Each removal moves every item behind it, so the queue is no longer constant time.
Counterexample: one post with 200,000 times in its queue. On my laptop, emptying such a list with pop(0) took about 3 seconds, and a deque took about 8 milliseconds. In JavaScript, 200,000 calls of shift() on an array of that size took about 3 seconds, and moving a head index took under a millisecond.
Use collections.deque in Python, ArrayDeque in Java, deque in C++, and an array with a head index in JavaScript, which has no built-in deque.
When the pattern does not apply#
Your team lead asks for a cache that evicts the item that was used least recently. A queue knows only the order in which items were added. When an item is read, it must move to the back, and a queue cannot move an item from the middle in one step.
For that you need a doubly linked list next to the table, so that an item can be unlinked and relinked in constant time. That is the LRU cache of the linked-list lessons, and a random-eviction cache like Template 2 needs only an array.
Product variations#
Your team lead brings four product changes. Each one asks which facts to keep.
A gateway lets a user make at most k requests in a window. Use the same queue for each user. Drop the old times, and allow the request when fewer than k times are left.
Push the time only when the request is allowed, so that a refused request does not extend the wait. When the limit is 1, the queue shrinks to one number, the time of the last allowed request. That is the logger problem: a message prints once in ten seconds (LeetCode 359: Logger Rate Limiter).
A real gateway also removes the queue of a user who has gone quiet, or the table grows with every user ever seen.
A transit app shows the average trip time between two stations, as riders tap in and out. Keep a table of open trips, from card to start station and time. Keep a second table from route to a total and a count. An average is the total over the count, and the key of a route is a pair that stays a pair (LeetCode 1396: Design Underground System).
A chat app turns a long link into a short code. Keep a table from link to number, and an array in which number k is at index k − 1. A shorten uses the table, and an expand uses the array (LeetCode 535: Encode and Decode TinyURL).
A payments app asks for the earliest id that has arrived exactly once so far. Keep a table of counts and a queue of ids in order of arrival. When a question comes, drop ids from the front while their count is more than 1. The stale entries wait until they reach the front (LeetCode 1429: First Unique Number).
Why this matters in real systems#
6. Say: lock it in#
Explain it back#
Explain it back: write the idea in your own words and get feedback.
In two or three sentences, explain to a teammate how you count the opens of each post in the last minute in constant time. Then explain how you remove a random item from a set in constant time. The AI tutor checks your answer against the invariant and the key points of this lesson.
Here is how you could explain it in an interview, now that you have built it.
I list the operations and the cost each must have. For a count over a window, I keep a queue of times for each key, in a map.
On a new event I drop the old times from the front, add the new time at the back, and answer with the length. Each time is pushed once and popped once, so it is constant on average.
To remove from the middle of an array in constant time, I keep a map from item to position. I move the last item into the hole, and update its position.
The 60-second interview answer#
For a design question, I first list the operations and the cost each one needs, here constant time. Then I pick the structure that gives each operation in one step: a map finds by key, an array picks by position, and a queue gives the oldest.
For a count in the last minute, I keep a map from each key to a queue of times. On an event I drop the old times from the front, add the new time, and read the length. Each time is pushed once and popped once, so the cost is constant on average.
To pick a random item and remove any item, I keep an array and a map from item to position. I remove by moving the last item into the hole and updating its position.
I state the invariant that keeps the structures in step, and I test removing the last item.
Checkpoint#
Checkpoint · The recipe
Q1/3 A design needs a pick by position, a find by key and the oldest item, each in constant time. Which structures give them, in that order?
Answer & explanation
Answer: B
An array reads a position in one step, a map finds a key in one step, and a queue gives its oldest item at the front.
Q2/3 A post has opens at times 0 and 10, and the window is 10. The open at time 10 arrives. What is its count?
Answer & explanation
Answer: B
The open at time 0 is exactly a window old, and the rule drops a time that is a full window old or older. Only the open at time 10 is left.
Q3/3 Why does a queue of open times cost constant time on average, although one open can drop many times?
Answer & explanation
Answer: C
A drop is paid for by the push that added the time. Over n opens, the pushes and the pops together make at most 2n operations. One open can still drop many times, so the constant is amortised: an average over the whole log.
Checkpoint · Swapping with the last
Q1/3 An array holds 10, 20, 30, and a table holds the position of each. You remove 10 by moving the last item into its place. What does the array hold?
Answer & explanation
Answer: C
The last item, 30, moves into place 0, and the array becomes one shorter, so it holds 30 and 20.
Q2/3 After the last item moves into the hole, what must you also change?
Answer & explanation
Answer: C
The moved item now sits at a new place, so its entry in the table must change. Without that, a later removal reads a place that no longer holds it.
Q3/3 What goes wrong if you delete the removed item from the table first, and then record the position of the last item?
Answer & explanation
Answer: B
If the removed item is also the last item, recording the position of "the last item" writes the removed item into the table again. It then looks present when it is not.
Checkpoint · Totals, queues and limits
Q1/4 Three trips on one route took 0, 0 and 6 minutes. A program sets the average to the mean of the old average and each new time. What does it give, and what is right?
Answer & explanation
Answer: B
The program gives 0, then 0, then (0 + 6) / 2 = 3. The right average is the total, 6, over the count, 3, which is 2. Keep a total and a count.
Q2/4 Why is removing the oldest item with list.pop(0) a poor choice for a queue in Python?
Answer & explanation
Answer: B
In the lesson, emptying a list of 200,000 items with pop(0) took about 3 seconds, and a deque took about 8 milliseconds.
Q3/4 In the first-unique-id design, an id arrives a second time while it sits in the middle of the queue. What do you do?
Answer & explanation
Answer: B
Removing from the middle costs a search. A stale entry can wait, and it is dropped once when it reaches the front.
Q4/4 Which design cannot be built from a plain queue and a table?
Answer & explanation
Answer: C
A queue knows only the order of insertion. A read must move an item to the back, and that needs a doubly linked list, which the linked-list lessons build.
Ten questions on this lesson. Pass with 80% or more to be sure the idea has landed before the next lesson. The checkpoint of this stretch, with its two mixed problems, comes after this lesson.
Practice ladder#
| Step | Problem | Product line | Level | What it practises |
|---|---|---|---|---|
| 1 | Logger that drops repeats within ten seconds | Observe | Easy | One time for each key, updated only on a print |
| 2 | Set with a fair random pick | Stream | Medium | A table and an array in step, with a swap |
| 3 | Average trip time between two stations | Maps | Medium | Two tables: open trips and route totals |
| 4 | Shorten and expand links | Chat | Medium | A table one way and an array the other way |
Review cards#
Review cards from this lesson.
Six cards from this lesson join your spaced-review deck. The first one comes back tomorrow.