Problem 67 · Object & System Design

LRU Cache from Scratch

MediumClassic DSA & systems

01Problem

Implement an LRU cache with get(key) and put(key, value) in O(1), evicting the least-recently-used entry when capacity is exceeded. Do not use OrderedDict.

02Key insight

Hash map gives O(1) lookup to a node; a doubly linked list with sentinel head/tail gives O(1) move-to-front and evict-from-tail. Sentinels eliminate all null-edge cases.

03Solution

solution.pypython48 lines

from __future__ import annotations


class _Node:
    __slots__ = ("key", "val", "prev", "next")

    def __init__(self, key: int = 0, val: int = 0) -> None:
        self.key, self.val = key, val
        self.prev: _Node = self
        self.next: _Node = self


class LRUCache:
    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self.map: dict[int, _Node] = {}
        self.head = _Node()  # head.next = most recent; head.prev = least recent

    def _unlink(self, node: _Node) -> None:
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node: _Node) -> None:
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._push_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        node = self.map.get(key)
        if node is not None:
            node.val = value
            self._unlink(node)
        else:
            if len(self.map) == self.capacity:
                lru = self.head.prev
                self._unlink(lru)
                del self.map[lru.key]
            node = self.map[key] = _Node(key, value)
        self._push_front(node)

Try it first.

TimeO(1) per op

SpaceO(capacity)

tests.py · 3 passing

tests.pypython7 lines

c = LRUCache(2)
c.put(1, 1); c.put(2, 2)
assert c.get(1) == 1
c.put(3, 3)
assert c.get(2) == -1
c.put(1, 10); c.put(4, 4)
assert c.get(3) == -1 and c.get(1) == 10 and c.get(4) == 4

04Staff-level follow-up

Make it thread-safe at high QPS? Shard into N independent LRUs by key hash, each with its own lock (or use CLOCK/approximate LRU like Redis sampling to avoid list mutation on every read).