LRU cache (O(1) get/put)

LRU cache (O(1) get/put)

Problem

Design a Least Recently Used (LRU) cache with O(1) get and put operations. The cache has a fixed capacity; when it 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 value or -1 if absent) and put(key: number, value: number): void methods.

Examples

Example 1:

const cache = new LRUCache(2); cache.put(1, 10); cache.put(2, 20); cache.get(1); // returns 10 cache.put(3, 30); // evicts key 2 (LRU) cache.get(2); // returns -1 (evicted)

Output: -1

After putting keys 1 and 2, accessing key 1 refreshes it. Putting key 3 evicts key 2 (least recently used before the put).

Example 2:

const cache = new LRUCache(1); cache.put(1, 10); cache.put(2, 20); // evicts key 1 cache.get(1); // returns -1 cache.get(2); // returns 20

Output: -1

With capacity 1, every new put evicts the previous entry.

Constraints

• Capacity is at least 1.
• All keys and values are integers.
• get and put must each run in O(1) amortized time.
• The cache starts empty.

Complexity

• Time: O(1) per get and put (Map operations are amortized O(1))
• 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);
}