Design and implement a data structure for LRU (Least Recently Used) 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 reaches its capacity, it should invalidate the least recently used item before inserting the new item.
The LRU Cache will be initialized with an integer corresponding to its capacity. Capacity indicates the maximum number of unique keys it can hold at a time.
Definition of “least recently used” : An access to an item is defined as a get or a set operation of the item. “Least recently used” item is the one with the oldest access time.
Example :
Input :
capacity = 2
set(1, 10)
set(5, 12)
get(5) returns 12
get(1) returns 10
get(10) returns -1
set(6, 14) this pushes out key = 5 as LRU is full.
get(5) returns -1
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 solutions:
class LRUCache:
# @param capacity, an integer
def __init__(self, capacity):
self.lru_capacity = capacity
self.lru_list = list()
self.lru_map = dict()
# @return an integer
def get(self, key):
if key in self.lru_map:
value = self.lru_map[key]
self.lru_list.remove(key)
self.lru_list.insert(0, key)
return value
return -1
# @param key, an integer
# @param value, an integer
# @return nothing
def set(self, key, value):
if key in self.lru_map:
self.lru_list.remove(key)
elif len(self.lru_list) == self.lru_capacity:
del self.lru_map[self.lru_list.pop()]
self.lru_map[key] = value
self.lru_list.insert(0, key)
It's really hard to solve this problem.
First of all, I didn't know about concept of LRU.
Secondly, I totally misunderstood LRUCache.
The point is 'get' method.
LRU is Least Recently Used, so if get key from cache I have to change used key index at list.
list is like queue (FIFO).