LRU Cache (O(1))

LRU Cache — задача #146 на LeetCode, одна из самых популярных на системных и frontend-собеседованиях. Интервьюер ждёт обе операции за O(1): можно использовать Map (iteration order trick) или Doubly Linked List + HashMap. Важно объяснить трейдоффы обоих подходов.

Подход 1 — Map-trick: порядок итерации Map совпадает с порядком вставки в JS:

// Map в JS: O(1) get/set/delete + порядок вставки = готовый LRU.
// «Недавно использованный» = удалить и вставить в конец Map.

class LRUCacheMap {
  #capacity;
  #cache = new Map(); // oldest (первый) → newest (последний)

  /** @param {number} capacity */
  constructor(capacity) {
    if (capacity &lt; 1) throw new RangeError('capacity &gt;= 1');
    this.#capacity = capacity;
  }

  /**
   * @param {number} key
   * @returns {number} значение или -1 если отсутствует
   * O(1) амортизированно
   */
  get(key) {
    if (!this.#cache.has(key)) return -1;
    const val = this.#cache.get(key);
    this.#cache.delete(key); // убрать со старой позиции
    this.#cache.set(key, val); // вставить в конец (newest)
    return val;
  }

  /**
   * Вставить/обновить. При переполнении вытесняем LRU (первый = oldest).
   * O(1) амортизированно
   */
  put(key, value) {
    if (this.#cache.has(key)) this.#cache.delete(key); // переставить в конец
    this.#cache.set(key, value);
    if (this.#cache.size &gt; this.#capacity) {
      this.#cache.delete(this.#cache.keys().next().value); // удалить oldest
    }
  }

  get size() { return this.#cache.size; }
}

// Трейдоффы Map-подхода:
// ✅ Компактный код (~25 строк), лёгкий для написания на доске
// ✅ O(1) амортизированно для get/put
// ⚠️  Зависит от внутренней реализации Map в движке (spec гарантирует порядок)
// ⚠️  На вопрос "докажи O(1)" — чуть сложнее аргументировать чем DLL

Подход 2 — Doubly Linked List + HashMap: явный O(1) без зависимости от Map:

// DLL: head (oldest) ↔ ... ↔ tail (newest), sentinel nodes
// Map: key → ListNode  →  O(1) доступ к любому узлу

class DLLNode {
  constructor(key = 0, val = 0) {
    this.key  = key; this.val  = val;
    this.prev = null; this.next = null;
  }
}

class LRUCacheDLL {
  #cap; #map = new Map();
  #head = new DLLNode(); // sentinel oldest
  #tail = new DLLNode(); // sentinel newest

  constructor(capacity) {
    this.#cap = capacity;
    this.#head.next = this.#tail;
    this.#tail.prev = this.#head;
  }

  #addToTail(node) {               // вставить перед tail
    node.prev = this.#tail.prev;
    node.next = this.#tail;
    this.#tail.prev.next = node;
    this.#tail.prev      = node;
  }

  #removeNode(node) {              // вырезать из списка
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  get(key) {                       // O(1)
    if (!this.#map.has(key)) return -1;
    const node = this.#map.get(key);
    this.#removeNode(node);
    this.#addToTail(node);         // переместить в newest
    return node.val;
  }

  put(key, value) {                // O(1)
    if (this.#map.has(key)) {
      const node = this.#map.get(key);
      node.val = value;
      this.#removeNode(node);
      this.#addToTail(node);
    } else {
      if (this.#map.size === this.#cap) {
        const lru = this.#head.next; // oldest — сразу после sentinel head
        this.#removeNode(lru);
        this.#map.delete(lru.key);
      }
      const node = new DLLNode(key, value);
      this.#addToTail(node);
      this.#map.set(key, node);
    }
  }
}

// Трейдоффы DLL-подхода:
// ✅ Явный O(1) — не зависит от внутренней реализации Map
// ✅ Правильный ответ на "докажи O(1)" — pointer-операции
// ⚠️  ~45 строк, больше шансов на ошибку в указателях на доске

Единые тесты для обоих классов:

function testLRU(LRU) {
  const cache = new LRU(2);
  cache.put(1, 1);                       // {1=1}
  cache.put(2, 2);                       // {1=1, 2=2}
  console.assert(cache.get(1) === 1);    // {2=2, 1=1}  ← 1 стал newest
  cache.put(3, 3);                       // вытеснить 2: {1=1, 3=3}
  console.assert(cache.get(2) === -1);   // 2 вытеснен
  cache.put(4, 4);                       // вытеснить 1: {3=3, 4=4}
  console.assert(cache.get(1) === -1);   // 1 вытеснен
  console.assert(cache.get(3) === 3);    // {4=4, 3=3}
  console.assert(cache.get(4) === 4);    // {3=3, 4=4}
  console.log('OK', LRU.name);
}

testLRU(LRUCacheMap);
testLRU(LRUCacheDLL);

// ─── Граничные случаи ─────────────────────────────────────────────────────
// capacity = 1
const single = new LRUCacheMap(1);
single.put(1, 10);
single.put(2, 20);                     // вытесняет 1
console.assert(single.get(1) === -1);
console.assert(single.get(2) === 20);

// Обновление существующего ключа не вызывает вытеснение
const c = new LRUCacheMap(2);
c.put(1, 1); c.put(2, 2);
c.put(1, 10);  // обновить 1, сделать его newest
c.put(3, 3);   // вытесняет 2 (oldest), не 1
console.assert(c.get(1) === 10); // 1 не вытеснен ✓
console.assert(c.get(2) === -1); // 2 вытеснен ✓

Сложность

Время: O(1) get / O(1) put для обоих подходов
Память: O(capacity) — хранится не более capacity элементов

Итог: LRU за O(1): Map-trick (25 строк) или DLL+HashMap (45 строк, явный O(1)). На собеседовании показать оба и объяснить трейдофф.