LFU Cache

🎯

LFU Cache

hardMIXEDAmazonGoogleFacebook

Imagine designing a caching system for a high-traffic website where you want to keep the most frequently accessed items readily available to minimize latency and server load.

💡 This problem requires designing a data structure that supports fast access and eviction based on usage frequency. Beginners often struggle because it requires combining multiple data structures and maintaining complex invariants efficiently. Think of it as managing a library where books are borrowed frequently; you want to keep the most popular books handy and remove the least popular ones when space runs out.

📋

Problem Statement

Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get(key) and put(key, value). get(key) - Get the value of the key if it exists in the cache, otherwise return -1. put(key, value) - Update or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. If there is a tie in frequency, the least recently used key should be evicted.

0 ≤ capacity ≤ 10^50 ≤ key, value ≤ 10^9At most 2 * 10^5 calls will be made to get and put.

💡

Example

Input"capacity = 2\nput(1, 1)\nput(2, 2)\nget(1)\nput(3, 3)\nget(2)\nget(3)\nput(4, 4)\nget(1)\nget(3)\nget(4)"

Output[null, null, 1, null, -1, 3, null, -1, 3, 4]

Initially cache is empty. After put(1,1) and put(2,2), cache has keys 1 and 2 with frequency 1. get(1) returns 1 and increases frequency of key 1 to 2. put(3,3) evicts key 2 because it has frequency 1 which is least. get(2) returns -1 because key 2 was evicted. get(3) returns 3 and increases frequency of key 3 to 2. put(4,4) evicts key 1 because keys 1 and 3 have frequency 2 but key 1 is least recently used. get(1) returns -1. get(3) returns 3. get(4) returns 4.

• capacity = 0 → all puts should not store anything, all gets return -1
• put with existing key → should update value and frequency
• multiple keys with same frequency → evict least recently used among them
• very large number of operations → must maintain O(1) average time per operation

⚠️

Common Mistakes

Not updating minFreq after eviction or frequency increment

Eviction or frequency updates become incorrect, causing wrong keys to be removed

✅ Always update minFreq when frequency lists become empty or after incrementing frequency

Using a single linked list instead of doubly linked list

Removal of arbitrary nodes becomes O(n), breaking O(1) time complexity

✅ Use doubly linked lists to remove nodes in O(1) time

Not handling capacity = 0 case

Code may crash or behave unexpectedly when capacity is zero

✅ Add explicit check to return immediately if capacity is zero

Updating frequency but forgetting to move node between frequency lists

Frequency counts become inconsistent with node positions, causing incorrect eviction

✅ Always remove node from old frequency list and add to new frequency list on frequency update

Evicting the most recently used key instead of least recently used among ties

Eviction policy is violated, causing wrong keys to be removed

✅ Evict the tail (oldest) node in the lowest frequency list to respect LRU among ties

🧠

Brute Force (Using HashMap and Sorting on Eviction)

💡 This approach exists to help understand the problem by implementing the eviction logic in the simplest way possible, even if inefficient. It clarifies the eviction criteria and frequency tracking. Think of it as a first draft or prototype before optimizing.

Intuition

Store all keys with their frequencies and timestamps. On eviction, scan all keys to find the least frequently used and least recently used key to remove.

Algorithm

1. Use a hashmap to store key to (value, frequency, timestamp).
2. On get(key), update frequency and timestamp, return value or -1 if not found.
3. On put(key, value), if key exists, update value, frequency, timestamp.
4. If capacity exceeded, scan all keys to find the LFU and LRU key to evict.
5. Insert new key with frequency 1 and current timestamp.

💡 The main difficulty is the eviction step which requires scanning all keys, making it inefficient but conceptually simple.

</>

Code

import time

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.time = 0
        self.cache = {}  # key: (value, freq, time)

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        value, freq, _ = self.cache[key]
        self.time += 1
        self.cache[key] = (value, freq + 1, self.time)
        return value

    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:
            return
        self.time += 1
        if key in self.cache:
            _, freq, _ = self.cache[key]
            self.cache[key] = (value, freq + 1, self.time)
            return
        if len(self.cache) == self.capacity:
            # Evict LFU and LRU
            min_freq = min(freq for _, freq, _ in self.cache.values())
            candidates = [k for k, (_, freq, _) in self.cache.items() if freq == min_freq]
            lru_key = min(candidates, key=lambda k: self.cache[k][2])
            del self.cache[lru_key]
        self.cache[key] = (value, 1, self.time)

# Driver code
if __name__ == '__main__':
    cache = LFUCache(2)
    cache.put(1, 1)
    cache.put(2, 2)
    print(cache.get(1))  # returns 1
    cache.put(3, 3)      # evicts key 2
    print(cache.get(2))  # returns -1
    print(cache.get(3))  # returns 3
    cache.put(4, 4)      # evicts key 1
    print(cache.get(1))  # returns -1
    print(cache.get(3))  # returns 3
    print(cache.get(4))  # returns 4

Line Notes

self.cache = {} # key: (value, freq, time)Stores all keys with their value, frequency, and last access time to track usage.

if key not in self.cache:Check if key exists before returning value to handle cache misses.

self.time += 1Increment global time to track recency and maintain order for eviction.

min_freq = min(freq for _, freq, _ in self.cache.values())Find minimum frequency among all keys to identify eviction candidates.

candidates = [k for k, (_, freq, _) in self.cache.items() if freq == min_freq]Collect all keys with minimum frequency to break ties.

lru_key = min(candidates, key=lambda k: self.cache[k][2])Among candidates, find least recently used key by timestamp for eviction.

del self.cache[lru_key]Evict the identified key from cache to make space for new entries.

import java.util.*;

class LFUCache {
    private int capacity, time;
    private Map<Integer, int[]> cache; // key -> {value, freq, time}

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.time = 0;
        this.cache = new HashMap<>();
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        int[] val = cache.get(key);
        val[1]++;
        val[2] = ++time;
        return val[0];
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        time++;
        if (cache.containsKey(key)) {
            int[] val = cache.get(key);
            val[0] = value;
            val[1]++;
            val[2] = time;
            return;
        }
        if (cache.size() == capacity) {
            int minFreq = Integer.MAX_VALUE;
            for (int[] v : cache.values()) {
                minFreq = Math.min(minFreq, v[1]);
            }
            int lruKey = -1;
            int oldestTime = Integer.MAX_VALUE;
            for (Map.Entry<Integer, int[]> entry : cache.entrySet()) {
                int[] v = entry.getValue();
                if (v[1] == minFreq && v[2] < oldestTime) {
                    oldestTime = v[2];
                    lruKey = entry.getKey();
                }
            }
            cache.remove(lruKey);
        }
        cache.put(key, new int[]{value, 1, time});
    }

    // Main method for testing
    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 1
        cache.put(3, 3); // evicts key 2
        System.out.println(cache.get(2)); // -1
        System.out.println(cache.get(3)); // 3
        cache.put(4, 4); // evicts key 1
        System.out.println(cache.get(1)); // -1
        System.out.println(cache.get(3)); // 3
        System.out.println(cache.get(4)); // 4
    }
}

Line Notes

private Map<Integer, int[]> cache;Stores key mapped to array of value, frequency, and timestamp for quick access and updates.

if (!cache.containsKey(key)) return -1;Return -1 if key not found to indicate cache miss.

val[1]++;Increment frequency on access to track usage count.

val[2] = ++time;Update timestamp to current time to maintain recency order.

int minFreq = Integer.MAX_VALUE;Initialize min frequency to find eviction candidates among all keys.

if (v[1] == minFreq && v[2] < oldestTime)Find least recently used key among those with min frequency for eviction.

cache.remove(lruKey);Remove the identified key from cache to free space.

#include <iostream>
#include <unordered_map>
#include <climits>
using namespace std;

class LFUCache {
    int capacity, time;
    unordered_map<int, tuple<int, int, int>> cache; // key -> (value, freq, time)
public:
    LFUCache(int capacity) : capacity(capacity), time(0) {}

    int get(int key) {
        if (cache.find(key) == cache.end()) return -1;
        auto &[value, freq, t] = cache[key];
        freq++;
        t = ++time;
        return value;
    }

    void put(int key, int value) {
        if (capacity == 0) return;
        time++;
        if (cache.find(key) != cache.end()) {
            auto &[val, freq, t] = cache[key];
            val = value;
            freq++;
            t = time;
            return;
        }
        if ((int)cache.size() == capacity) {
            int minFreq = INT_MAX;
            for (auto &[k, v] : cache) {
                int freq = get<1>(v);
                if (freq < minFreq) minFreq = freq;
            }
            int lruKey = -1;
            int oldestTime = INT_MAX;
            for (auto &[k, v] : cache) {
                int freq = get<1>(v);
                int t = get<2>(v);
                if (freq == minFreq && t < oldestTime) {
                    oldestTime = t;
                    lruKey = k;
                }
            }
            cache.erase(lruKey);
        }
        cache[key] = make_tuple(value, 1, time);
    }
};

int main() {
    LFUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << cache.get(1) << "\n"; // 1
    cache.put(3, 3); // evicts key 2
    cout << cache.get(2) << "\n"; // -1
    cout << cache.get(3) << "\n"; // 3
    cache.put(4, 4); // evicts key 1
    cout << cache.get(1) << "\n"; // -1
    cout << cache.get(3) << "\n"; // 3
    cout << cache.get(4) << "\n"; // 4
    return 0;
}

Line Notes

unordered_map<int, tuple<int, int, int>> cache;Maps key to tuple of value, frequency, and timestamp for efficient lookups.

if (cache.find(key) == cache.end()) return -1;Return -1 if key not found to indicate cache miss.

freq++;Increment frequency on access to track usage count.

t = ++time;Update timestamp to current time to maintain recency order.

int minFreq = INT_MAX;Find minimum frequency for eviction candidates among all keys.

if (freq == minFreq && t < oldestTime)Find least recently used key among minimum frequency keys for eviction.

cache.erase(lruKey);Remove the identified key from cache to free space.

class LFUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.time = 0;
        this.cache = new Map(); // key -> {value, freq, time}
    }

    get(key) {
        if (!this.cache.has(key)) return -1;
        let entry = this.cache.get(key);
        entry.freq++;
        this.time++;
        entry.time = this.time;
        return entry.value;
    }

    put(key, value) {
        if (this.capacity === 0) return;
        this.time++;
        if (this.cache.has(key)) {
            let entry = this.cache.get(key);
            entry.value = value;
            entry.freq++;
            entry.time = this.time;
            return;
        }
        if (this.cache.size === this.capacity) {
            let minFreq = Infinity;
            for (let entry of this.cache.values()) {
                if (entry.freq < minFreq) minFreq = entry.freq;
            }
            let lruKey = null;
            let oldestTime = Infinity;
            for (let [k, entry] of this.cache.entries()) {
                if (entry.freq === minFreq && entry.time < oldestTime) {
                    oldestTime = entry.time;
                    lruKey = k;
                }
            }
            this.cache.delete(lruKey);
        }
        this.cache.set(key, {value: value, freq: 1, time: this.time});
    }
}

// Test
const cache = new LFUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 1
cache.put(3, 3); // evicts key 2
console.log(cache.get(2)); // -1
console.log(cache.get(3)); // 3
cache.put(4, 4); // evicts key 1
console.log(cache.get(1)); // -1
console.log(cache.get(3)); // 3
console.log(cache.get(4)); // 4

Line Notes

this.cache = new Map();Stores key mapped to object with value, frequency, and timestamp for quick access and updates.

if (!this.cache.has(key)) return -1;Return -1 if key not found to indicate cache miss.

entry.freq++;Increment frequency on access to track usage count.

this.time++;Increment global time to track recency and maintain order for eviction.

let minFreq = Infinity;Find minimum frequency among all keys for eviction candidates.

if (entry.freq === minFreq && entry.time < oldestTime)Find least recently used key among minimum frequency keys for eviction.

this.cache.delete(lruKey);Remove the identified key from cache to free space.

⏱

Complexity

TimeO(n) per put in worst case due to scanning all keys for eviction

SpaceO(capacity) for storing cache entries

Each put operation may require scanning all keys to find the LFU and LRU key, leading to linear time complexity per put. Get operations are O(1) as they directly access the hashmap.

💡 For n=1000 puts, this approach could do up to 1,000,000 operations, which is too slow for large inputs. This highlights why optimization is necessary.

Interview Verdict: TLE / Use only to introduce problem and eviction logic

This approach is too slow for large inputs but helps understand the eviction criteria and frequency tracking before optimizing.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always aim to implement the optimized approach with frequency lists and doubly linked lists for O(1) operations.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n) per put due to scanning all keys	O(capacity)	No	N/A	Mention only - never code
2. Optimized with Frequency Lists and Doubly Linked Lists	O(1) average per get and put	O(capacity)	No	N/A	Code this approach
3. Python OrderedDict Approach	O(1) average per get and put	O(capacity)	No	N/A	Mention if using Python; good for quick implementation

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding the optimal approach, and prepare to explain tradeoffs and edge cases clearly in interviews.

How to Present

Clarify problem requirements and eviction policy.Describe brute force approach to show understanding of eviction criteria.Explain inefficiency and motivate optimized approach using frequency lists.Implement optimized approach with clear explanation of data structures.Test with examples and discuss edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test & Discuss: 7min. Total ~30min

What the Interviewer Tests

Interviewer tests your ability to design complex data structures, maintain multiple invariants, and achieve O(1) operations with careful bookkeeping.

Common Follow-ups

• How to handle ties in frequency? → Evict least recently used among them.
• What if capacity is zero? → No items stored, all gets return -1.
• Can you implement LFU with O(log n) complexity? → Use balanced trees or heaps but less optimal.
• How to extend to thread-safe or distributed cache? → Use locks or distributed coordination.

💡 These follow-ups test your understanding of edge cases, alternative implementations, and system design considerations.

🔍

Pattern Recognition

When to Use

1) Need to design a cache or data structure with eviction policy; 2) Eviction depends on frequency of access; 3) Tie-break by recency; 4) Require O(1) operations

Signature Phrases

least frequently usedevict the key with lowest frequencyif tie, evict least recently used

NOT This Pattern When

Problems that only require recency-based eviction (LRU) or simple caching without frequency tracking

Similar Problems

LRU Cache - simpler eviction based on recency onlyAll O(1) Data Structure - similar frequency and count trackingDesign Twitter - complex data structure design with multiple constraints

Practice

1. You need to design a stack data structure that supports the usual push and pop operations, but also an increment operation that adds a given value to the bottom k elements of the stack efficiently. Which approach guarantees the most optimal time complexity for a sequence of n operations?

easy

A. Use a balanced binary search tree to store elements and increments, allowing O(log n) updates and queries.

B. Directly increment the bottom k elements on each increment call, resulting in O(n*k) time for n operations.

C. Use a lazy increment array to record increments and propagate them during pop operations, achieving O(n) total time.

D. Maintain a prefix sum array of increments and update it on each increment call, applying increments during pop.

Solution

1. Step 1: Understand the problem constraints

   The increment operation must be efficient even when called multiple times, so directly incrementing bottom k elements each time (O(n*k)) is too slow.

2. Step 2: Recognize the lazy increment pattern

   Using an auxiliary array to store increments lazily and applying them during pop operations reduces total time to O(n), as increments are propagated only once per element.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Lazy increments avoid repeated updates, achieving O(n) total time [OK]

Hint: Lazy increments reduce repeated updates to O(n) total time [OK]

Common Mistakes:

• Directly incrementing elements each time causes TLE
• Using complex data structures unnecessarily

2. You need to design a system that tracks passengers checking in and out of stations, and efficiently calculates average travel times between stations. Which approach best balances time and space efficiency for frequent queries?

easy

A. Use hash maps to store running totals of travel times and counts per route.

B. Store all trips explicitly and scan them to compute averages on demand.

C. Use dynamic programming to precompute all possible route averages.

D. Use a priority queue to keep track of the shortest travel times per route.

Solution

1. Step 1: Understand the problem requirements

   The system must support frequent check-ins, check-outs, and quick average time queries between stations.

2. Step 2: Evaluate approaches

   Storing all trips (B) leads to slow queries. Dynamic programming (C) is not applicable as routes are dynamic and not fixed. Priority queues (D) do not help compute averages efficiently. Hash maps with running totals (A) allow O(1) updates and queries.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash maps maintain running sums and counts for O(1) average time queries [OK]

Hint: Running totals enable O(1) average queries [OK]

Common Mistakes:

• Thinking storing all trips is efficient for queries

3. You need to design a data structure that supports adding numbers from a stream and retrieving the median efficiently at any time. Which approach best balances insertion and median retrieval time for large data streams?

easy

A. Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half, balancing their sizes after each insertion.

B. Sort the entire list of numbers every time you query the median.

C. Use a balanced binary search tree to keep all numbers sorted and find the median by in-order traversal.

D. Store numbers in an unsorted array and scan it fully to find the median on each query.

Solution

1. Step 1: Understand the problem constraints

   We need efficient insertion and median retrieval for a data stream, so sorting on every query (Sort the entire list of numbers every time you query the median.) or scanning unsorted arrays (Store numbers in an unsorted array and scan it fully to find the median on each query.) is too slow.

2. Step 2: Evaluate data structures

   Using two heaps (max-heap for lower half, min-heap for upper half) allows O(log n) insertion and O(1) median retrieval by balancing sizes, which is optimal for streaming data.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two heaps balance halves efficiently for median [OK]

Hint: Two heaps balance halves for O(log n) insert and O(1) median [OK]

Common Mistakes:

• Sorting on every query is too slow for streams
• Using one heap only cannot track median efficiently

4. You need to design a data structure that supports inserting elements (including duplicates), removing one occurrence of an element, and retrieving a random element--all in average O(1) time. Which approach best guarantees these time complexities?

easy

A. Use a simple list and perform linear search for removals.

B. Use a balanced binary search tree to maintain elements and their counts.

C. Use a hash map to store element to indices mapping, combined with a list to store elements, updating indices on insert and remove.

D. Use a queue to track insertion order and a hash set for membership checks.

Solution

1. Step 1: Understand the operations required

   Insert, remove (one occurrence), and getRandom must all be average O(1), even with duplicates.

2. Step 2: Evaluate approaches

   A simple list with linear search (A) leads to O(n) removals. Balanced BST (C) has O(log n) operations. Queue and hash set (D) do not support random access efficiently. Hash map + list with index tracking (B) supports O(1) insert, remove, and getRandom by maintaining indices of duplicates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map + list with index tracking enables O(1) average operations [OK]

Hint: Hash map + list with index tracking enables O(1) ops [OK]

Common Mistakes:

• Assuming balanced BST can do O(1) getRandom
• Using linear search for removal
• Ignoring duplicates in data structure

5. Suppose the linked list with random pointers can contain cycles formed by random pointers (i.e., random pointers may create cycles independent of next pointers). Which approach correctly copies such a list without infinite loops or duplicate nodes?

hard

A. Use the optimal weaving approach as is, since it handles all cases in O(1) space.

B. Use a recursive approach with memoization to track already copied nodes and avoid infinite recursion.

C. Use the brute force approach but skip assigning random pointers to avoid cycles.

D. Modify the optimal approach to break cycles by removing random pointers before copying.

Solution

1. Step 1: Understand cycle implications

   Random pointer cycles cause infinite loops if naive traversal is used without tracking visited nodes.

2. Step 2: Identify safe approach

   Recursive copying with memoization tracks visited nodes, preventing infinite recursion and duplicate copies.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Memoization ensures each node is copied once even with cycles [OK]

Hint: Memoization prevents infinite recursion in cyclic graphs [OK]

Common Mistakes:

• Assuming weaving approach handles cycles safely
• Ignoring cycles and causing infinite loops
• Removing random pointers loses information