LRU Cache

The problem description can be found in LeetCode.

Approach

This is a great article that explains the design behind a LRU cache. Most of the code below is taken from the same article.

Solution

from collections import OrderedDict
from typing import OrderedDict


class LRUCache:
    def __init__(self, capacity: int) -> None:
        self.capacity = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1

        self.cache.move_to_end(key)

        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            self.cache.move_to_end(key)
            return

        if len(self.cache) >= self.capacity:
            lru_key = next(iter(self.cache))
            del self.cache[lru_key]

        self.cache[key] = value

Complexity

• Time: $O(1)$
• Space: $O(1)$

References

• Design LRU Cache by Roman Glushko.