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.head = Node('dummy', 0)
self.tail = Node('dummy', 0)
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key in self.data:
node = self.data[key]
self._tweak(node)
return self.head.next.value
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
self._add(node)
if len(self.data) > self.capacity:
leastNode = self.tail.prev
del self.data[leastNode.key]
self._remove(leastNode)
def _add(self, node):
# always move current node to the head
headNext = self.head.next
self.head.next = node
headNext.prev = node
node.next = headNext
node.prev = self.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
headNext = self.head.next
if node != headNext:
self.head.next = node
node.prev = self.head
node.next = headNext
headNext.prev = node
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)