[LC] 146. LRU Cache
TechDesign a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache
class:
LRUCache(int capacity)
Initialize the LRU cache with positive sizecapacity
.int get(int key)
Return the value of thekey
if the key exists, otherwise return-1
.void put(int key, int value)
Update the value of thekey
if thekey
exists. Otherwise, add thekey-value
pair to the cache. If the number of keys exceeds thecapacity
from this operation, evict the least recently used key.
Follow up:
Could you do get
and put
in O(1)
time complexity?
Approach
Although I’m crazy about the system design, it was my first coding without any reference, and accepted one. I used the priority queue as our basic data structure. To be specific, Max Heap is used for implementing LRU Cache. We can simply save a tuple of (time, key, value) in the max heap. in here, the key is the time which is created by time.time() that returns Epoch time (float). So, I was thinking I can use it as a key and it will be sorted out whenever the tuple is changed. So, every put/get action need at least O(logN) time.
import heapq
import time
class LRUCache:
cache = []
size = 0
def __init__(self, capacity: int):
self.cache = []
self.size = capacity
def get(self, key: int) -> int:
if len(self.cache) == 0:
return -1
if key in [k for t,k,v in self.cache]:
for i,c in enumerate(self.cache):
t,k,v = c
if k == key:
t = time.time()
self.cache[i] = (t,k,v)
heapq.heapify(self.cache)
return v
return -1
def put(self, key: int, value: int) -> None:
if key not in [k for t,k,v in self.cache] and len(self.cache) == self.size:
heapq.heappop(self.cache)
found = False
if key in [k for t,k,v in self.cache]:
for i,c in enumerate(self.cache):
t,k,v = c
if k == key:
t = time.time()
self.cache[i] = (t,k,value)
found = True
break
if not found:
t = time.time()
heapq.heappush(self.cache, (t, key, value))
else:
heapq.heapify(self.cache)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
I think it’s okay but the follow-up request gets and puts in O(1) time complexity. I think without a heap, there is no way to sort the cache. The trick is the amortized analysis. If we make a max heap whenever the cache is full, it requires just a few times except every time we put a different key, which has not happened frequently. So, in the revised code, I do the heapify only when the cache is full.
import heapq
import time
class LRUCache:
cache = []
size = 0
def __init__(self, capacity: int):
self.cache = []
self.size = capacity
def get(self, key: int) -> int:
if len(self.cache) == 0:
return -1
if key in [k for t,k,v in self.cache]:
for i,c in enumerate(self.cache):
t,k,v = c
if k == key:
t = time.time()
self.cache[i] = (t,k,v)
heapq.heapify(self.cache)
return v
return -1
def put(self, key: int, value: int) -> None:
if key not in [k for t,k,v in self.cache] and len(self.cache) == self.size:
heapq.heappop(self.cache)
found = False
if key in [k for t,k,v in self.cache]:
for i,c in enumerate(self.cache):
t,k,v = c
if k == key:
t = time.time()
self.cache[i] = (t,k,value)
found = True
break
if not found:
t = time.time()
heapq.heappush(self.cache, (t, key, value))
else:
heapq.heapify(self.cache)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
I first use for loop to find the cache by key but I soon realized that it does not match the follow-up question because every time when I put or get, I need actual index by key and I used for loop to find the index which requires O(N) So, revised #1 is O(N), not O(1)
So, I thought that O(1) is required some kind of max heap + hashmap structure. When putting the item, hashmap saves the index (in here, I just simply save size of the cache -1 since I always add item in the end), And when I need heapify again, I should update the index which requires O(N). So, the worst case of put() is logN + N but it will be working O(1) based on the amortized analysis.
import heapq
import time
class LRUCache:
cache = []
size = 0
m = {}
def __init__(self, capacity: int):
self.cache = []
self.m = {}
self.size = capacity
def get(self, key: int) -> int:
if len(self.cache) == 0:
return -1
if key in self.m:
t,k,v = self.cache[self.m[key]]
t = time.time()
self.cache[self.m[key]] = (t,k,v)
return v
return -1
def put(self, key: int, value: int) -> None:
if key not in [k for t,k,v in self.cache] and len(self.cache) == self.size:
heapq.heapify(self.cache)
t,k,v = heapq.heappop(self.cache)
self.m.pop(k)
t = time.time()
self.cache.append((t, key, value))
for i,c in enumerate(self.cache):
t,k,v = c
self.m[k] = i
elif key in self.m:
t,k,v = self.cache[self.m[key]]
t = time.time()
self.cache[self.m[key]] = (t,k,value)
else:
t = time.time()
self.cache.append((t, key, value))
self.m[key] = len(self.cache) - 1
Submission
Runtime: 2508 ms, faster than 5.06% of Python3 online submissions for LRU Cache.
Memory Usage: 23.5 MB, less than 62.47% of Python3 online submissions for LRU Cache.
Time/Space Complexity
O(1) (based on amortized analysis)