LFU Cache

class LFUCache {
    int cap, minFreq = 0;
    unordered_map<int, tuple<int,int,list<int>::iterator>> kv; // key -> {val, freq, it}
    unordered_map<int, list<int>> buckets; // freq -> LRU list of keys
    void touch(int key) {
        auto& [val, f, it] = kv[key];
        buckets[f].erase(it);
        if (buckets[f].empty() && f == minFreq) ++minFreq;
        ++f;
        buckets[f].push_front(key);
        it = buckets[f].begin();
    }
public:
    LFUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        if (!kv.count(key)) return -1;
        int v = get<0>(kv[key]);
        touch(key);
        return v;
    }
    void put(int key, int value) {
        if (cap == 0) return;
        if (kv.count(key)) {
            get<0>(kv[key]) = value;
            touch(key);
            return;
        }
        if ((int)kv.size() == cap) {
            int evict = buckets[minFreq].back();
            buckets[minFreq].pop_back();
            kv.erase(evict);
        }
        buckets[1].push_front(key);
        kv[key] = {value, 1, buckets[1].begin()};
        minFreq = 1;
    }
};

import "container/list"

type lfuEntry struct {
    key, val, freq int
    elem           *list.Element
}

type LFUCache struct {
    cap, minFreq int
    kv           map[int]*lfuEntry
    buckets      map[int]*list.List
}

func Constructor(capacity int) LFUCache {
    return LFUCache{
        cap:     capacity,
        kv:      map[int]*lfuEntry{},
        buckets: map[int]*list.List{},
    }
}

func (c *LFUCache) touch(e *lfuEntry) {
    c.buckets[e.freq].Remove(e.elem)
    if c.buckets[e.freq].Len() == 0 {
        delete(c.buckets, e.freq)
        if e.freq == c.minFreq {
            c.minFreq++
        }
    }
    e.freq++
    if _, ok := c.buckets[e.freq]; !ok {
        c.buckets[e.freq] = list.New()
    }
    e.elem = c.buckets[e.freq].PushFront(e.key)
}

func (c *LFUCache) Get(key int) int {
    e, ok := c.kv[key]
    if !ok {
        return -1
    }
    c.touch(e)
    return e.val
}

func (c *LFUCache) Put(key, value int) {
    if c.cap == 0 {
        return
    }
    if e, ok := c.kv[key]; ok {
        e.val = value
        c.touch(e)
        return
    }
    if len(c.kv) == c.cap {
        b := c.buckets[c.minFreq]
        back := b.Back()
        evict := back.Value.(int)
        b.Remove(back)
        if b.Len() == 0 {
            delete(c.buckets, c.minFreq)
        }
        delete(c.kv, evict)
    }
    if _, ok := c.buckets[1]; !ok {
        c.buckets[1] = list.New()
    }
    e := &lfuEntry{key: key, val: value, freq: 1}
    e.elem = c.buckets[1].PushFront(key)
    c.kv[key] = e
    c.minFreq = 1
}

from collections import OrderedDict, defaultdict

class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.min_freq = 0
        self.kv: dict = {}  # key -> (value, freq)
        self.buckets: dict = defaultdict(OrderedDict)  # freq -> OrderedDict[key, None]

    def _touch(self, key: int) -> None:
        value, freq = self.kv[key]
        del self.buckets[freq][key]
        if not self.buckets[freq]:
            del self.buckets[freq]
            if freq == self.min_freq:
                self.min_freq += 1
        self.kv[key] = (value, freq + 1)
        self.buckets[freq + 1][key] = None

    def get(self, key: int) -> int:
        if key not in self.kv:
            return -1
        value = self.kv[key][0]
        self._touch(key)
        return value

    def put(self, key: int, value: int) -> None:
        if self.cap == 0:
            return
        if key in self.kv:
            _, freq = self.kv[key]
            self.kv[key] = (value, freq)
            self._touch(key)
            return
        if len(self.kv) == self.cap:
            evict_key, _ = self.buckets[self.min_freq].popitem(last=False)
            if not self.buckets[self.min_freq]:
                del self.buckets[self.min_freq]
            del self.kv[evict_key]
        self.kv[key] = (value, 1)
        self.buckets[1][key] = None
        self.min_freq = 1

class LFUCache {
    constructor(capacity) {
        this.cap = capacity;
        this.minFreq = 0;
        this.kv = new Map(); // key -> { value, freq }
        this.buckets = new Map(); // freq -> Map (used as ordered LRU; insertion order)
    }
    _touch(key) {
        const entry = this.kv.get(key);
        const f = entry.freq;
        const bucket = this.buckets.get(f);
        bucket.delete(key);
        if (bucket.size === 0) {
            this.buckets.delete(f);
            if (f === this.minFreq) this.minFreq++;
        }
        entry.freq = f + 1;
        if (!this.buckets.has(f + 1)) this.buckets.set(f + 1, new Map());
        this.buckets.get(f + 1).set(key, true);
    }
    get(key) {
        if (!this.kv.has(key)) return -1;
        const v = this.kv.get(key).value;
        this._touch(key);
        return v;
    }
    put(key, value) {
        if (this.cap === 0) return;
        if (this.kv.has(key)) {
            this.kv.get(key).value = value;
            this._touch(key);
            return;
        }
        if (this.kv.size === this.cap) {
            const bucket = this.buckets.get(this.minFreq);
            const evictKey = bucket.keys().next().value;
            bucket.delete(evictKey);
            if (bucket.size === 0) this.buckets.delete(this.minFreq);
            this.kv.delete(evictKey);
        }
        this.kv.set(key, { value, freq: 1 });
        if (!this.buckets.has(1)) this.buckets.set(1, new Map());
        this.buckets.get(1).set(key, true);
        this.minFreq = 1;
    }
}

class LFUCache {
    private static class Entry {
        int value, freq;
        Entry(int value, int freq) { this.value = value; this.freq = freq; }
    }

    private final int cap;
    private int minFreq;
    private final Map<Integer, Entry> kv;
    private final Map<Integer, LinkedHashSet<Integer>> buckets;

    public LFUCache(int capacity) {
        this.cap = capacity;
        this.minFreq = 0;
        this.kv = new HashMap<>();
        this.buckets = new HashMap<>();
    }

    private void touch(int key) {
        Entry e = kv.get(key);
        int f = e.freq;
        LinkedHashSet<Integer> bucket = buckets.get(f);
        bucket.remove(key);
        if (bucket.isEmpty()) {
            buckets.remove(f);
            if (f == minFreq) minFreq++;
        }
        e.freq = f + 1;
        buckets.computeIfAbsent(f + 1, k -> new LinkedHashSet<>()).add(key);
    }

    public int get(int key) {
        if (!kv.containsKey(key)) return -1;
        int v = kv.get(key).value;
        touch(key);
        return v;
    }

    public void put(int key, int value) {
        if (cap == 0) return;
        if (kv.containsKey(key)) {
            kv.get(key).value = value;
            touch(key);
            return;
        }
        if (kv.size() == cap) {
            LinkedHashSet<Integer> bucket = buckets.get(minFreq);
            int evictKey = bucket.iterator().next();
            bucket.remove(evictKey);
            if (bucket.isEmpty()) buckets.remove(minFreq);
            kv.remove(evictKey);
        }
        kv.put(key, new Entry(value, 1));
        buckets.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1;
    }
}

interface LFUEntry {
    value: number;
    freq: number;
}

class LFUCache {
    private cap: number;
    private minFreq: number;
    private kv: Map<number, LFUEntry>;
    private buckets: Map<number, Map<number, true>>;

    constructor(capacity: number) {
        this.cap = capacity;
        this.minFreq = 0;
        this.kv = new Map();
        this.buckets = new Map();
    }

    private touch(key: number): void {
        const entry = this.kv.get(key) as LFUEntry;
        const f = entry.freq;
        const bucket = this.buckets.get(f) as Map<number, true>;
        bucket.delete(key);
        if (bucket.size === 0) {
            this.buckets.delete(f);
            if (f === this.minFreq) this.minFreq++;
        }
        entry.freq = f + 1;
        if (!this.buckets.has(f + 1)) this.buckets.set(f + 1, new Map());
        (this.buckets.get(f + 1) as Map<number, true>).set(key, true);
    }

    get(key: number): number {
        if (!this.kv.has(key)) return -1;
        const v = (this.kv.get(key) as LFUEntry).value;
        this.touch(key);
        return v;
    }

    put(key: number, value: number): void {
        if (this.cap === 0) return;
        if (this.kv.has(key)) {
            (this.kv.get(key) as LFUEntry).value = value;
            this.touch(key);
            return;
        }
        if (this.kv.size === this.cap) {
            const bucket = this.buckets.get(this.minFreq) as Map<number, true>;
            const evictKey = bucket.keys().next().value as number;
            bucket.delete(evictKey);
            if (bucket.size === 0) this.buckets.delete(this.minFreq);
            this.kv.delete(evictKey);
        }
        this.kv.set(key, { value, freq: 1 });
        if (!this.buckets.has(1)) this.buckets.set(1, new Map());
        (this.buckets.get(1) as Map<number, true>).set(key, true);
        this.minFreq = 1;
    }
}