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