Heap / Priority Queue
LC #146Medium
LRU Cache
Heap / Priority Queue
AmazonGoogleMetaMicrosoftBloombergUberProblem
Design a data structure that follows LRU (Least Recently Used) cache eviction. Both get and put must be O(1).
designhash-maplinked-list
Constraints
- ›1 ≤ capacity ≤ 3000
- ›0 ≤ key ≤ 10⁴
- ›0 ≤ value ≤ 10⁵
- ›get and put must be O(1) average
Example
Input
LRUCache(2) → put(1,1) → put(2,2) → get(1) → put(3,3) → get(2)Output
get(1)=1, get(2)=-1Why
After put(3,3), key 2 was evicted (LRU). get(2) returns -1.