Skip to main content

14. LRU Cache

mediumAsked at Riot Games

Design a cache that evicts the least-recently-used key when capacity is hit — Riot's matchmaking and asset-streaming systems both lean on LRU eviction.

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

Problem

Implement an LRU cache with get(key) and put(key, value) both running in O(1) average time. When the cache exceeds capacity, evict the least-recently-used entry.

Constraints

  • 1 <= capacity <= 3000
  • Up to 2 * 10^5 calls
  • All keys and values are non-negative

Examples

Example 1

Input
capacity=2, ops=[put(1,1),put(2,2),get(1),put(3,3),get(2)]
Output
[null,null,1,null,-1]

Example 2

Input
capacity=1, ops=[put(1,1),put(2,2),get(1)]
Output
[null,null,-1]

Approaches

1. Array + linear scan

Store [key,value] tuples and scan on every operation; evict via splice.

Time
O(n)
Space
O(n)
// get: linear find, move to front
// put: linear find/update or append + pop front when over capacity
// O(n) per op — unacceptable for Riot's hot path.

Tradeoff:

2. Hash map + doubly linked list

Map keys to list nodes; on get/put, splice the node to the front in O(1). Mirrors how Riot's asset cache promotes recently-streamed champion textures during loading screens.

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

Tradeoff:

Riot Games-specific tips

Riot wants you to articulate the O(1) requirement upfront and pick the JS Map insertion-order trick or hand-rolled doubly-linked-list — the same eviction policy their texture streamer uses to stay under 30Hz tick budget.

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

Practice these live with InterviewChamp.AI →