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 size capacity.
• int get(int key) Return the value corresponding to the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-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 10
l_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 evicted
l_r_u_cache.get(2);      # returns 20
l_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)