LFU Cache (C)
Topics: cache eviction, frequency counting, LRU tie-break
Problem
Implement an LFU (least-frequently-used) cache of int -> int: when full,
evict the key with the lowest access frequency, breaking ties by least
recently used. Entries live in caller-provided storage (no allocation).
typedef struct { int key, val; int freq; unsigned long seq; int used; } LFUEntry;
typedef struct { LFUEntry *entries; size_t cap; size_t count; unsigned long tick; } LFU;
void lfu_init(LFU *c, LFUEntry *storage, size_t cap);
bool lfu_get(LFU *c, int key, int *out); // bump frequency + recency
void lfu_put(LFU *c, int key, int val); // insert at freq 1 / update; evict when full
size_t lfu_len(const LFU *c);
lfu_get: on a hit, increment the entry's frequency, refresh its recency,
and return the value.lfu_put: if the key exists, update its value and bump frequency. Otherwise,
evict when at capacity, then insert the new key at frequency 1.- Eviction: drop the entry with the smallest frequency; on a frequency tie,
drop the one least recently used (oldest last-touch).
Key concepts
- Two-level ordering: the victim is chosen by
(frequency, recency) — first
the minimum frequency, then the oldest access among those. A monotonic tick
stamped on every touch gives the recency tie-break.
- Insert counts as a use: a freshly inserted key starts at frequency 1, so a
brand-new key is not immediately the rarest if an older key is still at 1 —
the older one (LRU) loses the tie.
- The real O(1) shape: production LFU keeps a linked list per frequency plus a
minFreq pointer so eviction is O(1). Here a linear scan of the slots is fine —
the focus is getting the eviction policy exactly right, not the container.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/lfu && /tmp/lfu
Sign in to submit your solution.