Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get
and set
.
get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(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.
Solution:
The easiest way to implement this cache is using a OrderedDict.
class LRUCache:
# @param capacity, an integer
def __init__(self, capacity):
self.cache = collections.OrderedDict()
self.capacity = capacity
# @return an integer
def get(self, key):
val = -1
if key in self.cache:
val = self.cache[key]
del self.cache[key]
self.cache[key] = val
return val;
# @param key, an integer
# @param value, an integer
# @return nothing
def set(self, key, value):
if key in self.cache:
del self.cache[key]
else:
if len(self.cache)==self.capacity:
for keyTemp in self.cache:
del self.cache[keyTemp]
break
self.cache[key] = value
No comments :
Post a Comment