DAY 45 - LRU Cache

Hey everyone! Welcome back to another day of problem-solving. It's day 45, and I'm still going strong on my quest for consistency. Today, We will be solving the daily leetcode problem and it's quite a popular one.

Question : LRU Cache

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 1:

**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

3 Intuition:

• Some things that we can observe are:
• Key Relation With the data set hinting towards a hashMap.
• O(1) lookup time hints towards a hashMap.
• So we can easily say that this is a hashMap problem.
• What we also additionally need to do is delete the least recently used key from our cache if it exceeds its capacity.
• So we will also maintain a queue and queueCounter that counts the number of times it has appeared in the queue so that we can pop it off our cache if it's the least recently used cache.

Let's get down to the algorithm:

• The LRUCache constructor takes an input parameter, capacity, which sets the maximum number of key-value pairs the cache can hold. It initializes the capacity variable with the provided value.

• The get() function takes a key as input and returns the corresponding value from the cache. It first checks if the key exists in the dictionary (dict) using the count() function. If the key is present, it indicates that the value exists in the cache. The function then updates the cache history by pushing the key into the cacheHistory queue and increments the counter (qCounter) for that key. Finally, it returns the value associated with the key from the dictionary. If the key is not found in the cache, the function returns -1.

• The put() function takes a key-value pair as input and inserts it into the cache. It starts by updating the cache history by pushing the key into the cacheHistory queue and increments the counter (qCounter) for that key. It then updates the dictionary (dict) with the provided key-value pair. If the size of the dictionary exceeds the capacity, it calls the remove_lru() function to remove the least recently used item from the cache.

• The remove_lru() function is responsible for popping the least recently used item from the cache. It uses a while loop to iterate as long as the cache history (cacheHistory) is not empty. It retrieves the front element of the cache history (cur), pops it from the queue, and decrements the counter (qCounter) for that key. If the counter becomes zero, it indicates that the item is the least recently used one and can be removed from the dictionary (dict) using the erase() function. The function then breaks out of the loop, as the eviction process is complete.

Code:

int capacity;
    queue<int> cacheHistory;
    unordered_map<int,int> dict;
    unordered_map<int,int> qCounter;

    LRUCache(int capacity) {
        this->capacity = capacity;
    }

    int get(int key) {
        if(dict.count(key)){
            cacheHistory.push(key);
            qCounter[key]++;
            return dict[key];
        }
        return -1;
    }

    void put(int key, int value) {
        cacheHistory.push(key);
        qCounter[key]++;
        dict[key] = value;
        if(dict.size() > capacity){
            remove_lru();
        }
    }

    void remove_lru()
    {

    while(!cacheHistory.empty()){
        int cur = cacheHistory.front();
        cacheHistory.pop();
        qCounter[cur]--;

        if(qCounter[cur] == 0){
            dict.erase(cur);
            break;
        }
    }
}

Here we also used O(capacity) space complexity for our answer.