Java O(1) Using LinkedHashMap, HashMap and Stack. Clear code.


  • 0
    Y

    Idea is keeping all entires having same level in a LinkedHashMap. Stack is used for the least level (LFU will be removed from that level). levelMap will be used to determine, what is the level of a key.

    public class LFUCache {

    private int capacity;
    private int size;
    private Map<Integer, LinkedHashMap<Integer, Integer>> levelLinkedMap;
    private Map<Integer, Integer> levelMap;
    private Deque<Integer> minLevels;
    
    public LFUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        levelMap = new HashMap<>();
        levelLinkedMap = new HashMap<>();
        minLevels = new LinkedList<>();
    }
    
    public int get(int key) {
        if(!levelMap.containsKey(key))
            return -1;
        update(key, null);
        return levelLinkedMap.get(levelMap.get(key)).get(key);
    }
    
    private void put(int level, int key, int value){
        levelMap.put(key, level);
        if(minLevels.size() == 0 || minLevels.getFirst() > level){
            minLevels.addFirst(level);
        }
        
        if(!levelLinkedMap.containsKey(level))
            levelLinkedMap.put(level, new LinkedHashMap<>());
        
        levelLinkedMap.get(level).put(key, value);
    }
    
    private void update(int key, Integer value){
        int oldLevel = levelMap.get(key);
        int oldValue = levelLinkedMap.get(levelMap.get(key)).get(key);
        if(value == null)
            value = oldValue;
            
        levelMap.put(key, oldLevel+1);
        levelLinkedMap.get(oldLevel).remove(key);
        checkLevel(oldLevel);
        put(oldLevel+1, key, value);
    }
    
    private void checkLevel(int level){
        if(levelLinkedMap.get(level).size() == 0){
            levelLinkedMap.remove(level);
            if(minLevels.size() > 0 && minLevels.getFirst() == level)
                minLevels.removeFirst();
        }
    }
    
    private void removeLFU(){
        int level = minLevels.getFirst();
        int key = levelLinkedMap.get(level).keySet().iterator().next();
    
        levelMap.remove(key);
        levelLinkedMap.get(level).remove(key);
        checkLevel(level);
        size--;
    }
    
    public void set(int key, int value) {
        if(this.capacity == 0)
            return;
        if(this.size == this.capacity && !levelMap.containsKey(key))
            removeLFU();
            
        if(!levelMap.containsKey(key)){
            put(1, key, value);
            size++;
        }
        else{
            update(key, value);
        }
        
    }
    

    }


Log in to reply
 

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