Skip to main content

17. LRU Cache

mediumAsked at Intuit

Design an LRU (least-recently-used) cache with O(1) get and put. Intuit asks this to test data-structure composition (hash + doubly-linked list) and reframes it as 'cache the last N tax-form lookups' for TurboTax candidates.

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

Source citations

Public interview reports confirming this problem appears in Intuit loops.

  • Glassdoor (2026-Q1)— Intuit SWE II onsite — system-design-flavored coding round.
  • LeetCode Discuss (2025-10)— TurboTax engineer cited LRU as the standard 45-min coding round.

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) initializes the cache with positive size capacity; int get(int key) returns the value of the key if it exists, otherwise return -1; void put(int key, int value) updates the value if the key exists, otherwise add the key-value pair; if the number of keys exceeds capacity, evict the least recently used key. The functions get and put 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(2); put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4);
Output
[1,-1,-1,3,4]

Explanation: put(3,3) evicts key 2; put(4,4) evicts key 1.

Approaches

1. Map with insertion-order iteration

Use JS Map (preserves insertion order). On get, delete and re-set to refresh recency. On put past capacity, delete the first key.

Time
O(1) amortized
Space
O(capacity)
class LRUCache {
  constructor(capacity) { this.cap = capacity; this.map = new Map(); }
  get(key) {
    if (!this.map.has(key)) return -1;
    const v = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, v);
    return v;
  }
  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);
    this.map.set(key, value);
  }
}

Tradeoff: Cleanest in JS — leans on Map's documented insertion-order behavior. Interviewer may want the doubly-linked-list version explicitly.

2. Hash + doubly-linked list (canonical)

Doubly-linked list keeps MRU at head, LRU at tail. Hash map points keys to list nodes for O(1) lookup. Get: lookup + move-to-head. Put: lookup-and-update or insert-at-head + evict tail.

Time
O(1)
Space
O(capacity)
class Node { constructor(k,v){ this.k=k; this.v=v; this.prev=null; this.next=null; } }
class LRUCache {
  constructor(capacity){
    this.cap = capacity;
    this.map = new Map();
    this.head = new Node(); this.tail = new Node();
    this.head.next = this.tail; this.tail.prev = this.head;
  }
  _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.v;
  }
  put(key,value){
    if(this.map.has(key)){
      const n = this.map.get(key); n.v = value;
      this._remove(n); this._addFront(n);
      return;
    }
    if(this.map.size >= this.cap){
      const lru = this.tail.prev;
      this._remove(lru);
      this.map.delete(lru.k);
    }
    const n = new Node(key,value);
    this._addFront(n);
    this.map.set(key, n);
  }
}

Tradeoff: Truly O(1) per operation. Sentinel head/tail nodes eliminate null checks. This is what most interviewers want to see.

Intuit-specific tips

Intuit interviewers will ask whether you'd use the Map shortcut or write the doubly-linked list explicitly — pick the DLL version in a 45-min round to demonstrate the data-structure composition. They grade for sentinel nodes (head/tail) eliminating edge cases. Bonus signal: discuss eviction policy variants (LFU = LC 460, TinyLFU, ARC) and where each wins.

Common mistakes

  • Forgetting to update the recency on get — the cache devolves to FIFO.
  • Using a singly-linked list and getting O(n) remove operations.
  • Forgetting to delete the evicted key from the hash map — memory leak.

Follow-up questions

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

  • LFU Cache — evict by frequency, not recency (LC 460).
  • Make the cache thread-safe.
  • Add a TTL to each entry and evict on expiry.

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 a doubly-linked list and not singly?

Singly-linked removal is O(n) because you need the predecessor. Doubly-linked gives O(1) removal with a direct pointer to the node from the hash map.

Can I use JS Map's insertion order in a real interview?

Yes for a phone screen, but for an onsite, write the DLL explicitly. Interviewers want to see you compose primitives, not lean on language-specific behavior.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →