Build a Least Recently Used cache with O(1) get and put. Combines a hash map with a doubly linked list.
Step 1 of 160%
Step 1 of 16
Create a Node class for the doubly linked list - add __slots__ = ("key", "val", "prev", "next") for memory efficiency
pythonLn 1, Col 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Design a Least Recently Used (LRU) Cache## Requirements:# - Fixed capacity, evicts least recently used item when full# - O(1) get and put operations# - get(key) returns value if exists, -1 otherwise# - put(key, value) inserts or updates; evicts LRU if over capacity## Hint: Combine a hash map with a doubly linked list## Example:# cache = LRUCache(2)# cache.put(1, 1)# cache.put(2, 2)# cache.get(1) # returns 1# cache.put(3, 3) # evicts key 2# cache.get(2) # returns -1