using TreeMap and HashMap


  • 1
    K

    public class LFUCache {
    TreeMap<Integer,LinkedHashMap<Integer,Integer>> tmap; //stores frequency as key and data as value in a map
    HashMap<Integer,Integer> hmap; //store data Key as key and frequency as value
    int capacity;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        tmap = new TreeMap<>();
        hmap = new HashMap<>();
    }
    
    public int get(int key) {
        if(!hmap.containsKey(key)||capacity==0) return -1;
        
        int freq = hmap.get(key);
        int value = tmap.get(freq).get(key);
        
        tmap.get(freq).remove(key);
        if(tmap.get(freq).size()==0) 
            tmap.remove(freq);
        
        hmap.put(key,freq+1);
        LinkedHashMap<Integer,Integer> temp = tmap.getOrDefault(freq+1,new LinkedHashMap<>());
        temp.put(key,value);
        tmap.put(freq+1,temp);
        
        return value;
    }
    
    public void put(int key, int value) {
        if(capacity==0) return;
        if(hmap.size()==capacity && !hmap.containsKey(key)){ //when new data has to be inserted, we need to remove the oldest entry
            Map.Entry<Integer,LinkedHashMap<Integer,Integer>> entry = tmap.firstEntry();
            Integer k = entry.getValue().entrySet().iterator().next().getKey();
            hmap.remove(k);
            entry.getValue().remove(k);
            if(entry.getValue().size()==0)
                tmap.remove(entry.getKey());
        }
        else if(hmap.containsKey(key)){
            int freq = hmap.get(key);
            tmap.get(freq).remove(key);
            if(tmap.get(freq).size()==0) 
                tmap.remove(freq);
        }
        
        int freq = hmap.getOrDefault(key,0) + 1;
        hmap.put(key,freq);
        
        LinkedHashMap<Integer,Integer> temp = tmap.getOrDefault(freq,new LinkedHashMap<>());
        temp.put(key,value);
        tmap.put(freq,temp);
    }
    

    }

    /**

    • 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.