LRU Cache
Problem statement
Implement an LRUCache class. LRU means least recently used.
When the cache exceeds its capacity, it should evict the least recently used key.
API
const cache = new LRUCache(2);
cache.set('a', 1);
cache.set('b', 2);
cache.get('a'); // 1, now a is most recent
cache.set('c', 3); // evicts bRequirements
get(key)returns the value or-1when missing.set(key, value)inserts or updates a key.- Both
getandsetshould update recency. - Evict the least recently used key when size exceeds capacity.
- Use
O(1)average operations.
Requirements & constraints
- Capacity must be positive.
- Missing values return -1.
- Average get/set should be O(1).
How to approach LRU Cache
The strategy an interviewer expects you to reach for.
An LRU cache keeps the N most recently touched keys — browser-y interview staple for “show me a data structure in JS.” Naive move Array of pairs: on get, scan and move-to-front. That is O(n) per operation and easy to get wrong under capacity eviction. Where it breaks Updating an existing key must refresh recency without duplicating. Capacity 1 is a sharp edge. get on missing keys must not reshuffle. The fix Use a Map: insertion order is recency. On get/set hit, delete and re-set the key to move it to the newest end. When over capacity, delete map.keys().next().value (the oldest). Remember: Map order is the LRU list — delete+set moves a key to most-recent. Say this in the interview: I'd back the cache with a Map, refresh recency by delete-and-set on every hit, and evict the first key when capacity overflows.
The full solution is part of HelloFrontend Pro
The question above is free to read in full. Upgrade to unlock the interactive workspace and the senior-level walkthrough that go with it.
- Runnable editor with the hidden test suite
- Progressive hints that unlock as you get stuck
- Senior-level reference solution with a line-by-line walkthrough
Already a member? Log in to open the workspace.