LRU (Least Recently Used) Cache
A least-recently-used cache keeps a bounded set of items and, when it has to evict, drops whichever one was touched longest ago. It is the standard pattern for route caches, image thumbnails, API response caches — anywhere memory is finite but recent reads should stay warm.
Implement LRUCache(capacity) with .get(key) and .put(key, value). Both operations must mark the touched key as _most_ recently used, and once size exceeds capacity, the oldest entry has to go.
Aim for O(1) time on both methods. The clean trick: a JavaScript Map preserves insertion order, so delete-then-set moves a key to the back without any manual bookkeeping.
Arguments
capacitynumber- Constructor argument. The maximum number of entries the cache will hold before it starts evicting.
.get(key)(key: K) => V | -1- Returns the stored value for
keyand marks it as most recently used. Returns-1when the key is absent. .put(key, value)(key: K, value: V) => void- Inserts or updates the entry for
keyand marks it most recently used. Whensizewould exceedcapacity, the least recently used entry is evicted.
Returns
LRUCache — A cache instance exposing .get and .put. Both operations run in amortized O(1).
Examples
const lru = new LRUCache(2);
lru.put(1, "a");
lru.put(2, "b");
lru.get(1); // "a" — key 1 is now most recent
lru.put(3, "c"); // over capacity: evicts key 2 (least recent)
lru.get(2); // -1 — gone
lru.get(3); // "c"What it has to do
.get(key)returns value or -1 if absent, marking key as recently used..put(key, value)inserts or updates value. Evicts least recently used item when capacity is exceeded.
Notes
- Updating an existing key with
.putshould also refresh its recency — not just overwrite the value in place. - A doubly-linked list plus a hash map is the textbook O(1) implementation;
Maplets you skip the linked list entirely in JavaScript.
- 1.evicts least recently used key when over capacity
These assertions run in your browser the moment you hit Run. Pass all of them to claim the XP.
Discussion
Sign in to postNo comments yet. Be the first to say something.