Cache design

Overview

Designing an in-memory cache is a classic machine-coding question: implement get(key) and put(key, value) in O(1) with a capacity limit and an eviction policy, usually LRU (least recently used). The standard solution combines a hash map (key to node) with a doubly linked list ordered by recency; get moves a node to the front, put inserts at the front and evicts from the tail when full.

A strong LLD answer goes further: pluggable eviction policies (LRU, LFU, FIFO) via Strategy, TTL expiry, thread safety, statistics (hit rate), and a clean generic interface Cache<K, V>. These extensions show design skill beyond the data structure itself.

When to use it

• Interview prompts: 'Design an LRU cache' or 'Design a cache with eviction policies'.
• Memoizing expensive computations or remote calls.
• Bounded memory with hot data reused often.

Where it shows up in interviews

Where it is used in real software

Key terms

Eviction policy

Rule choosing which entry to remove when full.

LRU / LFU / FIFO

Least recently used / least frequently used / first in, first out.

TTL

Entry expires after a time.

Hit rate

Fraction of gets served from the cache.

Doubly linked list

O(1) move and remove when you hold the node.

How it works, step by step

1. 1
   Define the interface

   get(key), put(key, value), size(), optional ttl.

2. 2
   Map for O(1) lookup

   key -> node.

3. 3
   Linked list for recency

   Head = most recent, tail = eviction candidate.

4. 4
   Extract eviction as a strategy

   EvictionPolicy with keyAccessed and evict.

5. 5
   Add thread safety and TTL

   Lock or striped locks; expiry on read and background cleanup.

Operation trace

LRU capacity 2

Every operation is O(1): one map lookup and a constant number of pointer changes.

Implementation

1import java.util.*;2import java.util.concurrent.locks.ReentrantLock;3 4public final class LruCache<K, V> {5    private final class Node {6        final K key; V value; Node prev, next;7        Node(K key, V value) { this.key = key; this.value = value; }8    }9 10    private final int capacity;11    private final Map<K, Node> map = new HashMap<>();12    private final Node head = new Node(null, null), tail = new Node(null, null); // sentinels13    private final ReentrantLock lock = new ReentrantLock();14    private long hits, misses;15 16    public LruCache(int capacity) {17        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");18        this.capacity = capacity;19        head.next = tail; tail.prev = head;20    }21 22    public Optional<V> get(K key) {23        lock.lock();24        try {25            Node n = map.get(key);26            if (n == null) { misses++; return Optional.empty(); }27            hits++;28            moveToFront(n);29            return Optional.of(n.value);30        } finally { lock.unlock(); }31    }32 33    public void put(K key, V value) {34        lock.lock();35        try {36            Node n = map.get(key);37            if (n != null) { n.value = value; moveToFront(n); return; }38            if (map.size() == capacity) {39                Node lru = tail.prev;40                unlink(lru);41                map.remove(lru.key);42            }43            n = new Node(key, value);44            map.put(key, n);45            addFront(n);46        } finally { lock.unlock(); }47    }48 49    public double hitRate() { long total = hits + misses; return total == 0 ? 0 : (double) hits / total; }50 51    private void moveToFront(Node n) { unlink(n); addFront(n); }52    private void unlink(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }53    private void addFront(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }54}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Using an array or list scan for recency.

  Fix: That makes operations O(n); use a linked list with node references.

• Forgetting to update the value and recency on put of an existing key.

  Fix: Update and move to front.

• Not removing the evicted key from the map.

  Fix: Store the key in the node so eviction can delete it.

Interview questions

Practice problems