LRU Cache

Implement a key-value cache with a fixed capacity that, when full, throws out the entry that was used least recently. Write a class LRUCache with:

• LRUCache(capacity): creates an empty cache that holds at most capacity entries.
• get(key): returns the value stored for key, or -1 if the key is not present. A successful lookup counts as a use of that key.
• put(key, value): stores value under key, replacing any old value; this also counts as a use. If adding a new key makes the cache exceed its capacity, first remove the key whose last use is the oldest.

Both get and put must run in O(1) average time.

Each test lists the operations and their arguments; the expected output lists each call's return value (null for the constructor and put).

Example 1

Example 2

Example 3

Constraints

• 1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105
• At most 2 · 105 calls to get and put

Pattern Path · Design · problem 163 of 169

Start simple

Keep a list of keys in use order and search it on every access to move the key to the end: O(capacity) per operation.

The key idea

Two structures work together. A doubly linked list keeps entries ordered by recency: the node right after the head sentinel is the least recently used, the node right before the tail sentinel is the most recent. A hash map sends each key straight to its list node.

• get(key): look up the node. If it exists, unlink it and re-link it just before the tail, then return its value.
• put(key, value): if the key exists, update the value and move the node to the tail end. Otherwise create a node, add it at the tail end and to the map; if the size now exceeds the capacity, unlink the node after the head and delete its key from the map.

Why a doubly linked list? Unlinking a node needs its predecessor, and with a prev pointer that is available in O(1) without scanning. The sentinel nodes mean the list is never empty, so linking and unlinking never need special cases for the first or last element. Each node stores its key so that the evicted node can also be removed from the map.

Many languages offer an ordered map (Python's OrderedDict, JavaScript's insertion-ordered Map) that can do this in a few lines, but interviewers usually want to see the underlying design.

Complexity

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

Python

class Node:
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.nodes = {}  # key -> Node
        # Sentinels: head.next is the least recent, tail.prev the most recent.
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head

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

    def _append(self, node):
        node.prev, node.next = self.tail.prev, self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key: int) -> int:
        node = self.nodes.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._append(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._unlink(node)
            self._append(node)
            return
        node = Node(key, value)
        self.nodes[key] = node
        self._append(node)
        if len(self.nodes) > self.capacity:
            oldest = self.head.next
            self._unlink(oldest)
            del self.nodes[oldest.key]

JavaScript

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.nodes = new Map(); // key -> node
    // Sentinels: head.next is the least recent, tail.prev the most recent.
    this.head = { key: null, value: null, prev: null, next: null };
    this.tail = { key: null, value: null, prev: this.head, next: null };
    this.head.next = this.tail;
  }

  unlink(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  append(node) {
    node.prev = this.tail.prev;
    node.next = this.tail;
    this.tail.prev.next = node;
    this.tail.prev = node;
  }

  get(key) {
    const node = this.nodes.get(key);
    if (node === undefined) return -1;
    this.unlink(node);
    this.append(node);
    return node.value;
  }

  put(key, value) {
    let node = this.nodes.get(key);
    if (node !== undefined) {
      node.value = value;
      this.unlink(node);
      this.append(node);
      return;
    }
    node = { key, value, prev: null, next: null };
    this.nodes.set(key, node);
    this.append(node);
    if (this.nodes.size > this.capacity) {
      const oldest = this.head.next;
      this.unlink(oldest);
      this.nodes.delete(oldest.key);
    }
  }
}

What the interviewer is checking

This is a classic design question: the interviewer checks that you can combine two data structures to meet a strict time bound and implement pointer manipulation without bugs.

Mistakes to avoid

• Forgetting that get also refreshes a key's recency.
• Evicting when updating an existing key, even though the size did not grow.
• Not storing the key in the node, which makes it impossible to delete the evicted entry from the map.

Follow-ups to expect

• How would you make it thread-safe? (Lock, or sharded caches with locks.)
• How would you build an LFU cache instead? (Frequency buckets of linked lists.)
• How would you add time-to-live expiry? (Store timestamps; lazy check on access.)

In real software

Page caches in operating systems, database buffer pools, CDN edge caches and in-process memoisation (for example Python's functools.lru_cache) all evict by least recent use.

Practice next