Modern C++ solution 86ms runtime beating 99%


  • 0
    F
    class LFUCache {
    public:
        LFUCache(int capacity) :
            cap(capacity) {
            
        }
        
        struct node {
            int key;
            int value;
            int freq;
        };
        
        typedef list<node> lru_list; // list of key, value
        typedef list<lru_list> freq_list; // list of nodes
        
        freq_list::iterator get_flist(int freq, freq_list::iterator insert_itr) {
            auto fmap_itr = fmap.find(freq);
            freq_list::iterator flist_itr;
            if (fmap_itr == fmap.end()) {
                flist_itr = flist.emplace(insert_itr); 
                fmap[freq] = flist_itr;
            } else {
                flist_itr = fmap_itr->second;
            }
            
            return flist_itr;
        }
        
        void update_freq(lru_list::iterator lru_itr) {
            auto old_flist_itr = fmap[lru_itr->freq];
            // update node frequency
            ++lru_itr->freq;
            // locate the new freq list if exist, otherwise create new one
            auto new_flist_itr = get_flist(lru_itr->freq, old_flist_itr);
            // add item to the new freq list begining as the most recently used
            new_flist_itr->splice(new_flist_itr->begin(), *old_flist_itr, lru_itr);
            
            // lru list became empty, remove its entry in the flist and the freq from the fmap
            if (old_flist_itr->empty()) {
                flist.erase(old_flist_itr);
                fmap.erase(lru_itr->freq - 1);
            }
        }
        
        int get(int key) {
            if (cap == 0) return -1;
            auto itr = c.find(key);
            if (itr == c.end()) return -1;
            
            // locate node and its old freq list
            update_freq(itr->second);
            return itr->second->value;
        }
        
        void put(int key, int value) {
            if (cap == 0) return;
            auto itr = c.find(key);
            // item exist, update value and freq
            if (itr != c.end()) {
                // locate node and its old freq list
                update_freq(itr->second);
                itr->second->value = value;
                return;
            }
            
            // cache is full, remove lru from the lfu, where the lfu
            // will be the last element in the flist
            if (c.size() == cap) {
                auto& lfu_list = flist.back();
                auto lru = lfu_list.back();
                lfu_list.pop_back();
                // no entry exist with that freq anymore, remove that lfu
                // item from both the flist and the freq from the fmap
                if (lfu_list.empty()) {
                    flist.pop_back();
                    fmap.erase(lru.freq);
                }
                c.erase(lru.key);
            }
            
            // this is a new item with freq of 1, get its
            // flist and if none exist, create one at the end
            auto flist_itr = get_flist(1, flist.end());
            // add the item to the front of the lru list
            flist_itr->push_front({ key, value, 1 });
            c[key] = flist_itr->begin();
            
        }
        
        unordered_map<int, freq_list::iterator> fmap; // map freq -> freq_list item
        unordered_map<int, lru_list::iterator> c; // map key -> lru_list item
        freq_list flist;
        size_t cap;
    };
    
    /**
     * Your LFUCache object will be instantiated and called as such:
     * LFUCache obj = new LFUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    

Log in to reply
 

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