LFU Cache

hard linked list hash map design

Problem

Design a Least Frequently Used (LFU) cache supporting get(key) and put(key, value) in O(1). On eviction, drop the least-frequently used key; ties are broken by least-recently used among that frequency.

Inputput(1,1); put(2,2); get(1); put(3,3); get(2); — cap=2

Output1, -1

After get(1), key 1 has freq 2; put(3,3) evicts key 2 (freq 1).

capacity

ops (semicolon-separated)

from collections import defaultdict, OrderedDict
class LFUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.size = 0
        self.min_freq = 0
        self.kv = {}                # key -> (val, freq)
        self.fk = defaultdict(OrderedDict)  # freq -> OrderedDict(key -> None)
    def _bump(self, key):
        val, f = self.kv[key]
        del self.fk[f][key]
        if not self.fk[f] and f == self.min_freq: self.min_freq += 1
        self.fk[f + 1][key] = None
        self.kv[key] = (val, f + 1)
    def get(self, key):
        if key not in self.kv: return -1
        self._bump(key)
        return self.kv[key][0]
    def put(self, key, val):
        if self.cap == 0: return
        if key in self.kv:
            self.kv[key] = (val, self.kv[key][1])
            self._bump(key); return
        if self.size == self.cap:
            ev, _ = self.fk[self.min_freq].popitem(last=False)
            del self.kv[ev]; self.size -= 1
        self.kv[key] = (val, 1)
        self.fk[1][key] = None
        self.min_freq = 1
        self.size += 1

class LFUCache {
  constructor(capacity) {
    this.cap = capacity; this.size = 0; this.minFreq = 0;
    this.kv = new Map();       // key -> { val, freq }
    this.fk = new Map();       // freq -> Map(key, true) (insertion ordered)
  }
  _bucket(f) { if (!this.fk.has(f)) this.fk.set(f, new Map()); return this.fk.get(f); }
  _bump(key) {
    const e = this.kv.get(key);
    this._bucket(e.freq).delete(key);
    if (this._bucket(e.freq).size === 0 && e.freq === this.minFreq) this.minFreq++;
    e.freq++;
    this._bucket(e.freq).set(key, true);
  }
  get(key) {
    if (!this.kv.has(key)) return -1;
    this._bump(key);
    return this.kv.get(key).val;
  }
  put(key, val) {
    if (this.cap === 0) return;
    if (this.kv.has(key)) { this.kv.get(key).val = val; this._bump(key); return; }
    if (this.size === this.cap) {
      const bucket = this._bucket(this.minFreq);
      const ev = bucket.keys().next().value;
      bucket.delete(ev); this.kv.delete(ev); this.size--;
    }
    this.kv.set(key, { val, freq: 1 });
    this._bucket(1).set(key, true);
    this.minFreq = 1; this.size++;
  }
}

class LFUCache {
    int cap, size = 0, minFreq = 0;
    Map<Integer, int[]> kv = new HashMap<>();  // key -> [val, freq]
    Map<Integer, LinkedHashSet<Integer>> fk = new HashMap<>();
    public LFUCache(int capacity) { this.cap = capacity; }
    private void bump(int key) {
        int[] e = kv.get(key);
        fk.get(e[1]).remove(key);
        if (fk.get(e[1]).isEmpty() && e[1] == minFreq) minFreq++;
        e[1]++;
        fk.computeIfAbsent(e[1], k -> new LinkedHashSet<>()).add(key);
    }
    public int get(int key) {
        if (!kv.containsKey(key)) return -1;
        bump(key); return kv.get(key)[0];
    }
    public void put(int key, int val) {
        if (cap == 0) return;
        if (kv.containsKey(key)) { kv.get(key)[0] = val; bump(key); return; }
        if (size == cap) {
            int ev = fk.get(minFreq).iterator().next();
            fk.get(minFreq).remove(ev); kv.remove(ev); size--;
        }
        kv.put(key, new int[]{ val, 1 });
        fk.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
        minFreq = 1; size++;
    }
}

class LFUCache {
    int cap, sz = 0, minFreq = 0;
    unordered_map<int, pair<int, int>> kv;   // key -> (val, freq)
    unordered_map<int, list<int>> fk;        // freq -> ordered keys
    unordered_map<int, list<int>::iterator> it;
    void bump(int key) {
        auto& e = kv[key];
        fk[e.second].erase(it[key]);
        if (fk[e.second].empty() && e.second == minFreq) minFreq++;
        e.second++;
        fk[e.second].push_back(key);
        it[key] = prev(fk[e.second].end());
    }
public:
    LFUCache(int capacity) : cap(capacity) {}
    int get(int key) {
        if (!kv.count(key)) return -1;
        bump(key); return kv[key].first;
    }
    void put(int key, int val) {
        if (cap == 0) return;
        if (kv.count(key)) { kv[key].first = val; bump(key); return; }
        if (sz == cap) {
            int ev = fk[minFreq].front();
            fk[minFreq].pop_front(); kv.erase(ev); it.erase(ev); sz--;
        }
        kv[key] = { val, 1 };
        fk[1].push_back(key);
        it[key] = prev(fk[1].end());
        minFreq = 1; sz++;
    }
};

Explanation

An LFU cache evicts the key that has been used the fewest times, and if several keys tie on use-count, it drops the least recently used among them. The hard part is doing all of this in constant time per operation.

The trick is two layers of bookkeeping. A map kv stores each key's value and its current frequency. A second map fk groups keys into buckets by frequency, and each bucket keeps its keys in insertion order (using an OrderedDict / linked structure), so the oldest key in a bucket sits at the front.

Every time a key is touched, _bump moves it from its current frequency bucket up to the next one. We also track min_freq, the smallest frequency that still has keys. When a bucket empties out and it was the minimum, min_freq increases by one. This lets eviction be instant: just pop the front key of the min_freq bucket.

On put, if the key exists we update its value and bump it. If the cache is full, we evict from the min_freq bucket first, then insert the new key at frequency 1 and reset min_freq = 1 (a brand-new key is the least frequently used).

Example (capacity 2): put(1,1), put(2,2), then get(1) raises key 1 to freq 2. Now put(3,3) is full, so it evicts the freq-1 key, which is key 2. A later get(2) returns -1 while get(1) returns 1.

Time: O(1) per get and put Space: O(capacity)