Build an LRU Cache

OrderedDict + move_to_end is all you need.

An LRU cache evicts the least-recently-used item when full. OrderedDict keeps insertion order and lets us cheaply move keys to the end on access.

class LRU:
    def __init__(self, cap):
        self.cap, self.d = cap, OrderedDict()
    def get(self, k):
        if k not in self.d: return -1
        self.d.move_to_end(k)
        return self.d[k]
    def put(self, k, v):
        if k in self.d: self.d.move_to_end(k)
        self.d[k] = v
        if len(self.d) > self.cap:
            self.d.popitem(last=False)  # evict oldest

This is the exact data structure behind functools.lru_cache.

main.py

Output

Press Run to execute.

Expected output

[(1, 'a'), (3, 'c')]