O(1) 85 ms C++ solution


  • 0
    A
    struct HASH_TABLE_DATA;
    struct FREQ_LIST_NODE;
    
    
    using MAP = unordered_map<int, HASH_TABLE_DATA>;
    using FREQ_LIST = list<FREQ_LIST_NODE>; // from least frequently used (front of the list) to most frequently used
    using LRU_LIST = list<int /* key */>; // from lru (front of the list) to the mru
    
    
    struct HASH_TABLE_DATA {
        int value;
    
        FREQ_LIST::iterator freq_list_iter;
        LRU_LIST::iterator  lru_list_iter;
        
        HASH_TABLE_DATA(int value_) :
        value(value_)
        { }
    };
    
    
    struct FREQ_LIST_NODE {
        long frequency;
        LRU_LIST lru_list_at_this_freq;
        
        FREQ_LIST_NODE(long frequency_) : 
        frequency(frequency_)
        { }
    };
    
    
    
    
    class LFUCache {
        
    private:
        const int NOT_FOUND = -1;
        
        MAP hash_table;
        FREQ_LIST freq_list;
        
        int capacity;
        bool is_at_capacity;
        
        
        void invalidate_lfu()
        {
            // Should only be called when is_at_capacity == true
            // assert(is_at_capacity);
            
            // The first node in the freq_list corresponds to least frequently used
            auto lfu_iter = freq_list.begin();
            
            // Multiple entries can have the same frequency count so tie break by evicting lru
            // The first node in the lru_list at that frequency is the LRU
            int key_being_removed = lfu_iter->lru_list_at_this_freq.front();
    
            // Remove the evicted from the lru list
            lfu_iter->lru_list_at_this_freq.pop_front();
            
            // Remove from hash_table
            auto num_elements_removed = hash_table.erase(key_being_removed);
            // assert(num_elements_removed != 0);
            
            // If the lru list is now empty, then remove the FREQ_LIST_NODE from the freq_list
            if (lfu_iter->lru_list_at_this_freq.empty())
            {
                freq_list.pop_front();
            }
        }
        
        
        void insert_into_cache(int key, int value)
        {
            // HASH_TABLE_DATA data(value);
            // auto ret_val = hash_table.emplace(key, data);
            
            // insert into hash table
            pair<MAP::iterator, bool> retval = hash_table.emplace(
                                                    std::piecewise_construct,
                                                    std::forward_as_tuple(key),
                                                    std::forward_as_tuple(value)
                                                );
            
            HASH_TABLE_DATA & hash_table_data = retval.first->second;
            
            // Make sure there is a node in the freq_list for frequency == 1
            if (freq_list.empty() || freq_list.front().frequency != 1)
            {
                //FREQ_LIST_NODE freq_list_node(/* frequency_ = */ 1);
                freq_list.emplace_front(1);
            }
            
            // At this point, the front of the freq_list is the one with frequency == 1
    
            // Insert a new node at the MRU position of the lru list (i.e. at the back)
            freq_list.front().lru_list_at_this_freq.push_back(key);
            
            // Set the iterators in the hash_table_data
            hash_table_data.freq_list_iter = freq_list.begin();
            hash_table_data.lru_list_iter  = (--(freq_list.front().lru_list_at_this_freq.end()));
        }
        
        
        void incr_freq_and_update_freq_list(int key, HASH_TABLE_DATA & hash_table_data)
        {
            FREQ_LIST::iterator & freq_list_iter = hash_table_data.freq_list_iter;
            LRU_LIST::iterator  & lru_list_iter  = hash_table_data.lru_list_iter;
            
            int freq = freq_list_iter->frequency;
            ++freq; // new frequency
            
            // remove from the old list b/c the frequency is being incremented
            // assert(key == *lru_list_iter);
            freq_list_iter->lru_list_at_this_freq.erase(lru_list_iter);
            
            // If the lru list is now empty, then remove the FREQ_LIST_NODE from the freq_list
            if (freq_list_iter->lru_list_at_this_freq.empty())
            {
                freq_list_iter = freq_list.erase(freq_list_iter);
            }
            else
            {
                // next in the freq_list
                ++freq_list_iter;
            }
    
            if (freq_list_iter == freq_list.end() || freq_list_iter->frequency != freq)
            {
                // Insert a new node in the freq_list for the new frequency value (freq)
                freq_list_iter = freq_list.emplace(freq_list_iter, freq);
            }
            
            // Insert a new node at the MRU position of the lru list (i.e. at the back)
            freq_list_iter->lru_list_at_this_freq.push_back(key);
            
            // update the iterators stored in the hash_table_data
            hash_table_data.freq_list_iter = freq_list_iter;
            hash_table_data.lru_list_iter  = (--(freq_list_iter->lru_list_at_this_freq.end()));
        }
    
    
    public:
        LFUCache(int capacity_) : 
        capacity(capacity_),
        is_at_capacity(false)
        { }
        
        
        int get(int key)
        {
            // lookup in hash table
            // if it exists
            //      - increment frequency
            //      - update frequency list
            //      - return the value
            // if it doesn't exist
            //      - return NOT_FOUND
            
            auto iter = hash_table.find(key);
            if (iter != hash_table.end())
            {
                incr_freq_and_update_freq_list(key, iter->second);
                return (iter->second).value;
            }
            else
            {
                return NOT_FOUND;
            }
        }
        
        
        void put(int key, int value)
        {
            if (capacity <= 0)
            {
                return;
            }
            
            // lookup in hash table
            // if it exists
            //      - update the value
            //      - increment frequency
            //      - update frequency list
            // if it doesn't exist
            //      - if necessary, evict least frequently used item (tie break with least recently used)
            //      - insert new (key, value) pair
            //      - initialize frequency to 1
            //      - update frequency list
            
            auto iter = hash_table.find(key);
            if (iter != hash_table.end()) // exists
            {
                // Update the value
                (iter->second).value = value;
                
                incr_freq_and_update_freq_list(key, iter->second);
            }
            else // doesn't exist
            {
                if (is_at_capacity)
                {
                    invalidate_lfu();
                    insert_into_cache(key, value);
                }
                else
                {
                    insert_into_cache(key, value);
                    
                    // After the insertion, check if we're at capacity
                    // If so, update the boolean flag
                    if (hash_table.size() == capacity)
                    {
                        is_at_capacity = true;
                    }
                }
            }
        }
    };
    

Log in to reply
 

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