LRU Cache

Medium

Amazon

14 views

Topics:

Linked ListsDynamic Programming

Design 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 size capacity.
int get(int key) Return the value of 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 number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

LRU Cache

Medium

Amazon

14 views

Topics:

Linked ListsDynamic Programming

Design 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 size capacity.
int get(int key) Return the value of 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 number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the key and value? Can keys or values be negative?
What should happen if the capacity is zero or negative?
If the key already exists in the cache during a `put` operation, should I update the value and move the key to the most recently used position?
Should the cache be thread-safe or are the get and put operations guaranteed to be called from a single thread?
Are there any specific eviction policies I should be aware of beyond least recently used?

Brute Force Solution

Approach

The LRU Cache stores items and discards the least recently used one when full. A brute force approach would check all possible arrangements of items to decide which to discard, making it slow but theoretically correct.

Here's how the algorithm would work step-by-step:

When we need to add a new item to the cache, first check if the cache is full.
If the cache is not full, simply add the new item to the cache.
If the cache is full, we need to find the item that was least recently used.
To find the least recently used item, we could go through every item in the cache, and check how recently it was accessed or added.
For each item, we compare its last access time to every other item's last access time.
After comparing every item's access time, the one with the earliest (oldest) access time is the least recently used.
Remove that least recently used item from the cache.
Now that there's space, add the new item to the cache.

Code Implementation

class LRUCacheBruteForce:

    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.access_history = {}
        self.current_time = 0

    def get(self, key):
        if key in self.cache:
            self.access_history[key] = self.current_time
            self.current_time += 1
            return self.cache[key]
        return -1

    def put(self, key, value):
        if len(self.cache) == self.capacity:
            # Need to evict the least recently used key
            least_recently_used_key = None
            least_recent_time = float('inf')

            for cached_key, last_access_time in self.access_history.items():

                if last_access_time < least_recent_time and cached_key in self.cache:
                    least_recent_time = last_access_time
                    least_recently_used_key = cached_key

            #  Remove the least recently used item from the cache and access history
            if least_recently_used_key is not None:
                del self.cache[least_recently_used_key]
                del self.access_history[least_recently_used_key]

        self.cache[key] = value
        # Update access history with the current time
        self.access_history[key] = self.current_time
        self.current_time += 1

Big(O) Analysis

Time Complexity

O(n²) – The problem involves adding and potentially replacing items in the cache. Determining the least recently used item requires comparing the last access time of each item in the cache against every other item. This involves iterating through all n items currently in the cache and, for each item, comparing it with the other n-1 items. Consequently, the total number of comparisons is proportional to n * (n-1), which approximates to n². Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The plain English explanation outlines a brute-force approach that iterates through existing cache items to find the least recently used. This method operates directly on the cache data structure itself. It does not mention creating any new or temporary data structures like lists, dictionaries, or sets to store intermediate results during the search for the least recently used item. Therefore, the auxiliary space used is constant, independent of the number of items, N, in the cache.

Optimal Solution

Approach

The LRU Cache problem requires us to quickly access and update data while also evicting the least recently used items when the cache is full. The most efficient way to do this is by combining a dictionary for fast lookups with a special data structure that remembers the order in which items were used.

Here's how the algorithm would work step-by-step:

Imagine you have two tools: a dictionary that lets you find data super fast, and a line of data entries that remembers the order data was accessed.
When someone asks for data, first check the dictionary. If it's there, you found it! If not, that data doesn't exist in the cache.
If the data exists, move it to the very front of the line, indicating that it was just used.
If someone wants to add new data, first check if it's already in the dictionary. If so, update it and move it to the front of the line.
If it's brand new data, add it to the dictionary and also to the front of the line.
If adding this new data makes the cache too big (over the size limit), remove the item at the very end of the line (the least recently used) and also remove it from the dictionary.
This setup makes finding, updating, and adding data very quick and also makes it easy to kick out old data when necessary.

Code Implementation

class LRUCache:

    def __init__(self, capacity_value: int):
        self.capacity_value = capacity_value
        self.cache_map = {}
        self.data_list = []

    def get(self, key: int) -> int:
        if key in self.cache_map:
            # Update the recency of the key
            self.data_list.remove(key)
            self.data_list.insert(0, key)
            return self.cache_map[key]
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache_map:
            self.data_list.remove(key)
        self.data_list.insert(0, key)
        self.cache_map[key] = value

        # Enforce capacity constraint
        if len(self.data_list) > self.capacity_value:
            # Remove least recently used
            least_recent_key = self.data_list[-1]

            # Delete LRU entry
            del self.cache_map[least_recent_key]

            # Remove last element
            self.data_list.pop()

Big(O) Analysis

Time Complexity

O(1) – The primary operations in the LRU cache implementation involve dictionary lookups and updates, as well as operations on a data structure maintaining the access order (typically a doubly linked list, although not explicitly mentioned, it's strongly implied by the 'line' metaphor). Dictionary operations (get and put) have an average time complexity of O(1). Moving an element to the front of the 'line' (doubly linked list) also takes constant time. Evicting the least recently used item involves removing the last element from the 'line' and deleting it from the dictionary, both O(1) operations. Therefore, all the operations described take constant time, resulting in an overall time complexity of O(1).

Space Complexity

O(capacity) – The LRU cache implementation utilizes a dictionary (hash map) and a data structure resembling a doubly linked list (implicitly represented by the order of operations) to store key-value pairs. In the worst-case scenario, the cache will store a number of items equal to its capacity. Therefore, the dictionary will hold up to 'capacity' key-value pairs and the linked list also effectively stores 'capacity' items, resulting in space proportional to the cache's capacity. Thus, the auxiliary space used is determined by the 'capacity' of the cache, leading to O(capacity) space complexity.

Edge Cases

Case	How to Handle
Capacity is zero	The cache should not store any elements, so all 'put' operations should be ignored and 'get' operations should always return -1.
Inserting a key that already exists with a new value	The existing key's value should be updated, and the key should be moved to the most recently used position.
Retrieving a key that exists	The key should be moved to the most recently used position.
Cache is full and a new key needs to be inserted	The least recently used key should be evicted to make space for the new key.
Multiple 'put' operations with the same key in quick succession	The last 'put' operation should determine the key's value and position in the cache.
Large number of 'get' and 'put' operations exceeding available memory	The solution should be memory-efficient and avoid memory leaks to handle prolonged usage.
Negative or very large key values	The solution should handle any valid integer key value, considering possible integer overflow in calculations if any.
Cache contains only one element, and it is accessed frequently	The element should always be considered the most recently used and not be evicted.