LRU Cache

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

Leave a Reply