Design Questions¶

LeetCode 146. LRU Cache¶

I have 2 solutions:

```class Node(object):
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
self.prev = None

class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.capacity = capacity
self.data = dict()
self.tail = Node('dummy', 0)

def get(self, key):
"""
:type key: int
:rtype: int
"""
if key in self.data:
node = self.data[key]
self._tweak(node)
else:
return -1

def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if key in self.data:
node = self.data[key]
node.value = value
self._tweak(node)
else:
node = Node(key, value)
self.data[key] = node

if len(self.data) > self.capacity:
leastNode = self.tail.prev
del self.data[leastNode.key]
self._remove(leastNode)

# always move current node to the head

def _remove(self, node):
# delete last element of the list
prevNode = node.prev
prevNode.next = self.tail
self.tail.prev = prevNode
node.prev = None
node.next = None

def _tweak(self, node):
# always move current node to the head
nextNode = node.next
prevNode = node.prev

prevNode.next = nextNode
nextNode.prev = prevNode

class LRUCache(object):

def __init__(self, capacity):
"""
:type capacity: int
"""
self.stamp = 0
self.size = capacity
self.data = {}

def get(self, key):
"""
:type key: int
:rtype: int
"""
if key in self.data:
self.stamp += 1
self.data[key]['time'] = self.stamp
return self.data[key]['value']
else:
return -1

def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
self.stamp += 1
if len(self.data) < self.size or key in self.data:
self.data[key] = {
'value':    value,
'time':     self.stamp
}
else:
recent = self.stamp
for _key in self.data.keys():
if self.data[_key]['time'] < recent:
recentkey = _key
recent = self.data[_key]['time']
del self.data[recentkey]
self.put(key, value)
```