Description
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with get(key) and put(key, value) methods. Both operations must run in O(1) average time complexity.
Examples
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]][null, null, null, 1, null, -1, null, -1, 3, 4]Cache capacity is 2. Operations demonstrate LRU eviction.
["LRUCache", "put", "put", "put", "get", "put", "get", "get", "put", "get", "get"] [[3], [5, 50], [6, 60], [7, 70], [5], [8, 80], [6], [7], [9, 90], [5], [8]][null, null, null, null, 50, null, -1, 70, null, -1, 80]Cache capacity is 3. After putting (5,50), (6,60), (7,70), cache is full. Getting key 5 moves it to most recent. Putting (8,80) evicts least recent key 6. Getting key 6 returns -1 (not found). Getting key 7 returns 70. Putting (9,90) evicts key 5 (least recent). Final gets: key 5 returns -1, key 8 returns 80.
["LRUCache", "put", "get", "put", "get", "get", "put", "get", "get"] [[1], [10, 100], [10], [20, 200], [10], [20], [30, 300], [20], [30]][null, null, 100, null, -1, 200, null, -1, 300]Cache capacity is 1 (minimum size). Put (10,100), then get 10 returns 100. Put (20,200) evicts key 10. Get 10 returns -1 (evicted), get 20 returns 200. Put (30,300) evicts key 20. Get 20 returns -1 (evicted), get 30 returns 300. This demonstrates behavior with minimum capacity where each new insertion causes eviction.
Constraints
- •
1 ≤ capacity ≤ 3000 - •
0 ≤ key ≤ 10⁴ - •
0 ≤ value ≤ 10⁵