LRU-кэш: вытеснение давно не использованного ключа
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Классы и ООП
- Словари и множества
Реализуйте кэш фиксированной вместимости, который вытесняет давно не использованный ключ (LRU), и выполните по порядку список операций. operations[i] — название операции, values[i] — список её аргументов. Первая операция всегда "init", она одна, values[i] = [capacity] (вместимость не меньше 1), и кэш в начале пуст. Дальнейшие операции: "put" с [key, value] записывает значение (если ключ уже есть, значение обновляется); "get" с [key] возвращает значение или -1, если ключа нет. И put, и успешный get делают ключ самым недавно использованным. Если после put ключей стало больше вместимости, удаляется ключ, который дольше всех не использовался. Для каждой операции верните число: для "init" и "put" это 0, для "get" значение или -1. Хорошо, если get и put работают за O(1).
Пример: ["init", "put", "put", "get", "put", "get"], [[2], [1, 1], [2, 2], [1], [3, 3], [2]] → [0, 0, 0, 1, 0, -1] (после get(1) ключ 2 самый давний и вытесняется при put(3, 3)).
Источник: задача CodeShare