What you're building
An LRU (Least Recently Used) cache β a fixed-capacity key/value store that automatically evicts the least-recently-used item when it runs out of space.
LRU caches are inside your browser (page cache), every CDN (CloudFront, Fastly), Redis, and countless database query caches.
Requirements
new LRUCache(capacity)β create a cache that holds at mostcapacityitemsget(key)β return the value forkey, or-1if not found; marks the key as recently usedput(key, value)β insert or update a key; if over capacity, evict the least recently used key first- Both
getandputmust run in O(1) time (use a Map β JS Maps preserve insertion order, so you can delete + re-insert to move a key to "most recent")
Stretch goals
- Add a
keys()method returning current keys from least-recently-used to most-recently-used - Track hit/miss stats with a
stats()method returning{ hits, misses }
What this proves
You understand cache eviction, O(1) data structure design, and how JavaScript's Map preserves insertion order β a pattern used in production Node.js services.
β‘ 40 XP
solution.jsRuns in your browser
Loading editorβ¦
Tests4 to pass
get returns -1 for missing key
put and get basic
evicts least recently used
update existing key keeps capacity
Run your code to check these.