- LRU Cache
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.
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
my thoughts:
1. use dict to store key:value; use a double linked list to keep track of key priority.
TLE
1'. slowest step is track the node. we can put key:val in the node and store the node in dict for fast track.
my solution:
**********TLE
class Node:
def __init__(self, x):
self.val = x
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
"""
:type capacity: int
"""
self.cap = capacity
self.d = {}
self.head = Node(0)
self.tail = Node(0)
p1 = self.head
for i in range(capacity):
p1.next = Node(0)
p1.next.prev = p1
p1 = p1.next
p1.next = self.tail
self.tail.prev = p1
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self.d:
return -1
p1 = self.head.next
while p1.val != key:
p1 = p1.next
p1.prev.next = p1.next
p1.next.prev = p1.prev
hn = self.head.next
self.head.next = p1
p1.next = hn
hn.prev = p1
p1.prev = self.head
return self.d[key]
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if key not in self.d:
p1 = Node(key)
hn = self.head.next
self.head.next = p1
p1.next = hn
hn.prev = p1
p1.prev = self.head
if self.tail.prev.val in self.d:
del self.d[self.tail.prev.val]
p1 = self.tail.prev.prev
p1.next = self.tail
self.tail.prev = p1
else:
p1 = self.head.next
while p1.val != key:
p1 = p1.next
p1.prev.next = p1.next
p1.next.prev = p1.prev
hn = self.head.next
self.head.next = p1
p1.next = hn
hn.prev = p1
p1.prev = self.head
self.d[key] = value
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
**********168ms
class Node:
def __init__(self, x, y):
self.val = (x, y)
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
"""
:type capacity: int
"""
self.cap = capacity
self.d = {}
self.head = Node(0,0)
self.tail = Node(0,0)
p1 = self.head
for i in range(capacity):
p1.next = Node(0, 0)
p1.next.prev = p1
p1 = p1.next
p1.next = self.tail
self.tail.prev = p1
def get(self, key):
"""
:type key: int
:rtype: int
"""
if key not in self.d:
return -1
p1 = self.d[key]
self.delNode(p1)
self.insNode(p1)
return self.d[key].val[1]
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: void
"""
if key not in self.d:
p1 = Node(key, value)
self.insNode(p1)
if self.tail.prev.val[0] in self.d:
del self.d[self.tail.prev.val[0]]
self.delNode(self.tail.prev)
else:
p1 = self.d[key]
p1.val = (key, value)
self.delNode(p1)
self.insNode(p1)
self.d[key] = p1
def delNode(self, n):
n.next.prev = n.prev
n.prev.next = n.next
def insNode(self, n):
hn = self.head.next
self.head.next = n
n.next = hn
hn.prev = n
n.prev = self.head
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
my comments:
from other ppl's solution:
1. N/A