LFU Cache (Go)
Topics: cache eviction, O(1) LFU, frequency buckets
Problem
Implement an LFU (Least-Frequently-Used) cache with O(1) Get/Put. On overflow, evict the
key with the lowest access frequency; break ties by least-recently-used within that
frequency.
func New[K comparable, V any](capacity int) *LFU[K, V]
func (c *LFU[K, V]) Get(key K) (V, bool)
func (c *LFU[K, V]) Put(key K, value V)
func (c *LFU[K, V]) Len() int
Get and Put on an existing key increment its frequency.- A new
Put past capacity evicts the least-frequent / least-recently-used entry first.
Put on an existing key updates the value and bumps frequency.
put 1,2 (cap 2); get(1); put(3) → evicts 2 (freq 1 < 1's freq 2)
put 1,2 (cap 2); put(3) → evicts 1 (tie at freq 1 → LRU)
Key concepts
- Frequency buckets:
map[int]*list.List — each frequency holds a doubly-linked list ordered by
recency (front = MRU, back = LRU). Moving a key on access is O(1).
minFreq tracker: the eviction list is always freqs[minFreq]; advance minFreq when a bump
empties the current minimum.- Tie-break = LRU: within the minimum-frequency list, the back element is the victim.
The entry type and pushFront are provided; you implement Get, Put, bump, and evict.
Run
go test -v -race ./challenges/lfu-cache/go/
Sign in to submit your solution.