Skip to main content

29. LRU Cache

mediumAsked at Lyft

Design an O(1) get/put cache that evicts the least-recently-used entry — Lyft runs the exact same LRU structure to cache driver location pings in memory so repeated ETA lookups for the same driver avoid hitting the database.

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 the following operations: LRUCache(int capacity) initializes the LRU cache with positive size capacity. int get(int key) returns the value of the key if the key exists, otherwise -1. void put(int key, int value) updates the value of the key if the key exists. Otherwise, adds the key-value pair to the cache. If the number of keys exceeds the capacity, evict the least recently used key. Both get and put 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); get(2) -> -1; put(4,4); get(1) -> 1; get(3) -> 3; get(4) -> 4
Output
[null,null,null,1,null,-1,null,1,3,4]

Explanation: Capacity is 2. After put(3,3), key 2 is evicted (LRU). After put(4,4), key 3 is evicted because key 1 was accessed more recently.

Approaches

1. Hash map + doubly linked list

Doubly linked list maintains recency order (head = MRU, tail = LRU). Hash map maps key to node for O(1) access. On get/put, move accessed node to head. On eviction, remove tail node and its map entry.

Time
O(1) for both get and put
Space
O(capacity)
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    // Sentinel head (MRU side) and tail (LRU side)
    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;
  }

  _insertFront(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._insertFront(node);
    return node.val;
  }

  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.val = value;
      this._remove(node);
      this._insertFront(node);
    } else {
      if (this.map.size === this.capacity) {
        const lru = this.tail.prev;
        this._remove(lru);
        this.map.delete(lru.key);
      }
      const node = { key, val: value, prev: null, next: null };
      this._insertFront(node);
      this.map.set(key, node);
    }
  }
}

Tradeoff:

Lyft-specific tips

Lyft gives LRU cache as a systems-design-in-code hybrid — they want you to narrate the doubly linked list invariants as you code them. State clearly: 'Head is MRU, tail is LRU. Every access moves the node to head. Every eviction removes the node just before the tail sentinel.' The sentinel pattern eliminates null checks at boundaries. Drawing the list on a whiteboard before coding is strongly encouraged at Lyft.

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

Practice these live with InterviewChamp.AI →