Java O(1) using two HashMap and a LinkedHashSet


  • 0
    S
    class CacheNode {
        int key;
        int value;
        int freq;
    
        public CacheNode (int key, int value) {
            this.key = key;
            this.value = value;
            this.freq = 1;
        }
    }
    
    int tailFreq;
    int capacity;
    Map<Integer, LinkedHashSet> freqMap; 
    Map<Integer, CacheNode> map;
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        freqMap = new HashMap<>();
        tailFreq = -1;
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        
        if ( !map.containsKey(key) ) {
            // a new item
            LinkedHashSet<CacheNode> s = null;
    
            // over capacity
            if (map.size() == capacity) {
                s = freqMap.get(tailFreq);
                CacheNode tailNode = null;
                for (CacheNode cn:s) {
                    tailNode = cn;
                    break;
                }
                
                if (tailNode != null) {
                    int size = s.size();
                    if (size == 1) {
                        freqMap.remove(1);
                    }
    
                    s.remove(tailNode);
                    map.remove(tailNode.key);
                }
            }
            
            CacheNode n = new CacheNode(key, value);
            map.put(key, n);
            
            if (freqMap.containsKey(1)) {
                s = freqMap.get(1);
            } else {
                s = new LinkedHashSet<>();
            }
            s.add(n);
            freqMap.put(1, s);
            
            tailFreq = 1;
        } else {
            CacheNode n = map.get(key);
            n.value = value;
            update(n);
        }
    
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
    
        CacheNode n = map.get(key);
        update(n);
        return n.value;
    }
    
    private void update(CacheNode n) {
        int freq = n.freq;
        
        // delete n from freq
        LinkedHashSet<CacheNode> s =  freqMap.get(freq);
    
        int size = s.size();
        if (size == 1) {
            freqMap.remove(freq);
        } else {
            s.remove(n);
            freqMap.put(freq, s);
        }
        
        // add n onto freqPlus
        int freqPlus = freq + 1;
        n.freq = freqPlus;
        if (!freqMap.containsKey(freqPlus)) {
            s = new LinkedHashSet<>();
        } else {
            s = freqMap.get(freqPlus);
        }
        s.add(n);
        freqMap.put(freqPlus, s);
        
        if (tailFreq == freq && !freqMap.containsKey(freq)) {
            tailFreq = freqPlus;
        }
    }  
    

Log in to reply
 

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