LRU cache

Q: Can I just use OrderedDict or LinkedHashMap?

In production, yes. Python's OrderedDict.move_to_end plus popitem(last=False), or Java's LinkedHashMap with accessOrder=true and an overridden removeEldestEntry, give the same O(1) behaviour in a few lines. In an interview, mention them first, then build the linked list, because the list is what is being tested.

Q: How would this look in Go, and in production?

In Go you would pair a map[K]*list.Element with container/list from the standard library, which is already a doubly linked list, and guard both with a sync.Mutex. Note that get also writes, because it reorders the list, so a sync.RWMutex read lock is not enough. Production caches often shard the key space across several LRUs, each with its own lock, to cut contention, and export hit, miss and eviction counters as metrics.

mediumCaches Must-do

Build a fixed-size cache that throws away the least recently used entry when it is full. This is the eviction policy behind many in-process caches, for example a cache of resolved DNS names or parsed config files in a long-running agent.

API (Python names shown; Java uses the same names, with generics LRUCache<K, V>)

◈ DIAGRAM

LRUCache(capacity: int)
get(key) -> value or None
put(key, value) -> evicted key or None
size() -> int

Rules

capacity must be at least 1; otherwise raise ValueError (Java: IllegalArgumentException).
get returns the value, or None (Java null) if the key is absent. A successful get makes the key the most recently used.
put on an existing key updates its value, makes it most recently used, and never evicts anything.
put on a new key when the cache is full first removes the least recently used key, then inserts. It returns the evicted key so the caller can log or count evictions. Otherwise it returns None.
get and put must both run in O(1) time.
You may not use a built-in ordered map (OrderedDict, LinkedHashMap) for the main solution. Interviewers want to see the linked list.

Outputs below show the return value of every call after the constructor, one per line.

Examples

Example 1

Input: c = LRUCache(2) c.put("a", 1) c.put("b", 2) c.get("a") c.put("c", 3) c.get("b") c.put("a", 10) c.get("a") c.size()

Output: null null 1 b null null 10 2

Explanation: Reading "a" makes "b" the least recently used, so inserting "c" evicts "b". Updating "a" does not evict anything.

Example 2

Input: c = LRUCache(1) c.put("x", 1) c.put("y", 2) c.get("x") c.get("y") LRUCache(0)

Output: null x null 2 error: capacity must be at least 1

Explanation: With capacity 1 every new key evicts the previous one. A capacity of 0 is rejected at construction.

Hints

Approach

Combine a hash map with a doubly linked list:

The list holds entries in recency order: right after the head sentinel is the most recently used, right before the tail sentinel is the least recently used.
The map goes from key to list node, so you can find any entry in O(1) and unlink it in O(1) because each node knows its neighbours.

Steps:

get: look up the node. If missing, return None. Otherwise unlink it, push it right after head, return its value.
put on an existing key: update the value and move the node to the front.
put on a new key: if the map is full, the victim is tail.prev. Unlink it and delete its key from the map. That is why each node stores its key. Then create the new node, add it to the map, push it to the front.

The two sentinel nodes mean the list is never empty, so _unlink and _push_front need no null checks.

ComplexityTime O(1) per get/putSpace O(capacity)

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):
        if capacity < 1:
            raise ValueError("capacity must be at least 1")
        self.capacity = capacity
        self.map = {}                      # key -> node
        self.head, self.tail = _Node(), _Node()   # sentinels: head.next is MRU, tail.prev is LRU
        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.prev, node.next = self.head, self.head.next
        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):
        """Insert or update. Returns the evicted key, or None."""
        node = self.map.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return None
        evicted = None
        if len(self.map) == self.capacity:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]
            evicted = lru.key
        node = _Node(key, value)
        self.map[key] = node
        self._push_front(node)
        return evicted
 
    def size(self):
        return len(self.map)

Follow-up questions

Make it thread-safe. Why does get need an exclusive lock, not a read lock?
Bound the cache by total bytes instead of entry count. What changes in put?
Add a TTL so stale entries expire even if they are popular (see the next problem).

Frequently asked questions

In production, yes. Python's OrderedDict.move_to_end plus popitem(last=False), or Java's LinkedHashMap with accessOrder=true and an overridden removeEldestEntry, give the same O(1) behaviour in a few lines. In an interview, mention them first, then build the linked list, because the list is what is being tested.

In Go you would pair a map[K]*list.Element with container/list from the standard library, which is already a doubly linked list, and guard both with a sync.Mutex. Note that get also writes, because it reorders the list, so a sync.RWMutex read lock is not enough. Production caches often shard the key space across several LRUs, each with its own lock, to cut contention, and export hit, miss and eviction counters as metrics.

Agents, proxies and control-plane services keep bounded caches everywhere: DNS results, auth tokens, compiled templates. The question checks that you can bound memory, pick an eviction policy on purpose, and hit O(1) with the right pair of data structures.

Problem statement