Код Middle Классы и интерфейсы обновлено
Generic LRU-кеш: класс с параметрами K и V
Условие
Напиши класс LRU<K, V> с конструктором (capacity: number) и методами get(key: K): V | undefined, set(key: K, value: V): void, геттер size. При переполнении вытесняется давно не использованный ключ; get обновляет использование. Сложность O(1).
run(capacity, ops) в заготовке выполняет операции ['set', k, v] / ['get', k] и собирает результаты get (промах как null).
Примеры
run(2, [["set", "a", 1], ["set", "b", 2], ["get", "a"], ["set", "c", 3], ["get", "b"], ["get", "a"], ["get", "c"]]) // [1, null, 1, 3, 2]
run(1, [["set", "a", 1], ["set", "b", 2], ["get", "a"], ["get", "b"]]) // [null, 2, 1]
run(2, [["set", "a", 1], ["set", "a", 5], ["set", "b", 2], ["set", "c", 3], ["get", "a"]]) // [null, 2]
Как подойти
Подсказки: 2
Mapхранит порядок вставки: удалить и вставить заново значит «освежить».map.getвозвращаетV | undefined: если значения сами могут бытьundefined, проверяйhas.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.