LFU Cache (Rust)
Topics: cache eviction, LFU, ordered index
Problem
Implement an LFU (Least-Frequently-Used) cache. On overflow, evict the key with the lowest
access frequency; break ties by least-recently-used within that frequency.
pub struct Lfu { /* … */ }
impl Lfu {
pub fn new(capacity: usize) -> Self;
pub fn get(&mut self, key: i32) -> Option<i32>;
pub fn put(&mut self, key: i32, val: i32);
pub fn len(&self) -> usize;
}
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
- Ordered index: key the cache by
(freq, seq) in a BTreeMap, where seq is a monotonic
counter. The smallest pair — lowest frequency, then oldest — is exactly the eviction victim, so
eviction is order.pop_first().
- Reinsert on access: to bump a key, remove its
(freq, seq) slot and re-add it at (freq + 1, new_seq), making it the most recent within its new frequency.
- Tradeoff: this is O(log n) (vs Go's O(1) frequency lists) but much simpler — the LRU port
makes the same clarity-over-asymptotics choice.
new, len, and next_seq are provided; you implement get, put, and reinsert.
Grading
Your solution.rs is compiled together with a trusted tests.rs (which include!s it) using
rustc --test. Only solution.rs is yours to edit.
Sign in to submit your solution.