Код Senior Коллекции спрашивают часто обновлено
LRU-кеш на OrderedDict
Условие
Смоделируйте LRU-кеш ёмкостью capacity. На вход список операций: ["put", key, value] или ["get", key]. Верните список результатов всех get (значение или -1, если ключа нет). get и put делают ключ самым свежим; при переполнении выбрасывается самый давно использованный. Каждая операция O(1).
Примеры
lru(2, [["put", 1, 1], ["put", 2, 2], ["get", 1], ["put", 3, 3], ["get", 2], ["get", 3]]) // [1, -1, 3]
lru(1, [["put", "a", 1], ["put", "b", 2], ["get", "a"], ["get", "b"]]) // [-1, 2]
lru(2, [["get", 1]]) // [-1]
Как подойти
Подсказки: 2
OrderedDict.move_to_endиpopitem(last=False).- Обновление существующего ключа тоже освежает его.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.