← All challenges

LRU cache (O(1) get/put)

Easy

Design a Least Recently Used cache with O(1) `get` and `put` operations.

LRU cache (O(1) get/put)

Problem

Caches are everywhere in backend systems - browser caches, DNS caches, database buffer pools, CDN edge caches - and every one of them must decide what to evict when it fills up. Least Recently Used (LRU) is the classic answer, and "design an LRU cache with O(1) operations" is a favorite opening question in backend and systems interviews.

Design an LRU cache with a fixed capacity. get returns the value for a key (or -1 when absent) and refreshes that key as the most recently used. put inserts or updates a key; when the cache is full, inserting a new key evicts the key that was least recently accessed. Each key maps to an integer value.

Input

  • capacity: number — Maximum number of key-value pairs the cache can hold. Must be greater than 0.

Output

  • LRUCache — An LRUCache instance with get(key: number): number (returns the stored value, or -1 if the key was never inserted or was evicted) and put(key: number, value: number): void (inserts or updates a key, evicting the least recently used key when the cache is full).

Examples

Example 1:

put(1, 10) put(2, 20) get(1) // -> 10 put(3, 30) // cache full; evicts key 2 (least recently used) get(2) // -> -1

Output: -1

Putting keys 1 and 2 fills the cache. get(1) refreshes key 1, so when key 3 arrives the least recently used key (2) is evicted, and get(2) returns -1.

Example 2:

put(1, 10) put(2, 20) // evicts key 1 get(2) // -> 20 get(1) // -> -1 (evicted)

Output: -1

With capacity 1, every new put evicts the previous entry, so get(2) returns 20 while the evicted key 1 returns -1.

Example 3:

put(1, 10) put(1, 99) // updates the existing key; capacity unchanged get(1) // -> 99

Output: 99

put on a key that already exists overwrites the value without growing the cache and without evicting anything.

Constraints

  • Capacity is at least 1.
  • All keys and values are integers.
  • The cache starts empty.
  • Aim for O(1) amortized time per get and put.

Complexity

  • Time: O(1) amortized per get and put (target)
  • Space: O(capacity)

Starter

class LRUCache {
  private capacity: number;
  private cache: Map<number, number> = new Map();

  constructor(capacity: number) {
    this.capacity = capacity;
  }

  // TODO: return the value for key, or -1 when the key is absent.
  // A successful get must refresh the key as the most recently used.
  get(key: number): number {
    // TODO: implement
    throw new Error('not implemented');
  }

  // TODO: insert or update key -> value. When the cache is full, evict
  // the least recently used key before inserting the new one.
  put(key: number, value: number): void {
    // TODO: implement
  }
}

export function solve(capacity: number): LRUCache {
  return new LRUCache(capacity);
}

Hints

Answer