LRU Cache (LeetCode 146)

Requirements

Implement a Least Recently Used (LRU) cache supporting get and put operations in $O(1)$ time.

• get(key): Returns the value if $key$ exists and marks the entry as most recently used; otherwise, returns -1.
• put(key, value): Inserts or updates the key-value pair. If capacity is exceeded, evicts the least recently used entry.

Core Architecture

To achieve $O(1)$ for both operations, we combine two structures:

• HashMap: Provides $O(1)$ node lookup via key.
• Doubly Linked List: Provides $O(1)$ node insertion and removal at any position.
  • Head: Points to the Most Recently Used (MRU) node.
  • Tail: Points to the Least Recently Used (LRU) node.

[Head Sentinal] <-> [Newest Node] <-> ... <-> [Oldest Node] <-> [Tail Sentinal]

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0); // Sentinel head
    private final Node tail = new Node(0, 0); // Sentinel tail

    static class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { this.key = k; this.val = v; }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        moveToFront(node);
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            moveToFront(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            addToFront(node);
            if (map.size() > capacity) {
                Node lruNode = removeLast();
                map.remove(lruNode.key);
            }
        }
    }

    private void addToFront(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToFront(Node node) {
        removeNode(node);
        addToFront(node);
    }

    private Node removeLast() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
}

The LinkedHashMap Alternative (Java Only)

Java's LinkedHashMap provides a built-in LRU implementation when constructed with accessOrder=true.

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private final int capacity;

    public LRUCache(int capacity) {
        // accessOrder=true enables LRU behavior
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

[!TIP] In systems programming, understanding the manual Doubly Linked List implementation is critical. While LinkedHashMap provides a ready-to-use alternative in Java, relying on it blindly obscures the true mechanics of eviction.

LFU Cache (LeetCode 460)

LFU (Least Frequently Used) evicts the item with the smallest access frequency. If multiple items share the same minimum frequency, the LRU item among them is evicted.

Design Logic: We maintain three maps for $O(1)$ access:

1. keyVal: Maps key to value.
2. keyFreq: Maps key to its access frequency.
3. freqKeys: Maps frequency to an ordered set (LinkedHashSet) of keys.

class LFUCache {
    private final int capacity;
    private int minFreq = 0;
    private final Map<Integer, Integer> keyVal = new HashMap<>();
    private final Map<Integer, Integer> keyFreq = new HashMap<>();
    private final Map<Integer, LinkedHashSet<Integer>> freqKeys = new HashMap<>();

    public LFUCache(int capacity) { this.capacity = capacity; }

    public int get(int key) {
        if (!keyVal.containsKey(key)) return -1;
        updateFrequency(key);
        return keyVal.get(key);
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;
        if (keyVal.containsKey(key)) {
            keyVal.put(key, value);
            updateFrequency(key);
            return;
        }
        if (keyVal.size() >= capacity) {
            evictMinFreq();
        }
        keyVal.put(key, value);
        keyFreq.put(key, 1);
        freqKeys.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }

    private void updateFrequency(int key) {
        int freq = keyFreq.get(key);
        keyFreq.put(key, freq + 1);
        freqKeys.get(freq).remove(key);
        if (freqKeys.get(freq).isEmpty()) {
            freqKeys.remove(freq);
            if (minFreq == freq) minFreq++;
        }
        freqKeys.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
    }

    private void evictMinFreq() {
        LinkedHashSet<Integer> keys = freqKeys.get(minFreq);
        int lruKey = keys.iterator().next(); // First element in LinkedHashSet is oldest
        keys.remove(lruKey);
        if (keys.isEmpty()) freqKeys.remove(minFreq);
        keyVal.remove(lruKey);
        keyFreq.remove(lruKey);
    }
}

筋