LRU Cache · fullstack.org.ua

LRU Cache

ПросунутийJavaScript

Реалізуйте кеш із витісненням найдавніше використаного елемента (LRU) фіксованої ємності.

Напишіть функцію solve(capacity, operations), яка симулює LRU-кеш ємністю capacity. operations — масив операцій виду ["put", key, value] або ["get", key]. Поверніть масив результатів у тому самому порядку: для "put" результат завжди null; для "get" — значення за ключем, якщо воно є в кеші, або -1, якщо немає. Кожне звернення до ключа (і put, і успішний get) робить його «нещодавно використаним»; коли ємність кешу перевищена, витісняється найдавніше використаний ключ.

Приклади

Вхід: solve(2, [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2]])

Вихід: [null, null, 1, null, -1]

put(3,3) витісняє ключ 2, бо після get(1) саме ключ 2 лишився найдавніше використаним

Обмеження: 1 ≤ capacity ≤ 1000

Ваше рішення

Підказки

Підказка 1

Map у JavaScript зберігає порядок вставки ключів і дозволяє за O(1) перевірити наявність, прочитати та видалити елемент — це природна структура для LRU-кешу.

Підказка 2

Щоб позначити ключ як «щойно використаний», видаліть його з Map і одразу вставте знову (set) — він автоматично опиниться в кінці порядку вставки.

Підказка 3

Коли розмір Map перевищує capacity, найдавніше використаний ключ — це перший ключ в ітераторі Map (cache.keys().next().value).

Пояснення розв'язку

javascript

function solve(capacity, operations) {
  const cache = new Map();
  const results = [];

  for (const [op, key, value] of operations) {
    if (op === "put") {
      if (cache.has(key)) cache.delete(key);
      cache.set(key, value);
      if (cache.size > capacity) {
        const oldestKey = cache.keys().next().value;
        cache.delete(oldestKey);
      }
      results.push(null);
    } else {
      if (!cache.has(key)) {
        results.push(-1);
      } else {
        const val = cache.get(key);
        cache.delete(key);
        cache.set(key, val);
        results.push(val);
      }
    }
  }

  return results;
}