LRU Cache
Design a Least Recently Used cache that supports get and put in O(1).
Examples
Input: [["LRUCache","put","put","get","put","get","put","get","get","get"],[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]]
Output: [null,null,null,1,null,-1,null,-1,3,4]
Input: [["LRUCache","put","get","put","get","get"],[[1],[2,1],[2],[3,2],[2],[3]]]
Output: [null,null,1,null,-1,2]
Hints
Use a combination of a hashmap and a doubly-linked list to achieve O(1) time complexity for both get and put operations.
Implement a dummy head and tail in the doubly-linked list to simplify edge cases when adding or removing nodes.
When a node is accessed (get or put), detach it from its current position in the list and move it to the front to mark it as recently used.
Related Problems
LRU Cache
Design a Least Recently Used cache that supports get and put in O(1).