« back

LFU Cache

Tags : leetcode, hash, linkedlist, cpp, hard

Problem Statement - link #

Design and implement a data structure for a Least Frequently Used (LFU) cache.

Implement the LFUCache class:

To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.

When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.

The functions get and put must each run in O(1) average time complexity.

Examples #

Example 1:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

Explanation
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is  most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // return 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // return -1 (not found)
lfu.get(3);      // return 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // return 4
                 // cache=[4,3], cnt(4)=2, cnt(3)=3

Constraints #

Solutions #

class LFUCache {
public:
  
    unordered_map <int,list<pair<int,int>>> lst_map;                    //will store frequency as key and list of all <key,value> with that frequency
    unordered_map <int,list<pair<int,int>>::iterator> key_map;          //will store key and it's respective address
    unordered_map <int,int> frequency_map;                              //will store key and it's frequency
    int cap=0,size=0,min_frequency=0;
    
    LFUCache(int capacity)
    {
        cap=capacity;
    }
    
    int get(int key) 
    {
      
        auto found= key_map.find(key);
        if(found==key_map.end())
            return -1;
        else
        {   auto temp = found->second->second;
            put(key,temp);
            return temp;
            
        }
    };
    
    void put(int key, int value) 
    {
        
        auto found = key_map.find(key);
        if(found== key_map.end()) 
        {   if(cap!=0)
            {  
            if(size>=cap)
            {                                                    //removing page
               auto temp = lst_map[min_frequency].back();        //making copy of popped element
               lst_map[min_frequency].pop_back();                //popping it out
               key_map.erase(temp.first);                        //popping from key_map
               frequency_map.erase(temp.first);                  //popping from frequency_map;
                                                                 // done removing
            }
            else
                size++;
            lst_map[1].emplace_front(make_pair(key,value));      // adding node in list
            min_frequency=1;
            key_map[key]= lst_map[1].begin();                    // adding new key iterator pair in key map
            frequency_map[key]=1;
            
        }
        }
        else
        {
            auto frequency = frequency_map[key];
            lst_map[frequency].erase(found->second);             //removed from old list
            if(lst_map[frequency].size()==0)                     //in case list becomes empty it might change min_frequency
            {
                if(min_frequency ==frequency)
                    min_frequency++;
            }
            lst_map[++frequency].emplace_front(key,value);       //added in new list
            key_map[key]=lst_map[frequency].begin();             //updated in keymap
            frequency_map[key]=frequency; 
            
        }
    }
    
};