Leetcode - LRU Cache

Question

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.

This is atesla question

• The LRU cache is a hash-map, mapping: {key (int): Node(key, value)}
• Use LRU and MRU pointers which are dummy pointers for swapping
• O(1) insert and query time

class Node():
def __init__(self, key, val):
	self.key, self.val = key, val
	self.prev = self.next = None
 
class LRUCache:
	def __init__(self, capacity: int):
		self.capacity = capacity
		self.cache = {}
 
		self.LRU, self.MRU = Node(0, 0), Node(0, 0)
		self.LRU.next, self.MRU.prev = self.MRU, self.LRU
 
# remove from list
def remove(self, node):
	prev, nxt = node.prev, node.next
	prev.next, nxt.prev = nxt, prev
 
# insert at right (MRU)
def insert(self, node):
	prev, nxt = self.MRU.prev, self.MRU
	prev.next = nxt.prev = node
	node.next, node.prev = nxt, prev
 
def get(self, key: int) -> int:
	if key in self.cache:
		# Update most recent
		self.remove(self.cache[key])
		self.insert(self.cache[key])
		return self.cache[key].val
	return -1
 
def put(self, key: int, value: int) -> None:
	if key in self.cache:
		self.remove(self.cache[key])
	self.cache[key] = Node(key, value)
	self.insert(self.cache[key])
 
	if len(self.cache) > self.capacity:
		# remove from list and delete LRU from cache
		LRU = self.LRU.next
		self.remove(LRU)
		del self.cache[LRU.key]