LFU Cache 370 ms clean Java solution with Maps


  • 0

    Free to look at this solution for inspiration. Any suggestions and corrections are welcomed!

    private final Map<Integer, FreqValue> keyValueCache = new HashMap<>();
    // queue ensures the first added (LRU) key will be removed from the cache
    private final NavigableMap<Integer, Queue<Integer>> freqKeys = new TreeMap<>();
    private final int capacity;
    private final int NO_KEY = -1;
    
    private class FreqValue {
    	int freq = 0;
    	int value;
    }
    
    public LFUCache(int capacity) {
    	this.capacity = capacity;
    }
    
    public int get(int key) {
    	if (keyValueCache.containsKey(key)) {
    		updateFreqFor(key, keyValueCache.get(key));
    		return keyValueCache.get(key).value;
    	}
    	return NO_KEY;
    }
    
    public void set(int key, int value) {
    	if (keyValueCache.size() >= capacity && capacity > 0 && !keyValueCache.containsKey(key))		
    		removeLRUEntry();
    	
    	if(keyValueCache.size() < capacity || keyValueCache.containsKey(key)){
    		updateCacheWith(key, value);
    		updateFreqFor(key, keyValueCache.get(key));
    	}
    }
    
    public void removeLRUEntry(){
    	Queue<Integer> q = freqKeys.firstEntry().getValue();
    		if (!q.isEmpty())
    			keyValueCache.remove(q.remove());
    }
    
    private void updateFreqFor(Integer key, FreqValue fv) {
    	if (freqKeys.containsKey(fv.freq)) {
    		Queue<Integer> q = freqKeys.get(fv.freq);
    		if(!q.isEmpty()) q.remove(key);
    		if(q.isEmpty()) freqKeys.remove(fv.freq);
    	}
    	fv.freq++;
    	if (!freqKeys.containsKey(fv.freq)) freqKeys.put(fv.freq, new LinkedList<>());
    
    	freqKeys.get(fv.freq).add(key);
    }
    
    private void updateCacheWith(int key, int value) {
    	FreqValue fv = new FreqValue();
    	if (keyValueCache.containsKey(key)) fv = keyValueCache.get(key);
    
    	fv.value = value;
    	keyValueCache.put(key, fv);
    }
    

Log in to reply
 

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