mediumcodingjavascript~15 min
Implement an LRU Cache
Objective: Combine hash lookup and recency ordering; know the Map insertion-order trick.
Implement `class LRUCache` with `get(key)` and `put(key, value)` that evicts the least recently used entry when `capacity` is exceeded. Both operations should be O(1).
- `new LRUCache(capacity)`.
- `get` returns the value or -1 and marks the key most recently used.
- `put` inserts or updates and marks the key most recently used.
- When size exceeds capacity, evict the least recently used key.
JavaScript
⌘/Ctrl + Enter to run tests · Esc then Tab leaves the editor
Output
> Nothing has run yet.
Interview follow-up questions
- How would you implement this with a doubly linked list and hash map?
- What changes for LFU?
- How would you add a TTL?