Design an LFU Cache
Least-Frequently-Used eviction in O(1) with frequency buckets — the harder cousin of LRU.
Problem Statement
Design a fixed-capacity LFU cache that supports get and put in O(1) average time. When the cache is full, inserting a new key must evict the entry with the lowest access frequency. If multiple entries share that minimum frequency, evict the least recently used entry among only that frequency bucket.
The interview-standard design combines three maps: key to node for direct lookup, key to frequency for the current count, and frequency to a recency-ordered doubly linked list. A minFreq pointer tells eviction which bucket to inspect without scanning counts.
Business context
LFU Cache is the harder cousin of LRU. It appears in cache-heavy interviews because it tests whether the candidate can preserve O(1) operations while maintaining more than one ordering dimension: frequency first, recency second.
Real services use frequency-aware policies when stable hot keys should survive short bursts. A product-catalog cache, feature-flag cache, or recommendation cache may prefer an object read thousands of times yesterday over an object touched once just now. The key lesson is that eviction policy is part of the data model, not an afterthought bolted onto a HashMap.
Functional Requirements
Initialize the cache with a positive fixed capacity.
Return the cached value for an existing key in O(1) average time.
Return a miss value for an absent key without changing cache state.
Increment a key's frequency after every successful get.
Insert a new key-value pair with frequency 1 when capacity is available.
Update an existing key's value and treat the update as an access.
When full, evict the key with the smallest frequency.
Break equal-frequency ties by LRU order inside that frequency bucket.
Maintain minFreq so eviction never scans all buckets.
Expose a small demo that proves frequency promotion and recency tie-breaking.
Non-Functional Requirements
O(1) average operations
Get and put must use HashMap lookup plus constant-time list movement. No operation should scan all entries, all frequencies, or a whole bucket.
Correct eviction
The victim must come from the current minFreq bucket, and specifically from that bucket's least-recent side. Frequency order has priority over global recency.
Bounded memory
The cache stores at most capacity entries. Auxiliary state is linear in capacity: one node, one key-to-node entry, one key-to-frequency entry, and membership in one frequency list per cached key.
Invariant safety
A key must appear in exactly one frequency bucket at a time, and keyToFrequency must agree with that bucket. Promotion is remove from old bucket, update count, add to new bucket.
Thread-safety awareness
The reference implementation synchronizes public methods so the three maps and frequency lists are updated atomically. Production systems may replace this with lock striping or segmented caches.
Generic key and value support
The cache should work with any immutable, hashable key and non-null value type supported by Java's HashMap.
Requirement Clarification
QWhat should get return on a miss?
The generic Java implementation returns null and rejects null values, so null unambiguously means miss. An integer interview API can return -1 instead.
QDoes put for an existing key increase frequency?
Yes. Updating an existing key is a cache access. It changes the value, promotes the key to the next frequency, and makes it most recent in the new bucket.
QHow are ties resolved among keys with the same frequency?
Use LRU order inside each frequency bucket. The most recently touched key is stored near the front; eviction removes from the tail side of the minFreq bucket.
QCan we scan frequencies during eviction?
No. Scanning breaks the O(1) requirement. The cache maintains minFreq eagerly whenever a key is inserted, promoted, or evicted.
QWhat happens when the cache capacity is zero or negative?
The constructor rejects non-positive capacity. A zero-capacity variant can be built, but it distracts from the core LFU invariants in an interview.
QWhy not use only a HashMap from key to value and key to count?
Counts alone identify the minimum frequency but not the least-recent key inside that frequency. The frequency-to-list map supplies constant-time tie-breaking.
UML Class Diagram
Sequence Diagram
Entity Identification
LFUCache
Public facade and invariant owner. It coordinates the three maps, owns minFrequency, and exposes synchronized get, put, and size methods.
Node
Internal cache entry stored inside exactly one frequency list. It carries the key for eviction cleanup, the value for reads, and previous/next pointers for O(1) movement.
DoublyLinkedList
Recency bucket for one frequency. Its front side is most recent and its tail side is least recent, so tie-breaking inside a frequency is constant-time.
keyToNode map
Maps each key to its node so get, update, and promotion start in O(1) average time.
keyToFrequency map
Stores the current access count for every key. It avoids placing frequency state in external scans and makes promotion a direct old-count lookup.
frequencyToNodes map
Maps each frequency to its recency-ordered bucket. Empty buckets are removed so minFrequency points only at a live bucket.
minFrequency pointer
Tracks the smallest frequency currently present in the cache. Insert resets it to 1; promotion advances it only when the old minimum bucket becomes empty.
Client
Uses the cache through a simple get and put API without manipulating buckets, counts, or list nodes directly.
Design Patterns Used
LFU is an eviction strategy: choose the smallest frequency first, then LRU within that bucket. Naming it as a strategy helps compare it cleanly with LRU, FIFO, TTL, and weighted policies.
Each frequency bucket exposes an iterator for diagnostics and demos without exposing mutable pointers. The core operations still remove by node reference, while traversal is a safe read-only view.
Clients see only get and put. The cache hides three maps, frequency buckets, promotion, and eviction behind one compact API so callers cannot corrupt internal state.
Step-by-Step Design
1Start with the LFU invariant
Every live key must have one node, one frequency count, and membership in exactly one list whose frequency equals that count. minFrequency must equal the smallest non-empty bucket.
2Store entries as removable list nodes
The key is stored in the node because eviction starts from a list tail and then must delete the matching map entries in O(1).
final class Node<K, V> { final K key; V value; Node<K, V> prev; Node<K, V> next; }3Make each frequency bucket an LRU list
Inside a frequency, most recent entries are added after the head sentinel and eviction removes from the tail sentinel side. This is the same tie-breaker idea as an LRU cache, scoped to one count.
void addMostRecent(Node<K, V> node) { Node<K, V> first = head.next; node.prev = head; node.next = first; head.next = node; first.prev = node; size++; }4Promote on every hit or update
Promotion removes the node from its old frequency bucket, increments keyToFrequency, and inserts the node as most recent in the next bucket. If the old bucket was minFrequency and becomes empty, advance minFrequency by one.
private void promote(K key, Node<K, V> node) { int oldFrequency = keyToFrequency.get(key); DoublyLinkedList<K, V> oldList = frequencyToNodes.get(oldFrequency); oldList.remove(node); if (oldList.isEmpty()) { frequencyToNodes.remove(oldFrequency); if (oldFrequency == minFrequency) { minFrequency++; } } int newFrequency = oldFrequency + 1; keyToFrequency.put(key, newFrequency); bucketFor(newFrequency).addMostRecent(node); }5Evict from the minimum frequency bucket
When inserting into a full cache, look up the minFrequency bucket and remove its least-recent node. This picks the LFU victim and handles equal-frequency ties in one constant-time step.
6Reset the minimum on new insert
Every new key starts with frequency 1. After inserting it, minFrequency must be set to 1, even if the previous minimum was higher because all old keys had been promoted.
7Keep synchronization at the public boundary
The three maps and bucket lists form one logical state machine. The sample synchronizes get, put, size, and debug reads so no caller can observe a half-promoted key.
Complete Java Implementation
Explanation of Every Class
Node
Package-private generic cache entry. It stores key and value plus previous and next links. Frequency intentionally lives in keyToFrequency so the design mirrors the three-map LFU invariant.
DoublyLinkedList
One recency bucket for one frequency. It uses dummy head and tail sentinels, supports O(1) add, remove, and remove-least-recent, and implements Iterable for safe diagnostics.
LFUCache
Generic fixed-capacity LFU cache. It coordinates keyToNode, keyToFrequency, frequencyToNodes, and minFrequency so get, update, insert, promotion, and eviction remain O(1) average time.
Main
Executable demo that creates a capacity-2 cache, promotes keys through reads, evicts the only frequency-1 key, then demonstrates LRU tie-breaking among keys with frequency 2.
Dry Run
Sample input
Capacity 2. Actions: put(1,A), put(2,B), get(1), put(3,C), get(3), put(4,D), get(1), get(3), get(4). Buckets are shown most recent to least recent within each frequency.
| Step | Operation | Return | minFreq | Frequency buckets | Explanation |
|---|---|---|---|---|---|
| 1 | put(1,A) | - | 1 | f1: [1] | Insert key 1 with frequency 1. |
| 2 | put(2,B) | - | 1 | f1: [2, 1] | Key 2 is most recent inside frequency 1. |
| 3 | get(1) | A | 1 | f1: [2]; f2: [1] | Key 1 moves from frequency 1 to frequency 2. |
| 4 | put(3,C) | - | 1 | f1: [3]; f2: [1] | Cache was full; key 2 was the only key in minFreq bucket 1, so it was evicted. |
| 5 | get(3) | C | 2 | f2: [3, 1] | The frequency 1 bucket becomes empty, so minFreq advances to 2. |
| 6 | put(4,D) | - | 1 | f1: [4]; f2: [3] | Keys 1 and 3 both had frequency 2; key 1 was less recent, so it was evicted before inserting key 4. |
| 7 | get(1) | null | 1 | f1: [4]; f2: [3] | Miss after eviction; state does not change. |
| 8 | get(3) | C | 1 | f1: [4]; f3: [3] | Key 3 is promoted from frequency 2 to frequency 3. |
| 9 | get(4) | D | 2 | f2: [4]; f3: [3] | Key 4 leaves frequency 1, so minFreq advances to 2. |
Step 6 is the core LFU moment. Frequency chooses the bucket first, and recency breaks the tie inside that bucket. Even though key 3 was read more recently than key 1 at the same frequency, key 1 is the victim.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| get hit | O(1) average | O(1) | HashMap lookup plus one constant-time removal and one constant-time insertion between frequency buckets. |
| get miss | O(1) average | O(1) | Only keyToNode lookup is needed. |
| put existing key | O(1) average | O(1) | Update the value, then run the same promotion path as a hit. |
| put new key with space | O(1) average | O(1) | Create one node, write two key maps, add to frequency 1, and set minFreq to 1. |
| put new key when full | O(1) average | O(1) | Remove the tail of the minFreq bucket, delete its map entries, then insert the new key at frequency 1. |
| cache storage | - | O(capacity) | One node, two key-based map entries, and one bucket membership per cached key. |
The O(1) claim assumes average O(1) HashMap operations and direct node removal from doubly linked lists. The diagnostic toString sorts frequencies for readability and is intentionally outside the cache API complexity guarantee.
Extensibility
Pluggable eviction policy
Extract promotion and eviction behind an EvictionPolicy interface. LFU, LRU, FIFO, TTL, and weighted policies can then share a storage layer while changing only policy behavior.
LinkedHashSet buckets
For interview pseudocode, a map from frequency to LinkedHashSet of keys is a compact alternative: remove and add keys in O(1), and evict the first key in the minimum-frequency set.
Metrics
Add hit, miss, promotion, and eviction counters inside the synchronized methods. This is useful for validating whether LFU is actually outperforming LRU.
TTL or expiry
Add expiry metadata to nodes and treat expired entries as misses. Expiry cleanup must remove from all three maps and the frequency bucket just like eviction.
Weighted capacity
Replace entry count with total weight, such as bytes. Eviction may need to remove several LFU victims until the cache is under budget.
Concurrency scaling
Segment the cache by key hash so independent keys do not share one lock. Each segment keeps its own maps, buckets, and minFrequency.
Alternative Designs
HashMap plus frequency to LinkedHashSet
Store values in a key map, counts in a key-to-frequency map, and each frequency bucket as a LinkedHashSet of keys. The set's iteration order supplies LRU tie-breaking.
Tradeoffs
This is concise in Java but less explicit about node removal. The custom doubly linked list is clearer for pointer-invariant interviews and supports storing values directly in nodes.
Single ordered tree by frequency and timestamp
Maintain all entries in a balanced tree ordered by frequency first and timestamp second.
Tradeoffs
Eviction is easy to reason about, but get and put become O(log n) because every access removes and reinserts an entry with a new ordering key.
Min-heap of frequency records
Push a record every time a key changes frequency and lazily discard stale heap entries during eviction.
Tradeoffs
This avoids list wiring but gives O(log n) updates, needs stale-entry cleanup, and makes exact recency tie-breaking more error-prone.
Plain LRU cache
Evict the least recently used key globally, ignoring frequency.
Tradeoffs
LRU is simpler and often good for recency-heavy workloads, but it can evict a historically hot key after a short burst of one-time reads.
Common Mistakes
- ×
Scanning all keys to find the minimum frequency, which violates O(1).
- ×
Tracking frequency counts but forgetting recency order inside the same count.
- ×
Forgetting to update minFrequency when the old minimum bucket becomes empty.
- ×
Not resetting minFrequency to 1 after inserting a new key.
- ×
Creating a new node for an existing key instead of updating and promoting the old node.
- ×
Removing a victim from the bucket but forgetting to remove it from both key maps.
- ×
Leaving empty frequency buckets around and later evicting from an empty list.
- ×
Claiming thread safety while promotion updates three structures without a shared lock.
- ×
Treating a put update as value-only and not increasing the frequency.
Follow-up Interview Questions
QWhy is **minFrequency** necessary?
Without it, eviction would need to scan frequencies to find the smallest non-empty bucket. minFrequency makes the victim bucket a direct O(1) lookup.
QHow exactly do you update **minFrequency** during promotion?
After removing the node from its old bucket, if that bucket is empty and the old frequency equals minFrequency, increment minFrequency. The promoted key moves to old plus one, so the next possible minimum is one higher unless a new key is inserted.
QWhy is LRU tie-breaking needed inside a frequency bucket?
LFU alone can identify a lowest count but not a unique victim. Recency gives deterministic, fair eviction among keys with equal frequency and is expected by the standard LFU cache problem.
QHow does LFU differ from LRU?
LFU evicts the lowest access count and uses recency only as a tie-breaker. LRU ignores counts and evicts the globally oldest recent access.
QCan the frequency counter overflow?
Yes in a very long-running process. Production caches may periodically age counters, cap frequencies, or use windowed LFU so ancient popularity does not dominate forever.
QHow would you make this cache highly concurrent?
Use lock striping or segmented LFU caches so unrelated keys mutate separate map and bucket sets. Exact global LFU under high concurrency is expensive, so production designs often accept approximate policies.
Production Considerations
Counter aging
Pure LFU can keep old hot keys forever. Add decay, reset windows, or TinyLFU-style admission so recent workload changes can replace stale winners.
Lock contention
A synchronized cache is correct and interview-friendly but serializes all hits. High-throughput systems use segments, striped locks, or specialized libraries.
Memory pressure
Each entry carries node pointers and two key maps. For large caches, consider primitive-specialized maps, weighted capacity, or off-heap storage.
Observability
Expose hit rate, miss rate, eviction count, average frequency, and frequency-bucket sizes. LFU is only worth its complexity if these metrics beat simpler policies.
Key equality
Keys must be immutable with stable equals and hashCode. A mutable key can make map lookup fail even though a node still exists in a bucket.
Eviction callbacks
Real caches often notify listeners or release resources on eviction. Run blocking callbacks outside the hot lock, or enqueue them for asynchronous processing.
Testing invariants
Tests should verify map size, bucket membership, minFrequency, promotion after get, promotion after update, and LRU tie-breaking at equal frequency.
What Interviewers Look For
Lead with the three maps and minFrequency; this proves you know how O(1) eviction works.
State the invariant that a key appears in exactly one frequency bucket.
Explain promotion carefully: remove old bucket, maybe advance minFrequency, then add to new bucket front.
Make tie-breaking explicit: tail of the minimum-frequency bucket is the victim.
Mention that new inserts always start at frequency 1 and reset minFrequency to 1.
Call out the average-case HashMap assumption behind O(1).
Discuss concurrency separately from algorithmic complexity; three structures need one atomic mutation boundary.
Quiz
0/6 answered
1.Which data structures are sufficient for the standard O(1) LFU cache?
2.When a get hits an existing key, what must happen?
3.If the minimum-frequency bucket has keys [A, B] ordered most recent to least recent, which key is evicted?
4.Why must **minFrequency** be reset to 1 after inserting a new key?
5.What is the most common reason an LFU implementation accidentally becomes O(n)?
6.How is LFU different from LRU?
Practice Variants
Implement LeetCode 460 integer API
AdvancedConvert the generic cache to int keys and values where get returns -1 on miss. Keep the same three-map plus min-frequency design.
Use LinkedHashSet buckets
IntermediateReplace custom doubly linked lists with a map from frequency to LinkedHashSet of keys and a separate key-to-value map. Compare readability and control over invariants.
Add expiring entries
AdvancedAttach expiry time to each node. On get and put, remove expired keys from all maps and buckets before applying normal LFU behavior.
Build windowed LFU
ExpertAdd counter aging so old popularity decays. Explain how this changes eviction correctness and why production caches prefer approximate LFU variants.
Flashcards
Cheat Sheet
Goal: fixed-capacity LFU cache with O(1) average get and put.
Data structures: key to node HashMap, key to frequency HashMap, frequency to doubly linked list HashMap, and minFreq.
Bucket order: each frequency bucket is an LRU list. Front is most recent; tail side is eviction candidate within that frequency.
Get hit: lookup node, remove from old frequency bucket, increment frequency, add to new bucket front, update minFreq if the old bucket emptied.
Get miss: return null and leave state unchanged.
Put existing: update value, then promote exactly like get hit.
Put new with space: create node, store frequency 1, add to bucket 1 front, set minFreq to 1.
Put new when full: remove tail of minFreq bucket, delete victim from both key maps, then insert the new key at frequency 1.
Invariants: one node per key; one frequency per key; key appears in exactly one bucket; no empty bucket is used for eviction.
Complexity: O(1) average time for get and put; O(capacity) space.
References
- DocsLeetCode 460 — LFU Cache
- DocsJava Platform Documentation — HashMap — Oracle
- DocsJava Platform Documentation — LinkedHashSet — Oracle
- BookEffective Java — equals, hashCode, and synchronization guidance — Joshua Bloch