Implement an LRU Cache

Question

Design a Least Recently Used (LRU) Cache with `get(key)` and `put(key, value)` operations, both O(1). When capacity is exceeded, evict the least recently used entry.

Accepted Answer

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.cache = new Map()   // Map preserves insertion order
  }

get(key) {
    if (!this.cache.has(key)) return -1

// Move to end (most recently used)
    const value = this.cache.get(key)
    this.cache.delete(key)
    this.cache.set(key, value)
    return value
  }

put(key, value) {
    if (this.cache.has(key)) this.cache.delete(key)
    else if (this.cache.size >= this.capacity) {
      // Delete least recently used (first key in Map)
      this.cache.delete(this.cache.keys().next().value)
    }
    this.cache.set(key, value)
  }
}

// Test
const lru = new LRUCache(2)
lru.put(1, 1)
lru.put(2, 2)
lru.get(1)     // 1   — 1 is now most recently used
lru.put(3, 3)  // evicts key 2
lru.get(2)     // -1  — evicted
lru.get(3)     // 3

Implement an LRU Cache

Answer