Design an LRU cache

Step 1 Understand it

Why interviewers ask this. It tests data-structure design under a strict time limit (O(1) operations), and it's asked both as a coding question and as a design question.

Watch it happen

Requirements

Classes

• LRUCache: capacity, a hash map from key to node, and a doubly linked list.
• Node: key, value, previous, next.

Patterns used

• Composition (map plus list)
• Strategy, if the eviction policy should be swappable

Start simple, then scale

1. Naive: a list kept in order of use. get is O(n), because you must find and move the item.
2. Better: a dictionary for lookups, but keeping the order still costs O(n).
3. Final: a dictionary plus a doubly linked list, so both operations are O(1).
4. Extensions: a TTL per entry, thread safety, or LFU instead of LRU.

Picture it

flowchart LR
  H["head<br/>(dummy)"] <--> N3["key 3<br/>most recent"] <--> N1["key 1"] <--> T["tail<br/>(dummy)"]
  M[("Hash map<br/>key → node")] -.-> N3
  M -.-> N1

The design, step by step

1. A hash map finds a key's node in O(1).
2. A doubly linked list keeps items in order of use: most recent at the front, least recent at the back.
3. get: move the node to the front. put: update and move to the front, or insert at the front and remove the back node if over capacity.

Deep dives

• Dummy head and tail nodes remove the edge cases.
• Thread safety: one lock around get and put (or several locks for parts of the cache).
• In Python, OrderedDict with move_to_end does the same in a few lines; know both versions.

Common mistakes

• A singly linked list, which can't remove a node in O(1).
• Forgetting to update the order on get.
• Forgetting to delete the evicted key from the dictionary.

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

class LRUCache:
    def __init__(self, capacity):
        self.cap, self.map = capacity, {}
        self.head, self.tail = Node(), Node()        # dummy ends
        self.head.next, self.tail.prev = self.tail, self.head

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

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

    def get(self, key):
        if key not in self.map:
            return None
        node = self.map[key]
        self._remove(node)
        self._add_front(node)
        return node.val

    def put(self, key, val):
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, val)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

Step 2 Go further (free, optional)

Optional. The notes above are written to be enough on their own. These free resources give a second explanation and extra practice.

• Watch

  LRU Cache solution

  NeetCode

• Code

  146. LRU Cache

  LeetCode

Step 3 Practise

Try each exercise yourself first: on paper, out loud or in code. Then open the answer and compare it with yours.

1. ExplainSay it in plain words in under a minute, with no notes.

   Explain why you need both a hash map and a doubly linked list.

   Show answer

   An LRU cache needs two things to be fast:
   1. Find an item by its key: is "user:42" in the cache?
   2. Know the order of use, and change it cheaply: move an item to "most recently used" on every get, and remove the least recently used one when full.

   A hash map does the first in O(1), but has no useful order. A list keeps the order, but finding a key in it takes O(n). So you use both: the map goes from key to the item's node in the list, and the list keeps the nodes in order of use.

   Why doubly linked: to move a node to the front, you must unlink it from wherever it is in the middle, which means fixing its neighbours' pointers. With a link back to the previous node, that is O(1). A singly linked list would have to walk from the start to find the previous node, which is O(n). The back of the list (just before the tail sentinel) is always the least recently used item, so eviction is O(1) too.

2. DrawSketch the diagram (or class diagram) from memory.

   Draw the list after put(1), put(2), get(1), put(3), with capacity 2.

   Show answer

   Front means most recently used. get(1) moves node 1 to the front, so node 2 becomes the least recently used, and it is the one evicted when put(3) overflows the capacity of 2. The map always points at exactly the nodes in the list.

   textCopy

   Capacity 2. Front of the list = most recently used.
   
   put(1):  head ⇄ [1:a] ⇄ tail
   put(2):  head ⇄ [2:b] ⇄ [1:a] ⇄ tail
   get(1):  head ⇄ [1:a] ⇄ [2:b] ⇄ tail     1 moves to the front
   put(3):  head ⇄ [3:c] ⇄ [1:a] ⇄ tail     full: 2 (at the back)
                                            is evicted
   map after put(3): {1 → node 1, 3 → node 3}

3. ApplyUse it in a real design question and say exactly where it fits.

   Implement it from memory, then again with OrderedDict, and test both with the same sequence of calls.

   Show answer

   The first version is the lesson's hash map plus doubly linked list. The second uses OrderedDict, which is exactly that structure built in: move_to_end() marks a key as most recent, and popitem(last=False) removes the oldest.

   Both run the same sequence of calls and give the same results. A second check runs 10,000 random gets and puts against both, with a fixed seed, and confirms they always agree.

   pythonCopy

   import random
   from collections import OrderedDict
   
   
   class Node:
       def __init__(self, key=None, val=None):
           self.key, self.val, self.prev, self.next = key, val, None, None
   
   
   class LRUCache:                                  # from memory: hash map + doubly linked list
       def __init__(self, capacity):
           self.cap, self.map = capacity, {}
           self.head, self.tail = Node(), Node()
           self.head.next, self.tail.prev = self.tail, self.head
   
       def _remove(self, node):
           node.prev.next, node.next.prev = node.next, node.prev
   
       def _add_front(self, node):
           node.prev, node.next = self.head, self.head.next
           self.head.next.prev = node
           self.head.next = node
   
       def get(self, key):
           if key not in self.map:
               return None
           node = self.map[key]
           self._remove(node)
           self._add_front(node)
           return node.val
   
       def put(self, key, val):
           if key in self.map:
               self._remove(self.map[key])
           node = Node(key, val)
           self.map[key] = node
           self._add_front(node)
           if len(self.map) > self.cap:
               lru = self.tail.prev
               self._remove(lru)
               del self.map[lru.key]
   
   
   class OrderedLRU:                                # the same with OrderedDict
       def __init__(self, capacity):
           self.cap, self.data = capacity, OrderedDict()
   
       def get(self, key):
           if key not in self.data:
               return None
           self.data.move_to_end(key)               # most recent at the end
           return self.data[key]
   
       def put(self, key, val):
           self.data[key] = val
           self.data.move_to_end(key)
           if len(self.data) > self.cap:
               self.data.popitem(last=False)        # least recent is at the start
   
   
   def run(cache, ops):
       return [cache.get(op[1]) if op[0] == "get" else cache.put(op[1], op[2]) for op in ops]
   
   
   ops = [("put", 1, "a"), ("put", 2, "b"), ("get", 1), ("put", 3, "c"), ("get", 2),
          ("get", 3), ("put", 1, "A"), ("put", 4, "d"), ("get", 3), ("get", 1), ("get", 4)]
   gets = [r for op, r in zip(ops, run(LRUCache(2), ops)) if op[0] == "get"]
   print(gets)                                      # ['a', None, 'c', None, 'A', 'd']
   print(run(LRUCache(2), ops) == run(OrderedLRU(2), ops))   # True
   
   random.seed(0)
   ops = [("get", random.randrange(20)) if random.random() < 0.5 else ("put", random.randrange(20), i)
          for i in range(10_000)]
   print(run(LRUCache(5), ops) == run(OrderedLRU(5), ops))   # True: 10,000 random calls agree

4. Trade-offsSay what it costs, when not to use it, and the alternative.

   How would you make it thread-safe, and what does that cost?

   Show answer

   The simple way: one lock around both get and put. get has to be inside the lock too, because it changes the list (it moves the node to the front); two threads moving nodes at once would corrupt the pointers. (Python's GIL doesn't help: a get is many steps, and a thread can switch between them.)

   What it costs:
   • Every operation, even a read, waits its turn, so under heavy concurrency the cache handles one request at a time and threads queue at the lock.
   • A read-write lock doesn't help, because every get is a write to the order.

   Ways to reduce the cost:
   • Shard it: N independent LRU caches, each with its own lock, chosen by a hash of the key. Contention drops by about N; the price is that eviction is only "least recently used" within each shard.
   • Approximate the order: record reads in a buffer and apply them in batches (as Java's Caffeine does), or use a CLOCK-style "recently used" bit instead of moving nodes. Redis samples a few keys and evicts the oldest of them.
   • Use a well-tested concurrent cache library instead of writing your own.

Step 4 Interview-ready, then prove it

Your interview answer

About 20 to 40 seconds, said out loud. Practise it until it sounds like you, not like notes.

A hash map from key to node gives O(1) lookup, and a doubly linked list keeps items in order of use. get moves the node to the front; put inserts at the front and removes the back node when over capacity. Dummy head and tail nodes keep the code simple.

Follow-up questions

Tick each check when you can do it without notes