Design an LFU (Least Frequently Used) cache. On eviction, remove the least frequently used item; if tie, remove the least recently used among them. Implement get and put in O(1).
Input: ["LFUCache","put","put","get","put","get","get"], [[2],[1,1],[2,2],[1],[3,3],[2],[3]]
Output: [null,null,null,1,null,-1,3]
Explanation: key=2 is evicted (freq=1) when key=3 is put; cap=2.
Input: capacity=1; put(1,1); put(2,2); get(1)→-1; get(2)→2
Output:
Three data structures: keyMap(key→{val,freq}), freqMap(freq→LinkedHashSet of keys), and minFreq tracker.
- get: increment key frequency, update freqMap, update minFreq
- put: if capacity exceeded evict minFreq entry, then insert with freq=1
class LFUCache {
Map<Integer,Integer> keyVal = new HashMap<>(), keyFreq = new HashMap<>();
Map<Integer,LinkedHashSet<Integer>> freqKeys = new HashMap<>();
int cap, minFreq = 0;
public LFUCache(int capacity) { cap = capacity; }
public int get(int key) {
if (!keyVal.containsKey(key)) return -1;
int f = keyFreq.get(key);
keyFreq.put(key, f+1);
freqKeys.get(f).remove(key);
if (freqKeys.get(f).isEmpty()) { freqKeys.remove(f); if (minFreq==f) minFreq++; }
freqKeys.computeIfAbsent(f+1, x->new LinkedHashSet<>()).add(key);
return keyVal.get(key);
}
public void put(int key, int value) {
if (cap <= 0) return;
if (keyVal.containsKey(key)) { keyVal.put(key,value); get(key); return; }
if (keyVal.size() >= cap) {
int evict = freqKeys.get(minFreq).iterator().next();
freqKeys.get(minFreq).remove(evict);
keyVal.remove(evict); keyFreq.remove(evict);
}
keyVal.put(key,value); keyFreq.put(key,1);
freqKeys.computeIfAbsent(1, x->new LinkedHashSet<>()).add(key);
minFreq = 1;
}
}
Complexity Analysis:
Time complexity: O(1) for get and put
Space complexity: O(capacity)