Leetcode 146: LRU Cache

https://leetcode.com/problems/lru-cache/description/

Notes:

There are two functions: one is get() and the other is put(). And both of them need O(1) time complexity. For get(), it is easy to think about a hash map. But for put(), and also the total size is finite, we need to remove the element once it is beyond full; and we need to always update the front element for both get() and put().

For put(), if the key is existed, we need to update the value to the key; and update the position in the list to the front.

One solution is using list, or double linked list. The erase() of list is O(1), but we need to know which one to be erased in O(1) too. So we need to a hash map to correlate the address of the element in the list too. In addition, when remove one element from a list, we need to know the address, not the value. Thus, the hash map needs to set up a relation between the key and the address.

We still need to return the value in the {key, value} pair. So we can find a way to put the value and address together.

See the code below:

class LRUCache{
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
   
    int get(int key) {
        if(!ump.count(key)) return -1;
        auto it = ump[key];
        lt.splice(lt.begin(), lt, it);//splice() of list!
        return lt.front().second;
    }
   
    void put(int key, int value) {
        if(ump.count(key)) {
            auto it = ump[key];
            it->second = value;//override the previous value
            lt.splice(lt.begin(), lt, it);
        }
        else {
            lt.push_front({key, value});
            ump[key] = lt.begin();
            if(lt.size() > cap) {
                ump.erase(lt.back().first);
                lt.pop_back();
            }
        }
    }

private:
    int cap;
    list<pair<int, int>> lt;
    unordered_map<int, list<pair<int, int>>::iterator> ump;//iterator!
};

There is a follow-up question: Leetcode 460.