Skip to main content

146. LRU Cache

mediumAsked at IBM

LRU Cache is IBM's data-structure-design screener — relevant to IBM Cloud / DB2 / storage teams where eviction policies matter daily. The interviewer is grading whether you reach for hash map + doubly linked list together, articulate why neither suffices alone, and ship O(1) for both get and put.

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

Source citations

Public interview reports confirming this problem appears in IBM loops.

  • Glassdoor (2026-Q1)— IBM Cloud-engineering and SWE-3+ onsite recurring design problem.
  • LeetCode (2026-Q1)— Top-15 IBM-tagged problem (medium tier).
  • GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive.
  • Blind (2025-11)— Multiple IBM SWE-3 onsite recap threads cite LRU as the data-structure design round.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with: LRUCache(int capacity), int get(int key), and void put(int key, int value). Both operations must 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(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)
Output
[null,null,null,1,null,-1,null,-1,3,4]

Explanation: After put(3,3), key 2 is evicted because it was least recently used.

Approaches

1. JavaScript Map (insertion-ordered)

JS Map preserves insertion order. delete + set on get to refresh recency; iterate keys to find LRU on eviction.

Time
O(1) average get, O(1) average put
Space
O(capacity)
class LRUCacheMap {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, val);
    return val;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    else if (this.map.size >= this.capacity) {
      const oldest = this.map.keys().next().value;
      this.map.delete(oldest);
    }
    this.map.set(key, value);
  }
}

Tradeoff: Ships in 15 lines if the language gives you insertion-ordered maps. Most interviewers accept this as the optimal because the underlying complexity is the same. Mention it before the doubly-linked-list version to acknowledge you saw the language feature.

2. Doubly linked list + hash map (canonical)

Map from key to node pointer + doubly linked list with sentinel head/tail. Move-to-front on get/put. Evict from tail when full.

Time
O(1) worst-case get, O(1) worst-case put
Space
O(capacity)
class Node {
  constructor(key, val) {
    this.key = key;
    this.val = val;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = new Node(0, 0); // most recent end
    this.tail = new Node(0, 0); // least recent end
    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);
      return;
    }
    if (this.map.size >= this.capacity) {
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.key);
    }
    const node = new Node(key, value);
    this.map.set(key, node);
    this._addToFront(node);
  }
}

Tradeoff: The textbook answer and what most interviewers expect when they say 'don't rely on language built-ins.' Sentinel head/tail nodes eliminate the null-check branches that break candidates under time pressure.

IBM-specific tips

IBM grades LRU Cache on two axes: (1) you reach for both data structures together AND can explain WHY neither alone works (hash map has O(1) lookup but no order; linked list has order but O(n) lookup), (2) you use sentinel head/tail nodes to eliminate edge cases. Bringing up sentinels unprompted earns the senior-bar checkbox. If you forget them and the interviewer points out a null deref, you can recover, but the unforced error costs the 'strong yes' rating.

Common mistakes

  • Using a singly linked list — you need O(1) node removal, which requires the prev pointer.
  • Forgetting to remove the evicted key from the hash map (memory leak).
  • Off-by-one on capacity check: should evict when size >= capacity, BEFORE insert, not after.
  • Forgetting that put on an existing key counts as access — recency must refresh.
  • Mixing up head and tail conventions — pick one (head = most-recent, tail = LRU) and document it inline.

Follow-up questions

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

  • Make it thread-safe — what about read/write locks?
  • Add TTL (time-to-live) per key — store an expiry timestamp on each node.
  • Implement LFU (Least Frequently Used) instead (LeetCode 460).
  • What if you also need O(1) for getMostRecent() and getLeastRecent() snapshots?
  • Distributed LRU — what changes when the cache spans multiple machines?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why not just use an array?

Move-to-front on an array is O(n) because you have to shift elements. The hash map gives O(1) lookup by key; the doubly linked list gives O(1) splice. Combining both is the only way to get O(1) for BOTH operations.

Will IBM accept the JavaScript Map shortcut?

It depends on the interviewer. Some count it as the elegant answer; others ask for the underlying data structures explicitly. The safe play is to mention both: 'I can ship the Map version in five lines, but the doubly-linked-list + hash-map version shows the underlying mechanism.' Volunteer to write both if asked.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →