Implement LRU Cache (get/put with O(1))

Question

Accepted Answer

**Approach:** `Map` preserves insertion order — `get` deletes+re-sets to mark recent; `put` does same and evicts first key when over capacity. O(1) via Map ops. DLL alternative for interview depth.

```javascript
class LRUCache {
  constructor(capacity) { this.capacity = capacity; this.map = new Map(); }
  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, val);
    return val;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      const firstKey = this.map.keys().next().value;
      this.map.delete(firstKey);
    }
  }
}

// Demo
const lru = new LRUCache(2);
lru.put(1, 1); lru.put(2, 2);
console.log(lru.get(1)); // 1 (makes 1 most recent, order: 2,1)
lru.put(3, 3); // evicts 2
console.log(lru.get(2)); // -1
lru.put(4, 4); // evicts 1
console.log(lru.get(1)); // -1
console.log(lru.get(3)); // 3
console.log(lru.g

Implement LRU Cache (get/put with O(1))

Understand the problem

Attempt it yourself

Study the solution

Solution ready — 2 min read

Join the discussion

Discussion (0)

KEEP THE
STREAK ALIVE.

Understand the problem

Attempt it yourself

Study the solution

Solution ready — 2 min read

Join the discussion

Discussion (0)

KEEP THESTREAK ALIVE.

KEEP THE
STREAK ALIVE.