LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
Constraints:
- 1 <= capacity <= 1000
- 0 <= key <= 1000
- 0 <= value <= 1000
- At most 3000 operations will be performed.
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]
Explanation: LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); lRUCache.put(2, 2); lRUCache.get(1); // return 1 lRUCache.put(3, 3); // evict key 2 lRUCache.get(2); // return -1 (not found) lRUCache.put(4, 4); // evict key 1 lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4
Solutions
Hash Table and Doubly Linked List
We use a hash table to store the keys and values, and a doubly linked list to keep track of the order of the elements. When we get a key, we move it to the end of the list. When we put a key, we add it to the end of the list and remove the first element if the list is full.
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity:
int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key:
int) -> int:
if key not in self.cache:
return -1
value = self.cache.pop(key)
self.cache[key] = value
return value
def put(self, key:
int, value:
int) -> None:
if key in self.cache:
self.cache.pop(key)
elif len(self.cache) >= self.capacity:
self.cache.popitem(last=False)
self.cache[key] = valueFollow-up:
How would you implement the LRU cache if you were not allowed to use a hash table?
