Skip to main content

22. LRU Cache

mediumAsked at Coursera

Design and implement an LRU cache with O(1) get and put, a data-structure design problem Coursera uses to evaluate caching knowledge relevant to content delivery optimization.

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

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with get(key) returning the value or -1 if absent, and put(key, value) inserting or updating the key, evicting the least recently used key if capacity is exceeded.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • 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
Output
operations return described values

Example 2

Input
LRUCache(1); put(2,1); get(2)->1; put(3,2); get(2)->-1; get(3)->2
Output
operations return described values

Approaches

1. Array-based eviction (O(n) put)

Track insertion order in an array; scan to evict LRU — O(n) put makes this too slow.

Time
O(n) put
Space
O(n)
// Naive: scan array to find LRU — not O(1)
// Skipped for brevity

Tradeoff:

2. HashMap + Doubly Linked List

A HashMap provides O(1) key lookup; a doubly linked list keeps usage order with O(1) move-to-front and O(1) tail eviction. Sentinel head/tail nodes eliminate edge-case null checks.

Time
O(1) get/put
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:this.head,next:null};
    this.head.next = this.tail;
  }
  _remove(n) { n.prev.next = n.next; n.next.prev = n.prev; }
  _addFront(n) { n.next = this.head.next; n.prev = this.head; this.head.next.prev = n; this.head.next = n; }
  get(key) {
    if (!this.map.has(key)) return -1;
    const n = this.map.get(key);
    this._remove(n); this._addFront(n);
    return n.val;
  }
  put(key, value) {
    if (this.map.has(key)) this._remove(this.map.get(key));
    const n = {key, val:value, prev:null, next:null};
    this._addFront(n); this.map.set(key, n);
    if (this.map.size > this.cap) { const lru = this.tail.prev; this._remove(lru); this.map.delete(lru.key); }
  }
}

Tradeoff:

Coursera-specific tips

Coursera interviews emphasize algorithms for educational platforms, content recommendation systems, and scalable delivery pipelines. Medium-difficulty graph and DP problems are typical.

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 Coursera interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →