Skip to main content

25. LRU Cache

mediumAsked at Tripadvisor

Design a cache that evicts the least-recently-used entry when capacity is exceeded — Tripadvisor uses LRU caches throughout their recommendation pipeline to keep hot destination and hotel data in memory without unbounded growth.

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

Problem

Design a data structure that follows the Least Recently Used (LRU) cache constraints. Implement the LRUCache class with get(key) returning the value if the key exists (else -1) and put(key, value) inserting or updating the key-value pair, evicting the least recently used key if capacity is exceeded. Both operations must run in O(1) average time.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • At most 2 * 10^5 calls will be made to get and put

Examples

Example 1

Input
LRUCache(2); put(1,1); put(2,2); get(1) → 1; put(3,3) evicts key 2; get(2) → -1; put(4,4) evicts key 1; get(1) → -1; get(3) → 3; get(4) → 4
Output
[null,null,null,1,null,-1,null,-1,3,4]

Approaches

1. Array-based eviction (naive)

Maintain an ordered array of keys tracking recency. On access, move the key to the end. On eviction, remove the first element. O(n) per operation due to array shifts.

Time
O(n)
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.order = [];
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    this.order.splice(this.order.indexOf(key), 1);
    this.order.push(key);
    return this.map.get(key);
  }
  put(key, value) {
    if (this.map.has(key)) this.order.splice(this.order.indexOf(key), 1);
    else if (this.map.size === this.cap) {
      const lru = this.order.shift();
      this.map.delete(lru);
    }
    this.map.set(key, value);
    this.order.push(key);
  }
}

Tradeoff:

2. HashMap + Doubly-Linked List (optimal O(1))

Combine a hash map (O(1) key lookup) with a doubly-linked list (O(1) move-to-front and tail eviction). JavaScript Map preserves insertion order, making this concise.

Time
O(1)
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map(); // Map preserves insertion order
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, val); // refresh to most-recent
    return val;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size === this.cap) {
      this.map.delete(this.map.keys().next().value); // evict LRU (oldest key)
    }
    this.map.set(key, value);
  }
}

Tradeoff:

Tripadvisor-specific tips

Tripadvisor's search and recommendation systems rely heavily on caching hot destination data — this problem is effectively a systems-design warm-up. Interviewers want to see you articulate the doubly-linked list + hash map combo before coding, then note that JavaScript's Map insertion order gives you this for free. In a real implementation they'll ask about thread safety, TTL expiry, and whether you'd use Redis instead — have opinions ready.

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

Practice these live with InterviewChamp.AI →