DevOps NetworkDevOpsNetwork
Join Free
Advanced

LRU Cache

mediumDesign-heavy Must-do

Problem statement

Build a fixed-size cache that throws away the least recently used entry when it runs out of room. This is the eviction rule behind many real caches: the entry nobody has touched for the longest time is the one least likely to be needed soon.

Implement a class LRUCache:

  • LRUCache(capacity) — create an empty cache that can hold at most capacity keys (capacity >= 1).
  • get(key) — return the value stored for key, or -1 if it isn't in the cache. A successful get counts as using the key.
  • put(key, value) — store value for key. If the key already exists, replace its value (this also counts as using it). If it's new and the cache is already full, first remove the least recently used key, then add the new one.

Both get and put must take O(1) time on average, no matter how full the cache is.

Examples

Example 1

Input: ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation: After get(1), key 2 is the least recently used, so put(3, 3) evicts it and get(2) returns -1. Then key 1 is the oldest, so put(4, 4) evicts it; keys 3 and 4 remain.

Hints

Hint 1: A hash map gives O(1) lookup by key, but it doesn't remember the order in which keys were used. What structure keeps an order and lets you move any item to the front in O(1)?

Approach

Optimal: Hash map + doubly linked list

Intuition

The brute force was slow only because it had to search the list to find a key before moving it. So store the list node itself in the map: key → node. Now we can jump straight to any node.

To move that node in O(1), each node needs pointers to both its neighbours — a doubly linked list. Unlinking is then just "my previous node now points to my next node, and back". Keep the most recently used node at the front and the least recently used at the back.

Two sentinel nodes, a fixed head and tail that never hold data, sit at the ends. With them, every real node always has a neighbour on both sides, so there are no special cases for an empty list or for removing the first or last node. Each node also stores its key, so when we evict the back node we know which key to delete from the map.

Steps

  1. Create head and tail sentinels linked to each other, and an empty map.
  2. Helpers: remove(node) links node.prev and node.next together. add_front(node) inserts node right after head.
  3. get(key): if the key isn't in the map, return -1. Otherwise take its node, remove it, add_front it, and return its value.
  4. put(key, value):
    • If the key exists: update the node's value, remove it and add_front it.
    • Otherwise: if the map is full, take tail.prev (the least recently used), remove it and delete its key from the map. Then create a new node, add_front it and store it in the map.

Dry run

Capacity 2 (list shown front = most recent → back = least recent):

call list after map keys returns
put(1, 1) 1 {1} null
put(2, 2) 2, 1 {1, 2} null
get(1) 1, 2 {1, 2} 1
put(3, 3) evict back (2) → 3, 1 {1, 3} null
get(2) 3, 1 {1, 3} -1
put(4, 4) evict back (1) → 4, 3 {3, 4} null
get(1) 4, 3 {3, 4} -1
get(3) 3, 4 {3, 4} 3
get(4) 4, 3 {3, 4} 4

Edge case: with capacity 1, every new key evicts the only existing one, and the sentinels keep the pointer updates the same as for larger caches.

Complexity

Time O(1) — per operation — The map finds a key's node in O(1) on average. Unlinking a node from a doubly linked list and inserting it at the front only changes four pointers, so it is O(1) too. Evicting reads the node just before the tail, also O(1). So 200,000 calls take about 200,000 constant-time steps, whatever the capacity.

Space O(capacity) — The map and the list each hold one entry per cached key, plus two fixed sentinel nodes.

from typing import Dict, List, Optional


class Node:
    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.prev: Optional["Node"] = None
        self.next: Optional["Node"] = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes: Dict[int, Node] = {}
        self.head = Node()  # sentinel: most recent side
        self.tail = Node()  # sentinel: least recent side
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node: Node) -> None:
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1
        self._remove(node)
        self._add_front(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._remove(node)
            self._add_front(node)
            return
        if len(self.nodes) == self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.nodes[lru.key]
        node = Node(key, value)
        self._add_front(node)
        self.nodes[key] = node


def replay(ops: List[str], args: List[List[int]]) -> str:
    out: List[str] = []
    cache = None
    for op, a in zip(ops, args):
        if op == "LRUCache":
            cache = LRUCache(*a)
            out.append("null")
        elif op == "put":
            cache.put(*a)
            out.append("null")
        else:
            out.append(str(cache.get(*a)))
    return "[" + ", ".join(out) + "]"


if __name__ == "__main__":
    print(replay(["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"],
                 [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]))
RecapThe whole problem in a few lines, for the night before
  • Spot it: fixed-size cache, evict the least recently used, get and put in O(1)
  • Idea: hash map from key to node + doubly linked list ordered by recency; move to front on use, evict from the back
  • Cost: O(1) time per operation, O(capacity) space
  • Trap: forgetting that get also counts as a use, or not storing the key in the node (then eviction can't update the map)
  • Remember: sentinel head and tail nodes remove every empty-list and end-of-list special case

Interview follow-ups

  • Make it safe to use from many threads at once.

    The simplest fix is one lock around every get and put, because even get changes the list order. That's correct but serialises all calls. To scale, split the cache into N shards by hash(key) % N, each with its own lock and its own LRU list, so different keys rarely wait on each other. The trade-off is that eviction becomes "least recently used within a shard" rather than globally.

  • Entries should also expire after a time-to-live (TTL).

    Store an expiry time in each node, taken from an injectable clock so tests can control time. On get, if the node has expired, remove it and return -1 (lazy expiry). To free memory without waiting for a get, a background sweep can walk from the back of the list and drop expired nodes. get and put stay O(1).

  • The cache must survive a restart.

    Periodically write a snapshot of the keys and values, in LRU order, to disk, and reload it on startup. Between snapshots, append each put to a write-ahead log so recent changes aren't lost; replay the log on top of the snapshot when starting. Reads stay in memory, so get is still O(1); only put pays for the log write.

Frequently asked questions

To unlink a node you must change the next pointer of the node before it. In a singly linked list, finding that previous node means walking from the start, which is O(n). With a prev pointer in every node, you reach the previous node directly, so removing any node is O(1).

When the cache is full, we evict the node at the back of the list. We also have to delete that key from the map, but the list alone doesn't tell us the key — unless the node stores it. Without the key in the node, eviction would need a search through the map.

Yes, in real code. OrderedDict with move_to_end and popitem(last=False), or LinkedHashMap with access order and removeEldestEntry, is exactly a map plus a doubly linked list under the hood. In interviews, you're usually asked to build it yourself — mention the built-in, then show you understand what it does.

In Go you'd pair a map[int]*list.Element with the standard container/list doubly linked list; the logic is the same. In production caches, the harder parts are concurrency (many goroutines or threads hitting it at once), memory limits in bytes rather than entry counts, and time-to-live expiry. Libraries like groupcache and Caffeine add sharding and smarter eviction on top of this core.

LRU eviction is everywhere in infra: CDN and reverse-proxy caches, DNS resolver caches, database buffer pools, the Linux page cache (an LRU variant), and in-memory caches in front of slow services. Building one checks that you can combine two data structures to hit an O(1) target, which is a common "build it yourself" interview question.