# LeetCode 146: LRU Cache II

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.

• 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.put(4, 4);    // evicts key 1
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.tail = '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:

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 _remove_node(self, node):
"""
Remove an existing node from the linked list.
"""
prev = node.prev
new = node.next

prev.next = new
new.prev = prev

"""
Move certain node in between to the head.
"""
self._remove_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

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;

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.key = key
newNode.value = value

self.cache[key] = 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


### Reference

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

Something smells funny here:

    self.head = 'HEAD'
self.tail = 'TAIL'

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.