Description
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get and put methods with O(1) time complexity.
Examples
Input:
capacity = 2, operations = [put(1,1), put(2,2), get(1), put(3,3), get(2)]Output:
[1,-1]Explanation:
Cache evicts least recently used.
Input:
capacity = 1, operations = [put(5,10), put(7,20), get(5), get(7)]Output:
[-1, 20]Explanation:
With capacity 1, putting (5,10) fills the cache. When putting (7,20), key 5 gets evicted since it's the only item and least recently used. Getting key 5 returns -1 (not found), getting key 7 returns 20.
Input:
capacity = 3, operations = [put(1,100), put(2,200), put(3,300), get(1), put(4,400), get(2), get(3), get(4)]Output:
[100, -1, 300, 400]Explanation:
Cache fills with keys 1,2,3. Getting key 1 makes it recently used. Adding key 4 evicts key 2 (least recently used). So get(2) returns -1, while get(3) and get(4) return their values since they weren't evicted.
Constraints
- •
1 ≤ capacity ≤ 3000 - •
0 ≤ key ≤ 10⁴ - •
0 ≤ value ≤ 10⁵