LRU Cache

MediumHash Table Linked List Design

A photo app keeps recently viewed thumbnails in a small in-memory cache so that scrolling back is instant. When the cache is full and another thumbnail has to be stored, the app throws out the entry that has gone unused for the longest time.

Implement the LRUCache class:

LRUCache(capacity) creates an empty cache that holds at most capacity entries.
get(key) returns the value stored under key, or -1 if that key is not cached.
put(key, value) stores value under key, overwriting any earlier value. If this adds a new key and the cache now holds more than capacity entries, evict the least recently used entry.

A key counts as used whenever put writes it or get finds it; a get for a missing key changes nothing. Both operations must take O(1) time on average.

Example 1

Input: ["LRUCache","put","put","get","put","get","get","get"]
[[2],[7,70],[3,30],[7],[9,90],[3],[9],[7]]
Output: [null,null,null,70,null,-1,90,70]

Explanation: Reading key 7 makes key 3 the least recently used entry, so storing key 9 evicts key 3.

Example 2

Input: ["LRUCache","put","put","put","put","get","put","get","get","get"]
[[3],[1,100],[2,200],[3,300],[1,111],[2],[4,400],[1],[3],[4]]
Output: [null,null,null,null,null,200,null,111,-1,400]

Explanation: Overwriting key 1 and then reading key 2 leave key 3 as the least recently used, so adding key 4 evicts it. Key 1 keeps its new value 111.

Constraints

capacity is between 1 and 3000.
Keys are integers from 0 to 10^4, and values are integers from 0 to 10^5.
A test makes at most 200,000 calls to get and put combined.

💡 Hint 1

A hash map gives O(1) lookup, but it does not remember which key was used least recently. What structure can reorder items in O(1)?

💡 Hint 2

Keep the entries in a doubly linked list ordered by recency, and let the map point at the list nodes so you can unlink any entry instantly.

💡 Hint 3

Sentinel head and tail nodes remove the empty-list edge cases. In JavaScript, a Map already iterates in insertion order, which you can exploit.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Combine a hash map with a doubly linked list ordered by recency. The list runs from least recently used (just after a sentinel head) to most recently used (just before a sentinel tail), and the map sends each key to its list node. get looks the node up, unlinks it and re-inserts it before tail. put either updates an existing node and moves it the same way, or appends a new node; if that pushes the size past capacity, it removes the node right after head and deletes its key from the map. Every step touches a constant number of pointers.

In JavaScript, a Map iterates keys in insertion order, so deleting and re-setting a key moves it to the "most recent" end, and map.keys().next().value is the least recently used key. That gives the same O(1) behavior with much less code.

Time O(1) average per operationSpace O(capacity)

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const value = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, value);
    return value;
  }
  put(key, value) {
    this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      this.map.delete(this.map.keys().next().value);
    }
  }
}

class LRUCache {
    private static class Node {
        int key, 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), tail = new Node(0, 0);

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

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

    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            node.value = value;
            unlink(node);
            append(node);
            return;
        }
        node = new Node(key, value);
        map.put(key, node);
        append(node);
        if (map.size() > capacity) {
            Node lru = head.next;
            unlink(lru);
            map.remove(lru.key);
        }
    }

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

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

class LRUCache {
  /** @param {number} capacity */
  constructor(capacity) {

  }

  /**
   * @param {number} key
   * @return {number}
   */
  get(key) {

  }

  /**
   * @param {number} key
   * @param {number} value
   * @return {void}
   */
  put(key, value) {

  }
}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit