dataset/problem_13/cache.py

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.store: OrderedDict[str, int] = OrderedDict()

    def get(self, key: str) -> int:
        if key not in self.store:
            return -1
        # BUG: does not refresh recency when key is accessed.
        return self.store[key]

    def put(self, key: str, value: int) -> None:
        if key in self.store:
            self.store.pop(key)
        self.store[key] = value
        if len(self.store) > self.capacity:
            self.store.popitem(last=False)