C++ concise O(1) solution with list and hashmap (with detailed analysis)


  • 0

    To achieve O(1) performance, naturally a hashmap of key to value mapping should be employed. However, hashmap does not track the order of entries to be added. Therefore, a sequential container is needed to maintain the history bookkeeping ordered as when the entry is added. Note that we also need to evict the oldest entry from the container when capacity is reached as well as moving entries from middle to the tail, so list would be a good candidate to do the job due to O(1) performance of list::erase by iterator.

    Based on the analysis above, we can employ:

    • A list of type list<pair<int,int>> to store data of key-value pairs ordered as when they are added to the cached.
    • A hashmap of type unordered_map<int, list<pair<int, int>>::iterator> to map key to the position in the data list for quick look-up.

    Note that we also need to store key in list since we need reference from list to hashmap when evicting the oldest key-value pair to keep list and hashmap in sync.

    Performance concern of self-made double linked list vs STLstd::list:
    Actually, I realized this from a hint during an actual interview (too bad...). Self-made double linked list only re-directs references whenever moving a node to a different place while std::list does not really provide such capability, so the consequence is that std::list will have to erase and re-create the same node again. This might not be too bad for key-value pair as type int here, but could be a huge drawback in realistic situation.

    class LRUCache{
    private:
        int _cap; list<pair<int, int>> _data; // list of pair(key, value)
        unordered_map<int, list<pair<int, int>>::iterator> _pos; // key->position in list
        void addToTail(int key, int value) { _data.emplace_back(key, value); _pos[key] = --_data.end(); }
    public:
        LRUCache(int capacity):_cap(capacity) { }
        
        int get(int key) {
          if (!_pos.count(key)) return -1;
          int value = _pos[key]->second;
          _data.erase(_pos[key]); addToTail(key, value);
          return value;
        }
        
        void set(int key, int value) {
          if (_pos.count(key)) _data.erase(_pos[key]);
          if (_data.size() == _cap) _pos.erase(_data.front().first), _data.pop_front();
          addToTail(key, value);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.