Код Middle Кеширование спрашивают часто обновлено
LRU-кеш с TTL по журналу операций
Условие
Смоделируйте кеш ёмкостью capacity с TTL. Операции: ["set", key, value, ttl, now], ["get", key, now]. Ключ истекает, когда now >= время_записи + ttl. get истёкшего ключа удаляет его и возвращает None; get живого ключа делает его самым свежим. set существующего ключа обновляет значение, TTL и свежесть. При переполнении сначала удаляются истёкшие ключи (на момент set), а если места всё равно нет, самый давно использованный. Верните результаты всех get.
Примеры
simulate(2, [["set", "a", 1, 10, 0], ["get", "a", 5], ["get", "a", 10]]) // [1, null]
simulate(2, [["set", "a", 1, 100, 0], ["set", "b", 2, 100, 0], ["get", "a", 1], ["set", "c", 3, 100, 2], ["get", "b", 3], ["get", "a", 3]]) // [1, null, 1]
simulate(2, [["set", "a", 1, 5, 0], ["set", "b", 2, 100, 0], ["get", "b", 1], ["set", "c", 3, 100, 6], ["get", "b", 7], ["get", "c", 7]]) // [2, 2, 3]
Как подойти
Подсказки: 2
OrderedDictдля LRU, в значении храните момент истечения.- При
setсначала чистите истёкшие, потом LRU.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.