Design a Least Frequently Used (LFU) cache. When capacity is exceeded, evict the LFU item (if tie, evict LRU among them).
LFUCache(2), put(1,1), put(2,2), get(1)→1, put(3,3) [evicts 2], get(2)→-1, get(3)→3
Two HashMaps + HashMap of LinkedHashSets. keyMap(key→val,freq), freqMap(freq→orderedSet of keys), minFreq.
- keyMap: key → [val, freq].
- freqMap: freq → LinkedHashSet (insertion-ordered for LRU within freq).
- minFreq: tracks current minimum frequency.
- On get: update freq, move key in freqMap. On put: evict minFreq first from freqMap[minFreq].
import java.util.*;
class LFUCache {
Map<Integer,int[]> keyMap = new HashMap<>(); // key -> [val, freq]
Map<Integer,LinkedHashSet<Integer>> freqMap = new HashMap<>();
int cap, minFreq;
public LFUCache(int capacity) { cap=capacity; }
private void updateFreq(int key) {
int freq = keyMap.get(key)[1];
freqMap.get(freq).remove(key);
if (freqMap.get(freq).isEmpty()) { freqMap.remove(freq); if (minFreq==freq) minFreq++; }
keyMap.get(key)[1]++;
freqMap.computeIfAbsent(freq+1, k->new LinkedHashSet<>()).add(key);
}
public int get(int key) {
if (!keyMap.containsKey(key)) return -1;
updateFreq(key); return keyMap.get(key)[0];
}
public void put(int key, int value) {
if (cap <= 0) return;
if (keyMap.containsKey(key)) { keyMap.get(key)[0]=value; updateFreq(key); return; }
if (keyMap.size() >= cap) {
int evict = freqMap.get(minFreq).iterator().next();
freqMap.get(minFreq).remove(evict); if(freqMap.get(minFreq).isEmpty()) freqMap.remove(minFreq);
keyMap.remove(evict);
}
keyMap.put(key, new int[]{value,1});
freqMap.computeIfAbsent(1, k->new LinkedHashSet<>()).add(key);
minFreq = 1;
}
}
- Time Complexity: get/put: O(1)
- Space Complexity: O(N)