CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 4 of 6 · 3 min read

The code

Unlink, add to front, evict from the back.

class LruCache<K, V> {
    private class Node { K key; V val; Node prev, next; Node(K k, V v) { key = k; val = v; } }

    private final int capacity;
    private final Map<K, Node> map = new HashMap<>();
    private final Node head = new Node(null, null), tail = new Node(null, null);
    private long hits, misses;

    LruCache(int capacity) {
        if (capacity < 1) throw new IllegalArgumentException("capacity must be at least 1");
        this.capacity = capacity; head.next = tail; tail.prev = head;
    }

    private void unlink(Node n)   { n.prev.next = n.next; n.next.prev = n.prev; }
    private void addFront(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }

    synchronized Optional<V> get(K key) {
        Objects.requireNonNull(key);
        Node n = map.get(key);
        if (n == null) { misses++; return Optional.empty(); }
        hits++; unlink(n); addFront(n);
        return Optional.of(n.val);
    }

    synchronized void put(K key, V val) {
        Objects.requireNonNull(key); Objects.requireNonNull(val);
        Node n = map.get(key);
        if (n != null) { n.val = val; unlink(n); addFront(n); return; }
        if (map.size() == capacity) {                 // full: evict the oldest
            Node lru = tail.prev; unlink(lru); map.remove(lru.key);
        }
        n = new Node(key, val); map.put(key, n); addFront(n);
    }
}

Each public method does a constant number of map operations and pointer changes, so both are constant time. Absent values come back as Optional, never as null (Level 5, module 1). Nulls are refused at the door, so a null value cannot be mistaken for a miss.

A run with capacity 2:

Step Cache, newest first Note
put a=1, put b=2 b, a
get a a, b a moves to the front
put c=3 c, a b was oldest, so b is evicted
get b c, a a miss
put a=10, get a a, c updating a moves it to the front, size stays 2
Counters 1 hit, 1 miss from the get a and get b calls
Capacity 0 refused "capacity must be at least 1"

Why is get synchronized? In an LRU cache a read changes the order, so it writes to the list. If two threads call get at once without a lock, the pointer changes can interleave and corrupt the list. This is the point of module 3 in Level 5: a method that looks like a read may write. A test with eight threads, each running 20,000 mixed put and get calls on a cache of 100, ends with a size of exactly 100 and a list whose length matches the map.

The built-in shortcut is LinkedHashMap. With its access-order mode on, and an override of removeEldestEntry, it gives the same behaviour in a few lines. It is worth saying in a round that it exists, and that the interviewer usually wants the hand-built version to see the structure.

Check yourself: 1. What are the cache contents after put a, put b, get a, put c with capacity 2? 2. Why does put of an existing key not change the size? 3. Why does get need the lock?