Skip to main content

23. LRU Cache

mediumAsked at GitHub

Design an O(1) get/put LRU cache using a doubly-linked list plus hashmap — the exact caching strategy used in GitHub's object store and pack-file cache layers.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Design a data structure that follows the Least Recently Used cache constraint with get(key) and put(key, value) both running in O(1) time. Evict the least recently used item when capacity is exceeded.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key, value <= 10^4
  • At most 2×10^5 calls to get and put

Examples

Example 1

Input
LRUCache(2); put(1,1); put(2,2); get(1)=1; put(3,3); get(2)=-1; get(3)=3
Output
[1, -1, 3]

Example 2

Input
LRUCache(1); put(2,1); get(2)=1; put(3,2); get(2)=-1; get(3)=2
Output
[1, -1, 2]

Approaches

1. Ordered map / array scan

Keep an array of (key, value) pairs sorted by recency; scan for key on get, shift elements on put.

Time
O(n) per operation
Space
O(n)
// Array splice to move accessed item to front
// get/put both O(n) — fails capacity/time requirements

Tradeoff:

2. HashMap + Doubly Linked List

A dummy head/tail doubly-linked list keeps recency order; a HashMap gives O(1) node lookup. get moves a node to MRU position; put inserts at MRU and evicts LRU (tail.prev) when over capacity.

Time
O(1) amortized
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.head = {key:0,val:0,prev:null,next:null};
    this.tail = {key:0,val:0,prev:null,next:null};
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  _insertMRU(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node); this._insertMRU(node);
    return node.val;
  }
  put(key, val) {
    if (this.map.has(key)) this._remove(this.map.get(key));
    const node = {key, val};
    this._insertMRU(node);
    this.map.set(key, node);
    if (this.map.size > this.cap) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
  }
}

Tradeoff:

GitHub-specific tips

GitHub's git object cache and pack-index reads use LRU semantics; connect your solution to how GitHub avoids re-reading cold packfiles by evicting infrequently-accessed repo objects first.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill LRU Cache and other GitHub interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →