Skip to main content

67. LRU Cache

mediumAsked at Workday

Design an LRU cache with O(1) get and put. Workday uses this for hash-map + doubly-linked-list composition — same shape as caching the most-recently-viewed employee records in an HR app.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday SDE2 onsite — design canonical.
  • Blind (2025)— Workday Pleasanton — every backend round.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(capacity), get(key), put(key, value). The functions must each run in O(1) average time complexity.

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","put","put","get","put","get","put","get","get","get"], [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output
[null,null,null,1,null,-1,null,-1,3,4]

Approaches

1. Hash map + ordered insertion-time array

Hash map for value; array for access order.

Time
get O(n), put O(n)
Space
O(n)
// updating access order requires array shift

Tradeoff: O(n) on access reordering — violates O(1).

2. Hash map + doubly-linked list

DLL for O(1) move-to-front + evict-from-tail. Hash map for O(1) key -> node lookup.

Time
O(1) all ops
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;
  }
  _addToFront(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._addToFront(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._addToFront(node);
    } else {
      if (this.map.size === this.cap) {
        const lru = this.tail.prev;
        this._remove(lru);
        this.map.delete(lru.key);
      }
      const node = { key, val: value, prev: null, next: null };
      this._addToFront(node);
      this.map.set(key, node);
    }
  }
}

Tradeoff: Sentinel head/tail nodes avoid null checks. _remove and _addToFront are the only two list operations needed.

Workday-specific tips

Workday LOVES this question. Use sentinel head/tail nodes — they eliminate null checks. Mention that JavaScript's Map preserves insertion order, so a Map-only solution is possible (but Workday usually wants the explicit DLL to see you understand the data structure).

Common mistakes

  • Forgetting to evict on insert when at capacity.
  • Not removing the key from the map when evicting from the DLL.
  • Updating value on existing key but forgetting to move-to-front.

Follow-up questions

An interviewer at Workday may pivot to one of these next:

  • LFU Cache (LC 460).
  • Map-only JS solution using insertion-order property.
  • What if expiration is involved (TTL)?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Sentinels?

Dummy head and tail nodes. Every real node has both prev and next non-null — no null checks in _remove and _addToFront.

Map alternative?

JS Map preserves insertion order. You can delete + re-insert to refresh. Same O(1) behavior with less code. Mention both.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →