Код Middle Кеш и очереди спрашивают часто обновлено

LRU-кеш с TTL

Условие

Реализуй class LruCache с конструктором new LruCache({ max, ttlMs, now = () => Date.now() }):

  • set(key, value) кладёт значение со сроком жизни ttlMs; если элементов стало больше max, вытесняет давно не использованный;
  • get(key) возвращает значение или undefined, если ключа нет или срок истёк (просроченный ключ удаляется); успешный get делает ключ самым свежим;
  • has(key) как get, но не меняет порядок использования;
  • size: число хранимых элементов (просроченные, которые ещё не трогали, можно считать).

get и set за O(1). Время берётся из now(), чтобы его можно было подменить в тестах.

Что проверяют тесты

  • get/set

  • вытесняет давно не использованный

  • перезапись ключа делает его свежим

  • TTL истекает

  • перезапись продлевает TTL

  • has не меняет порядок

  • значения undefined и 0 различаются с промахом через has

  • max = 1

Как подойти

Подсказки: 3
  1. Map помнит порядок вставки: удаление и повторная вставка переносят ключ в конец.
  2. Самый старый ключ: map.keys().next().value.
  3. Храни в значении момент истечения, а не момент записи.

Решите в тренажёре

Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.