Skip to main content

13. LRU Cache

mediumAsked at LINE

Design a least-recently-used cache with O(1) get and put — LINE uses this to gauge how cleanly you wire a hash map to a doubly linked list, the exact shape behind their chat-message read-state cache.

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

Problem

Design a data structure that supports get(key) and put(key, value) in O(1) average time. When capacity is reached, evict the least recently used key before inserting a new one. Both reading and writing count as recent use.

Constraints

  • 1 <= capacity <= 3000
  • 0 <= key, value <= 10^4
  • Up to 2 * 10^5 calls total.

Examples

Example 1

Input
ops = ["LRUCache","put","put","get","put","get"], args = [[2],[1,1],[2,2],[1],[3,3],[2]]
Output
[null,null,null,1,null,-1]

Example 2

Input
capacity = 1, put(1,1), put(2,2), get(1)
Output
-1

Approaches

1. Array bookkeeping

Store entries in an array, move accessed item to the front on every get and put.

Time
O(n) per op
Space
O(n)
// arr.unshift after splicing out the touched key.
// O(n) per access blocks 2e5 calls.

Tradeoff:

2. Hash map plus doubly linked list

Map keys to list nodes for O(1) lookup. The list orders nodes by recency; move the touched node to the head on every access and evict from the tail on overflow.

Time
O(1) per op
Space
O(capacity)
class LRUCache {
  constructor(cap) {
    this.cap = cap;
    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, val) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, val);
    if (this.map.size > this.cap) {
      this.map.delete(this.map.keys().next().value);
    }
  }
}

Tradeoff:

LINE-specific tips

At LINE, link this to caching the most recent unread-state for active chat rooms across millions of devices — chat fan-out framing wins 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 LINE interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →