Implement LRU Cache

Problem

Design an LRUCache — a fixed-size cache that keeps the most recently used items and drops the stale ones. This is exactly how browsers cache assets, how CDNs decide what to keep hot, and a classic interview question (LeetCode 146).

new LRUCache(capacity) must support:

• get(key) — return the value if present, else -1. A successful get marks the key as most recently used.
• put(key, value) — insert or update. Updating also marks the key most-recently-used. If inserting exceeds capacity, evict the least-recently-used key first.

Both operations must run in O(1) average time.

Input

const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 1  → key 1 is now most-recent
cache.put(3, 3);    // capacity exceeded → evict key 2 (least-recent)
cache.get(2);       // -1

Expected output

• cache.get(1) → 1
• After put(3, 3), cache.get(2) → -1 (evicted)

Implement from scratch:

class LRUCache {
  constructor(capacity) {
    // Your code here
  }
  get(key) {}
  put(key, value) {}
}