Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
What is considered as `used`?
Both get and put are considered as used.
Example 1:
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); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
class Node:
def __init__(self, key, value, left=None, right=None):
self.key = key
self.value = value
self.left = left
self.right = right
class LRUCache(object):
def __init__(self, capacity):
self.cap = capacity
self.head, self.tail = None, None
self.keyMap = dict()
def get(self, key):
if key not in self.keyMap:
return -1
node = self.keyMap[key]
self.removeNode(node)
self.addingNodeFront(node)
return node.value
def put(self, key, value):
if key in self.keyMap:
# Move the key in the first.
keyNode = self.keyMap[key]
self.removeNode(keyNode)
self.addingNodeFront(keyNode)
else:
# first check the capacity.
if len(self.keyMap) < self.cap:
# if less than capacity, add the key in the first
newNode = Node(key, value)
if self.head == None:
self.head = newNode
self.tail = newNode
else:
self.addingNodeFront(newNode)
# add the node to Mapp
self.keyMap[key] = newNode
else:
# else remove the last in the list and add the new key in the first. and add the node in keymap
tmp = self.tail
self.tail = tmp.left
self.tail.right = None
self.keyMap.pop(tmp.key)
newNode = Node(key, value)
self.addingNodeFront(newNode)
self.keyMap[key] = newNode
print(self.keyMap)
def addingNodeFront(self, node):
tmp = self.head
self.head = node
node.right = tmp
tmp.left = node
def removeNode(self, node):
_prev = node.left
_next = node.right
if _prev == None:
self.head = node.right
_next.left = None
elif _next == None:
self.tail = node.left
_prev.right = None
else:
_prev.right = _next
_next.left = _prev
Test Code
lRUCache = LRUCache(2)
lRUCache.put(1, 1) # cache is {1=1}
lRUCache.put(2, 2) # cache is {1=1, 2=2}
print(lRUCache.get(1)) # // return 1
lRUCache.put(3, 3) # // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
print(lRUCache.get(2)) # // returns -1 (not found)
lRUCache.put(4, 4) # // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
# lRUCache.get(1); // return -1 (not found)
# lRUCache.get(3); // return 3
# lRUCache.get(4); // return 4