LeetCode 146: LRU Cache II

Question

I'm posting my code for a LeetCode problem. If you'd like to review, please do so.

Problem

• Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

• get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

• put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

• The cache is initialized with a positive capacity.

Follow up:

• Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );
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 (not found) 
cache.put(4, 4); // evicts key 1 
cache.get(1); // returns -1 (not found) 
cache.get(3); // returns 3 
cache.get(4); // returns 4

Accepted Python

class LRUCache:
 def __init__(self, capacity: int) -> None:
 self.cache = {}
 self.capacity = capacity
 self.next = {}
 self.prev = {}
 self.head = 'HEAD'
 self.tail = 'TAIL'
 self.connect(self.head, self.tail)
 def connect(self, node_a: int, node_b: int) -> None:
 self.next[node_a], self.prev[node_b] = node_b, node_a
 def remove(self, key: int) -> None:
 self.connect(self.prev[key], self.next[key])
 del(self.prev[key], self.next[key], self.cache[key])
 def append(self, key: int, val: int) -> None:
 self.cache[key] = val
 self.connect(self.prev[self.tail], key)
 self.connect(key, self.tail)
 if len(self.cache) > self.capacity:
 self.remove(self.next[self.head])
 def get(self, key: int) -> int:
 if key not in self.cache:
 return -1
 val = self.cache[key]
 self.remove(key)
 self.append(key, val)
 return val
 def put(self, key: int, val: int) -> None:
 if key in self.cache:
 self.remove(key)
 self.append(key, val)

LeetCode's Solution (Not for review)

class DLinkedNode(): 
 def __init__(self):
 self.key = 0
 self.value = 0
 self.prev = None
 self.next = None
 
class LRUCache():
 def _add_node(self, node):
 """
 Always add the new node right after head.
 """
 node.prev = self.head
 node.next = self.head.next
 self.head.next.prev = node
 self.head.next = node
 def _remove_node(self, node):
 """
 Remove an existing node from the linked list.
 """
 prev = node.prev
 new = node.next
 prev.next = new
 new.prev = prev
 def _move_to_head(self, node):
 """
 Move certain node in between to the head.
 """
 self._remove_node(node)
 self._add_node(node)
 def _pop_tail(self):
 """
 Pop the current tail.
 """
 res = self.tail.prev
 self._remove_node(res)
 return res
 def __init__(self, capacity):
 """
 :type capacity: int
 """
 self.cache = {}
 self.size = 0
 self.capacity = capacity
 self.head, self.tail = DLinkedNode(), DLinkedNode()
 self.head.next = self.tail
 self.tail.prev = self.head
 
 def get(self, key):
 """
 :type key: int
 :rtype: int
 """
 node = self.cache.get(key, None)
 if not node:
 return -1
 # move the accessed node to the head;
 self._move_to_head(node)
 return node.value
 def put(self, key, value):
 """
 :type key: int
 :type value: int
 :rtype: void
 """
 node = self.cache.get(key)
 if not node: 
 newNode = DLinkedNode()
 newNode.key = key
 newNode.value = value
 self.cache[key] = newNode
 self._add_node(newNode)
 self.size += 1
 if self.size > self.capacity:
 # pop the tail
 tail = self._pop_tail()
 del self.cache[tail.key]
 self.size -= 1
 else:
 # update the value.
 node.value = value
 self._move_to_head(node)

Reference

On LeetCode, there is a class usually named Solution with one or more public functions which we are not allowed to rename.

• 146. LRU Cache - Problem

• 146. LRU Cache - Discuss

Answer 1

Something smells funny here:

 self.head = 'HEAD'
 self.tail = 'TAIL'
 self.connect(self.head, self.tail)
def connect(self, node_a: int, node_b: int) -> None:

Those are strings, not integers. Briefly looking through your code, there's nothing requiring that your node keys be integers; they only need to be hashable. This is probably what you want to use for your type hints:

https://docs.python.org/3/library/typing.html#typing.Hashable

Beyond that, though, I question using those strings for HEAD and TAIL. It would be safer to make sentinel objects self.head = object(); self.tail = object() that will not match anything the user provides.