К задачам
LRU Cache с операциями get/put
СредняяАлгоритмы
Лучше работает на десктопе
ПроектированиеХеш-таблицаСвязный списокКеш
Реализуйте LRU cache с фиксированной вместимостью.
Кеш поддерживает операции:
put key value: положить или обновить значение;get key: вернуть значение по ключу или-1, если ключа нет.
Если после put вместимость превышена, нужно удалить least recently used ключ: тот, к которому дольше всего не обращались через get или put.
В тренажере операции передаются списком, а функция должна вернуть ответы только для операций get.
Сигнатура
def lru_cache_interview(capacity: int, operations: list[list]) -> list[int]:Примеры
Пример 1
Вход:
capacity = 2operations = [["put",1,1],["put",2,2],["get",1],["put",3,3],["get",2],["put",4,4],["get",1],["get",3],["get",4]]Выход:
[1,-1,-1,3,4]Пример 2
Вход:
capacity = 1operations = [["put",1,10],["get",1],["put",2,20],["get",1],["get",2]]Выход:
[10,-1,20]Пример 3
Вход:
capacity = 2operations = [["put",1,1],["put",1,2],["get",1],["get",2]]Выход:
[2,-1]Код
Python · Ctrl/⌘ + Enter для запуска
Лимит
15:00
Консоль
Нажмите кнопку запуска или Ctrl+Enter