# Design an LRU Cache Class — High-Level & Low-Level Design Interview Problems

Source: https://www.skillbyai.com/en/design-interviews/lru-design

> O(1) get and put with eviction.

## Hash map plus doubly linked list

An LRU cache with fixed capacity evicts the **least recently used** entry when full. To make `get` and `put` O(1), combine a **hash map** from key to node with a **doubly linked list** ordered by recency: on access, move the node to the head; on insert when full, remove the tail. Interview extensions: make it thread-safe (a single lock is simplest; segmenting by key hash reduces contention), add TTL expiry, support eviction callbacks, or make the eviction policy a strategy (LRU, LFU). In Java, `LinkedHashMap` with access order and `removeEldestEntry` gives LRU behaviour, but interviewers usually want to see the structure built by hand.

## LRU cache from scratch

Python; sentinel head and tail nodes simplify edge cases.

```python
class _Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=None, value=None):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map: dict = {}
        self.head, self.tail = _Node(), _Node()      # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.next, node.prev = self.head.next, self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value) -> None:
        if key in self.map:
            node = self.map[key]
            node.value = value
            self._unlink(node)
        else:
            if len(self.map) == self.capacity:
                lru = self.tail.prev
                self._unlink(lru)
                del self.map[lru.key]
            node = _Node(key, value)
            self.map[key] = node
        self._push_front(node)
```

## A stack of papers on a desk

Every paper you touch goes back on top; when the desk is full, the one at the bottom, untouched longest, goes in the bin.

**Quiz:** Why is a doubly linked list used rather than a singly linked list?

- [ ] To avoid using a hash map
- [ ] To sort keys alphabetically
- [ ] To store duplicate keys
- [x] To unlink a node in O(1) given only a reference to it

*Answer:* To unlink a node in O(1) given only a reference to it. Removal needs the previous pointer.