LRU Cache Design
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(capacity)- Initialize with the capacity of the LRU cacheget(key)- Return the value if the key exists, otherwise return -1put(key, value)- Update or insert the value. If capacity is exceeded, evict the least recently used item.
Both get and put operations must run in O(1) time complexity.
Examples
Input: [["LRUCache","put","put","get","get","get"],[[],[1,1],[2,2],[1],[2],[3]]]
Output: [null,null,null,1,2,-1]
Input: [["LRUCache","put","get","put","get","get"],[[],[1,1],[1],[2,2],[1],[2]]]
Output: [null,null,1,null,1,2]
Hints
Use a combination of HashMap and Doubly Linked List to achieve O(1) for both operations.
The most recently used item should be at the front, and the least recently used at the back.
When updating an existing key, move it to the front.
Related Problems
LRU Cache Design
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.