LRU Cache
Medium · Design · Hash Table · Linked List · Design
Problem
Build a fixed-capacity cache that evicts whatever was used least recently. Both operations must run in constant time.
- LRUCache(capacity) — create it
- get(key) — return the value, or -1 if absent; a hit counts as a use
- put(key, value) — insert or overwrite; a write counts as a use, and going over capacity evicts the least recently used key
Tests replay a call sequence: the first entry names the class and its constructor arguments, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: LRUCache(2), put(1,1), put(2,2), get(1), put(3,3), get(2) Output: 1, then -1
get(1) refreshes key 1, so adding key 3 evicts key 2 instead.
Constraints
- 1 <= capacity <= 3000
- 0 <= key, value <= 10^5
- Up to 2 * 10^5 calls
- get and put must both be O(1)
Approaches
- Dict plus a hand-built doubly linked list — time O(1) both, space O(capacity)
Related problems
Start free on Cariara · Coding problems · System design studio
