Код 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
Mapпомнит порядок вставки: удаление и повторная вставка переносят ключ в конец.- Самый старый ключ:
map.keys().next().value. - Храни в значении момент истечения, а не момент записи.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.
Предыдущий вопрос
Очередь задач с ретраями и dead letter
Следующий вопрос
Дедупликация событий из NDJSON-потока