Loading page…
Build constant-time structures from a map plus an array or a queue: random pick, rate limits, trip averages and short links (the LRU cache is S1).
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.
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.
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.
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;
}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;
}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.
This version keeps one queue of times for all posts, so every post counts the opens of every other post.
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.
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.
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.
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.
systemdesignmastery.dev/dsa/cheatsheets/designing-with-maps