LFU Cache — HashMap + Frequency Buckets + DLL

# Python
from collections import defaultdict, OrderedDict
class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.min_freq = 0
        self.key_val = {}
        self.key_freq = {}
        self.freq_keys = defaultdict(OrderedDict)

    def _touch(self, key):
        f = self.key_freq[key]
        self.key_freq[key] += 1
        del self.freq_keys[f][key]
        if not self.freq_keys[f] and f == self.min_freq:
            self.min_freq += 1
        self.freq_keys[f+1][key] = None

    def get(self, key):
        if key not in self.key_val: return -1
        self._touch(key)
        return self.key_val[key]

    def put(self, key, value):
        if self.cap <= 0: return
        if key in self.key_val:
            self.key_val[key] = value
            self._touch(key)
        else:
            if len(self.key_val) >= self.cap:
                evict, _ = self.freq_keys[self.min_freq].popitem(last=False)
                del self.key_val[evict]
                del self.key_freq[evict]
            self.key_val[key] = value
            self.key_freq[key] = 1
            self.freq_keys[1][key] = None
            self.min_freq = 1

// Java
class LFUCache {
    int cap, minFreq;
    Map<Integer,Integer> keyVal = new HashMap<>(), keyFreq = new HashMap<>();
    Map<Integer,LinkedHashSet<Integer>> freqKeys = new HashMap<>();

    public LFUCache(int capacity) { cap = capacity; }

    private void touch(int key) {
        int f = keyFreq.getOrDefault(key, 0);
        keyFreq.put(key, f+1);
        freqKeys.computeIfAbsent(f, k->new LinkedHashSet<>()).remove(key);
        if (freqKeys.getOrDefault(f, new LinkedHashSet<>()).isEmpty() && f == minFreq) minFreq++;
        freqKeys.computeIfAbsent(f+1, k->new LinkedHashSet<>()).add(key);
    }

    public int get(int key) {
        if (!keyVal.containsKey(key)) return -1;
        touch(key); return keyVal.get(key);
    }

    public void put(int key, int value) {
        if (cap <= 0) return;
        if (keyVal.containsKey(key)) { keyVal.put(key, value); touch(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, k->new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }
}