LRU Cache
Problem Statement
Implement the Least Recently Used (LRU) cache class LRUCache
. The class should support the following operations
LRUCache(int capacity)
Initialize the LRU cache of sizecapacity
.int get(int key)
Return the value corresponding to thekey
if thekey
exists, otherwise return-1
.void put(int key, int value)
Update thevalue
of thekey
if thekey
exists. Otherwise, add thekey
-value
pair to the cache. If the introduction of the new pair causes the cache to exceed its capacity, remove the least recently used key.
A key is considered used if a get
or a put
operation is called on it.
Ensure that get
and put
each run in O(1)
average time complexity.
Example 1:
Input:["LRUCache", [2], "put", [1, 10], "get", [1], "put", [2, 20], "put", [3, 30], "get", [2], "get", [1]]
Output:[None, None, 10, None, None, 20, -1]
Explanation:l_r_u_cache = LRUCache(2);l_r_u_cache.put(1, 10); # cache: {1=10}l_r_u_cache.get(1); # return 10l_r_u_cache.put(2, 20); # cache: {1=10, 2=20}l_r_u_cache.put(3, 30); # cache: {2=20, 3=30}, key=1 was evictedl_r_u_cache.get(2); # returns 20l_r_u_cache.get(1); # return -1 (not found)
You should aim for a solution with O(1)
time for each put()
and get()
function call and an overall space of O(n)
, where n
is the capacity of the LRU
cache.
Recommended Time and Space Complexity
You should aim for a solution with O(1)
time for each put()
and get()
function call and an overall space of O(n)
, where n
is the capacity of the LRU
cache.
Hint 1
Can you think of a data structure for storing data in key-value pairs? Maybe a hash-based data structure with unique keys.
Hint 2
We can use a hash map which takes O(1)
time to get and put the values. But, how can you deal with the least recently used to be removed criteria as a key is updated by the put()
or recently used by the get()
functions? Can you think of a data structure to store the order of values?
Hint 3
A brute-force solution would involve maintaining the order of key-value pairs in an array list, performing operations by iterating through the list to erase and insert these key-value pairs. However, this would result in an O(n)
time complexity. Can you think of a data structure that allows removing and reinserting elements in O(1)
time?
Hint 4
We can use a doubly-linked list, which allows us to remove a node from the list when we have the address of that node. Can you think of a way to store these addresses so that we can efficiently remove or update a key when needed?
Hint 5
We can use a doubly linked list where key-value pairs are stored as nodes, with the least recently used (LRU) node at the head and the most recently used (MRU) node at the tail. Whenever a key is accessed using get()
or put()
, we remove the corresponding node and reinsert it at the tail. When the cache reaches its capacity, we remove the LRU node from the head of the list. Additionally, we use a hash map to store each key and the corresponding address of its node, enabling efficient operations in O(1)
time.
Solution
Brute Force
def lru_get(cache, key): for i in range(len(cache)): if cache[i][0] == key: tmp = cache.pop(i) cache.append(tmp) return tmp[1] return -1
def lru_put(cache, capacity, key, value): for i in range(len(cache)): if cache[i][0] == key: tmp = cache.pop(i) tmp[1] = value cache.append(tmp) return
if capacity == len(cache): cache.pop(0)
cache.append([key, value])
class LRUCache:
def __init__(self, capacity: int): self.cache = [] self.capacity = capacity
def get(self, key: int) -> int: return lru_get(self.cache, key)
def put(self, key: int, value: int) -> None: lru_put(self.cache, self.capacity, key, value)
Time complexity: O(n)
for each put()
and get()
operation. Space complexity: O(n)