Sizing Thread Pools
with Little's Law.

Start with the behavior.

Implement a fixed-capacity cache of integer keys and values. Every successful access makes that entry the most recently used (MRU). When a new entry exceeds capacity, remove the least recently used (LRU) entry.

Lookup is not ordering.

The invariants to protect

• Every map entry refers to exactly one live list node, and vice versa.
• head.next is MRU; tail.prev is LRU when the cache is nonempty.
• Sentinel nodes are never stored in the map or evicted.
• After each public operation, map.size() ≤ capacity.
• Neighbor pointers agree: node.prev.next == node and node.next.prev == node.

Follow the pointers.

1. Get: find, promote, return.

   Look up the node. On a miss, return -1. On a hit, unlink it, insert it after head, and return its value.

2. Put existing: update in place.

   Change the node’s value and move it to MRU. Size stays the same; no eviction is necessary.

3. Put new: insert, then enforce capacity.

   Add the new node to both structures. If over capacity, unlink tail.prev and remove its key from the map.

Small helpers. Fewer edge cases.

Dummy head and tail nodes make insertion and removal uniform, even when the cache has only one entry. Store the key in each node so eviction can remove its map entry without a search.

import java.util.HashMap;
import java.util.Map;

public final class LRUCache {
    private static final class Node {
        final int key;
        int value;
        Node prev, next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

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

    public LRUCache(int capacity) {
        if (capacity < 1) {
            throw new IllegalArgumentException(
                "Capacity must be positive"
            );
        }
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;

        moveToFront(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToFront(node);
            return;
        }

        Node added = new Node(key, value);
        map.put(key, added);
        insertAtFront(added);

        if (map.size() > capacity) {
            Node victim = tail.prev;
            unlink(victim);
            map.remove(victim.key);
        }
    }

    private void moveToFront(Node node) {
        unlink(node);
        insertAtFront(node);
    }

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

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

This implementation is intentionally not thread-safe. Synchronizing only the map would not protect the list or the cross-structure invariants.

Prove the behavior, not just the code.

“Average” matters: hash map operations are not a strict worst-case O(1) guarantee. No throughput or nanosecond latency claims are needed to establish this design’s complexity.

A minimal test checklist

• Empty cache: get returns -1 without changing state.
• Capacity one: the next distinct insertion evicts the previous entry.
• Existing key: value updates, size stays fixed, and the key becomes MRU.
• Get hit: the accessed key survives the next eviction.
• Get miss: the eviction order remains unchanged.
• Repeated eviction: removed keys are absent from both structures.
• Invalid capacity: construction throws immediately.

put(1, 10)  → [1:10]
put(2, 20)  → [2:20, 1:10]
get(1)      → 10       [1:10, 2:20]
put(3, 30)  → evict 2  [3:30, 1:10]
get(2)      → -1       [3:30, 1:10]
put(1, 99)  → update   [1:99, 3:30]

Order shown: MRU → LRU

Extend only when asked.

The base solution is complete. Keep follow-up discussion local to the cache’s contract and implementation, rather than introducing a distributed architecture.