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]:

Пример

lru_cache_interview(2, [
    ["put", 1, 1],
    ["put", 2, 2],
    ["get", 1],
    ["put", 3, 3],
    ["get", 2],
])
# -> [1, -1]