Задача: LRU-кеш
На этой странице
LRU (Least Recently Used) — кеш ограниченного размера, который при переполнении удаляет давно не использованный элемент. Операции get и put должны работать за O(1). В JavaScript самое короткое решение — Map: он хранит ключи в порядке вставки, поэтому «использование» = удалить ключ и вставить заново в конец, а самый старый ключ — первый в map.keys(). Классическое решение на любом языке — хеш-таблица + двусвязный список.
Вопрос
Реализуйте класс LRUCache(capacity) с методами get(key) (вернуть значение или undefined и отметить как использованное) и put(key, value) (добавить или обновить; при превышении capacity удалить самый давно использованный). Обе операции — O(1).
Решение на Map
class LRUCache {
#map = new Map();
constructor(capacity) {
if (capacity <= 0) throw new RangeError("capacity должен быть больше 0");
this.capacity = capacity;
}
get(key) {
if (!this.#map.has(key)) return undefined;
const value = this.#map.get(key);
this.#map.delete(key);
this.#map.set(key, value); // переместить в конец — самый свежий
return value;
}
put(key, value) {
if (this.#map.has(key)) this.#map.delete(key);
this.#map.set(key, value);
if (this.#map.size > this.capacity) {
const oldestKey = this.#map.keys().next().value; // первый — самый старый
this.#map.delete(oldestKey);
}
}
get size() {
return this.#map.size;
}
}Проверка
const cache = new LRUCache(2);
cache.put("a", 1);
cache.put("b", 2);
cache.get("a"); // 1 — теперь "a" свежее "b"
cache.put("c", 3); // переполнение: удаляется "b"
cache.get("b"); // undefined
cache.get("a"); // 1
cache.get("c"); // 3Решение на двусвязном списке
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCacheList {
constructor(capacity) {
this.capacity = capacity;
this.map = new Map(); // key → Node
this.head = new Node(null, null); // фиктивные узлы упрощают граничные случаи
this.tail = new Node(null, null);
this.head.next = this.tail;
this.tail.prev = this.head;
}
#remove(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
#addToFront(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
get(key) {
const node = this.map.get(key);
if (!node) return undefined;
this.#remove(node);
this.#addToFront(node);
return node.value;
}
put(key, value) {
const existing = this.map.get(key);
if (existing) {
existing.value = value;
this.#remove(existing);
this.#addToFront(existing);
return;
}
const node = new Node(key, value);
this.map.set(key, node);
this.#addToFront(node);
if (this.map.size > this.capacity) {
const lru = this.tail.prev; // самый старый — перед хвостом
this.#remove(lru);
this.map.delete(lru.key);
}
}
}Голова списка — самые свежие элементы, хвост — самые старые; Map дает доступ к узлу за O(1), список — перемещение и удаление за O(1).
Доп. вопросы интервьюера
- Почему
Map, а не объект?Mapгарантирует порядок вставки для любых ключей и имеетsize; у объекта числовые ключи сортируются. - Как добавить TTL? хранить
{ value, expiresAt }и проверять время вget. - Где используется? кеш запросов и изображений, мемоизация с ограничением, кеш страниц в браузере, кеш в Redis (
allkeys-lru). - LRU vs LFU? LFU удаляет наименее часто используемый элемент — нужен счетчик обращений.
Что важно помнить
getтоже обновляет «свежесть» элемента.- Обновление существующего ключа не должно увеличивать размер.
- В решении на
Mapудаление и повторная вставка — O(1). - Теория: hash table, linked list.
Мини-шпаргалка
Map в порядке вставки: get → delete + set (в конец), put → delete + set, переполнение → удалить keys().next().value. Классика: Map key → узел двусвязного списка, голова — свежие, хвост — старые, фиктивные head/tail. O(1).
Документация
MDN: Map, LeetCode 146: LRU Cache, Wikipedia: Cache replacement policies.