Код Senior Реализация с нуля обновлено
LRU-кэш
Условие
Класс-фабрика LRU(capacity) с get(key) и set(key, value). При переполнении выбрасывается самый давно не используемый. get тоже обновляет свежесть.
Что проверяют тесты
хранит и отдаёт
вытесняет самый старый
get обновляет свежесть
перезапись не раздувает размер
Как подойти
Map сохраняет порядок вставки, поэтому «голова» - первый ключ итератора, «хвост» - последний вставленный. get и set одинаково освежают: delete + set. Вытеснение: map.delete(map.keys().next().value). Классический follow-up - реализация на двусвязном списке + хеш-таблице за O(1) без опоры на порядок Map.
Подсказки: 3
- Map помнит порядок вставки - этого достаточно, связный список писать не обязательно.
- Чтобы «освежить» ключ, удали и вставь заново - он уедет в конец.
- Самый старый ключ - первый из map.keys().
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.