Skip to main content

12. LRU Cache

mediumAsked at Flipkart

Implement an LRU cache with O(1) get and put — Flipkart asks this because inventory-snapshot lookups during flash sales must hit cache in microseconds.

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

Problem

Design a data structure that follows the constraints of a Least Recently Used cache. Implement get(key) and put(key, value) both in O(1) average time. Evict the least recently used entry when capacity is exceeded.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key, value <= 10^4
  • At most 2 * 10^5 calls

Examples

Example 1

Input
cap=2; put(1,1); put(2,2); get(1); put(3,3); get(2)
Output
1, -1

Example 2

Input
cap=1; put(1,1); put(2,2); get(1)
Output
-1

Approaches

1. Array scan

Store entries in an array; linear-scan for recency on each call.

Time
O(n) per op
Space
O(n)
// fails O(1) requirement under load

Tradeoff:

2. Hash map + doubly linked list

Hash maps the key to its DLL node for O(1) lookup; the DLL orders by recency so we can move-to-front in O(1) and evict the tail when full.

Time
O(1) avg
Space
O(capacity)
class LRUCache {
  constructor(cap) { this.cap = cap; this.m = new Map(); }
  get(k) {
    if (!this.m.has(k)) return -1;
    const v = this.m.get(k);
    this.m.delete(k); this.m.set(k, v);
    return v;
  }
  put(k, v) {
    if (this.m.has(k)) this.m.delete(k);
    else if (this.m.size >= this.cap) this.m.delete(this.m.keys().next().value);
    this.m.set(k, v);
  }
}

Tradeoff:

Flipkart-specific tips

Flipkart panels love the Map insertion-order trick in modern JS but expect you to also describe the underlying hash+DLL — call out the eviction race during sale-event traffic spikes for bonus points.

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

Practice these live with InterviewChamp.AI →