20-line concise C++ O(1) solution using a list and hashmap with comments, no extra struct/class definition


  • 0

    To achieve O(1)for both setandget, the key idea is to figure out how to sort frequency of key by using a std::list.

    • Define a list _flist of type list<pair<int, list<int>>>to store a key list with same frequency, where the element in the list is defined as pair(frequency, key list) sorted by frequency in ascending order.
    • Define a hashmap _data of type unordered_map<int, tuple<int, FreqList::iterator, KeyList::iterator>> to quickly look up information of a given key, which is mapped to tuple(value, position in frequency list, position in key list).

    Whenever we need to read or write a cache entry, the frequency of the key in request needs to be incremented by one, which is implemented by utility private method incrementFrequency. With the help from the utility method, setandgetof cache will become very simple to implement.

    typedef list<int> KeyList; // list of keys with same frequency
    typedef list<pair<int, KeyList>> FreqList; // list of (freq, keys) pairs
    class LFUCache {
    public:
      LFUCache(int capacity) :_cap(capacity) { }
      int get(int key) { return _data.count(key) ? (incrementFrequency(key), std::get<0>(_data[key])) : -1; }
      void set(int key, int val) { if (_cap > 0) incrementFrequency(key), std::get<0>(_data[key]) = val; }
    
    private:
      int _cap; FreqList _flist; // list of (freq, keys) pairs sorted in frequency
      unordered_map<int, tuple<int, FreqList::iterator, KeyList::iterator>> _data; // key->(val,freq itr,key itr)
      void incrementFrequency(int key) { // increment frequence of given key by one
        if (_cap <= 0) return;
        int val = -1, freq = 1; auto fpos = _flist.begin(); // default info
        if (_data.count(key)) { // update info if found in cache
    	val = std::get<0>(_data[key]); fpos = std::get<1>(_data[key]); freq += fpos->first;
    	fpos->second.erase(std::get<2>(_data[key]));
    	if (fpos->second.empty()) fpos = _flist.erase(fpos); else ++fpos;
        } else if (_data.size() == _cap) { // evict oldest cache with lowest frequency if capacity reached
    	_data.erase(*fpos->second.begin()); fpos->second.pop_front();
    	if (fpos->second.empty()) fpos = _flist.erase(fpos);
        }
        // insert new cache
        if (fpos != _flist.end() && fpos->first == freq) fpos->second.push_back(key);
        else fpos = _flist.emplace(fpos, freq, KeyList(1, key));
        _data[key] = make_tuple(val, fpos, --fpos->second.end());
      }
    };
    

Log in to reply
 

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