22. LRU Cache

mediumAsked at Adyen

Design a data structure that supports get and put in O(1) with least-recently-used eviction.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-20

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get(key) and put(key, value) such that both run in O(1) average time complexity.

Constraints

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

Examples

Example 1

Input

LRUCache(2); put(1,1); put(2,2); get(1); put(3,3); get(2)

Output

[null,null,null,1,null,-1]

Approaches

1. Array-based naive

Reorder array on access; O(n) per op.

Time: O(n) per op
Space: O(n)

class LRUCache { constructor(c){this.c=c;this.a=[];} get(k){const i=this.a.findIndex(x=>x[0]===k);if(i<0)return -1;const e=this.a.splice(i,1)[0];this.a.push(e);return e[1];} put(k,v){const i=this.a.findIndex(x=>x[0]===k);if(i>=0)this.a.splice(i,1);this.a.push([k,v]);if(this.a.length>this.c)this.a.shift();} }

Tradeoff:

2. Map preserves insertion order

Use JavaScript Map iteration order — delete+set to refresh LRU position.

Time: O(1) per op
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, 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:

Adyen-specific tips

Adyen interviewers grade LRU because their idempotency-key store sits right behind a bounded cache — they expect the O(1) per-op contract and a one-line eviction rule.

Solve it now

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