#146MediumLinked lists

LRU Cache

The tell: Get and put both O(1), with eviction ordered by recency.

How you get there

1A hash map gives O(1) lookup but no ordering.
2A doubly linked list gives O(1) reordering but no lookup.
3Combine them — or use OrderedDict, which is exactly that pairing.

Solution

Python

from collections import OrderedDict

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

    def get(self, key: int) -> int:
        if key not in self._data:
            return -1
        self._data.move_to_end(key)          # mark as most recent
        return self._data[key]

    def put(self, key: int, value: int) -> None:
        if key in self._data:
            self._data.move_to_end(key)
        self._data[key] = value
        if len(self._data) > self._cap:
            self._data.popitem(last=False)   # evict least recent

Time: O(1) per operation
Space: O(capacity)

What goes wrong

Forgetting move_to_end on a get means reads never refresh recency, so the wrong entry is evicted.

Test yourself on DSA Next: Reverse Linked List →