Реализуйте LRU-кэш с ограничением capacity, в котором при переполнении удаляется элемент, к которому дольше всего не обращались; операции get и put должны работать за константное время.

LRU реализуют хеш-таблицей ключ → узел и двусвязным списком давности. Обращение переносит узел в начало, переполнение удаляет хвост.

Ниже get при промахе возвращает undefined, capacity=0 ничего не хранит:

class LRU {
  constructor(capacity) {
    if (!Number.isInteger(capacity) || capacity < 0) throw new RangeError('capacity');
    this.capacity = capacity;
    this.nodes = new Map();
    this.head = {};
    this.tail = { prev: this.head };
    this.head.next = this.tail;
  }
  unlink(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  front(node) {
    node.prev = this.head;
    node.next = this.head.next;
    node.next.prev = node;
    this.head.next = node;
  }
  get(key) {
    const node = this.nodes.get(key);
    if (!node) return undefined;
    this.unlink(node);
    this.front(node);
    return node.value;
  }
  put(key, value) {
    if (this.capacity === 0) return;
    let node = this.nodes.get(key);
    if (node) {
      this.unlink(node);
      node.value = value;
    } else {
      node = { key, value };
      this.nodes.set(key, node);
    }
    this.front(node);
    if (this.nodes.size > this.capacity) {
      const oldest = this.tail.prev;
      this.unlink(oldest);
      this.nodes.delete(oldest.key);
    }
  }
}

Операции списка O(1), обращения к хеш-таблице — ожидаемо O(1); стандарт JS не обещает строгую худшую O(1) для Map. Память O(capacity).