Problem 9: Design an LRU Cache

The setup

"Implement an LRU cache. Two operations: get(key) and put(key, value). Both must be O(1). Capacity is fixed; when full, evict the least recently used item."

This is a data structure problem, not an OO design problem. But it tests whether you understand the right combination of structures to achieve O(1) for both operations.

The data structure

flowchart LR
    subgraph HM["Hash Map: key → Node*"]
        HMA["'A' →"]
        HMB["'B' →"]
        HMC["'C' →"]
        HMD["'D' →"]
    end
    H((Head)) --next--> NA["A"]
    NA --next--> NB["B"]
    NB --next--> NC["C"]
    NC --next--> ND["D"]
    ND --next--> T((Tail))
    T --prev--> ND
    ND --prev--> NC
    NC --prev--> NB
    NB --prev--> NA
    NA --prev--> H
    HMA -.-> NA
    HMB -.-> NB
    HMC -.-> NC
    HMD -.-> ND

get(key): O(1) via hash map; move accessed node to head. put(key, val): O(1) insert at head; if over capacity, evict the node just before tail.

A hashmap alone: O(1) lookup but no concept of "least recently used."

A linked list alone: can maintain recency order but O(n) lookup.

Combined: hashmap (key → node) + doubly-linked list (recency order). The hashmap gives O(1) access; the list gives O(1) reordering on access.

class LRUCache {
  private final int capacity;
  private final Map> map;
  private final Node head, tail;  // sentinels; head = most recent; tail = least recent
  
  public LRUCache(int capacity) {
    this.capacity = capacity;
    this.map = new HashMap<>();
    this.head = new Node<>(null, null);
    this.tail = new Node<>(null, null);
    head.next = tail;
    tail.prev = head;
  }
  
  public V get(K key) {
    Node node = map.get(key);
    if (node == null) return null;
    moveToFront(node);
    return node.value;
  }
  
  public void put(K key, V value) {
    Node existing = map.get(key);
    if (existing != null) {
      existing.value = value;
      moveToFront(existing);
      return;
    }
    if (map.size() >= capacity) {
      // Evict LRU: tail.prev is the least recently used
      Node lru = tail.prev;
      removeNode(lru);
      map.remove(lru.key);
    }
    Node newNode = new Node<>(key, value);
    addToFront(newNode);
    map.put(key, newNode);
  }
  
  private void moveToFront(Node node) {
    removeNode(node);
    addToFront(node);
  }
  
  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 static class Node {
    K key;
    V value;
    Node prev, next;
    Node(K k, V v) { key = k; value = v; }
  }
}

Cross-examination round 1: thread-safety

Cross-examination round 2: alternative — Java's LinkedHashMap

class LRUCache extends LinkedHashMap {
  private final int capacity;
  public LRUCache(int capacity) {
    super(capacity, 0.75f, true);  // accessOrder = true
    this.capacity = capacity;
  }
  protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > capacity;
  }
}

Takeaway

LRU cache is the textbook problem for "combine two data structures to get the best of both." HashMap + DoublyLinkedList → O(1) for both operations. Recognising this pattern (and being able to implement it cleanly) is a baseline expectation for senior engineers. The variant question — "what about LFU?" — has its own elegant solution (HashMap + buckets per frequency).