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. Consider the following Python code implementing the optimal DP solution for the stock problem with k transactions. What is the final output when calling maxProfit(1, [1, 5, 2])?

def maxProfit(k, prices):
    n = len(prices)
    if k >= n // 2:
        profit = 0
        for i in range(1, n):
            profit += max(0, prices[i] - prices[i - 1])
        return profit
    next_dp = [[0, 0] for _ in range(k + 1)]
    curr_dp = [[0, 0] for _ in range(k + 1)]
    for i in range(n - 1, -1, -1):
        for t in range(1, k + 1):
            curr_dp[t][0] = max(-prices[i] + next_dp[t][1], next_dp[t][0])
            curr_dp[t][1] = max(prices[i] + next_dp[t - 1][0], next_dp[t][1])
        next_dp, curr_dp = curr_dp, next_dp
    return next_dp[k][0]

print(maxProfit(1, [1, 5, 2]))

easy

A. 4

B. 5

C. 3

D. 1

Solution

1. Step 1: Trace dp for i=2 (price=2), t=1

   Initialize next_dp and curr_dp with zeros. At i=2, curr_dp[1][0] = max(-2 + next_dp[1][1], next_dp[1][0]) = max(-2 + 0, 0) = 0; curr_dp[1][1] = max(2 + next_dp[0][0], next_dp[1][1]) = max(2 + 0, 0) = 2.

2. Step 2: Trace dp for i=1 (price=5), t=1

   curr_dp[1][0] = max(-5 + next_dp[1][1], next_dp[1][0]) = max(-5 + 2, 0) = 0; curr_dp[1][1] = max(5 + next_dp[0][0], next_dp[1][1]) = max(5 + 0, 2) = 5.

3. Step 3: Trace dp for i=0 (price=1), t=1

   curr_dp[1][0] = max(-1 + next_dp[1][1], next_dp[1][0]) = max(-1 + 5, 0) = 4; curr_dp[1][1] = max(1 + next_dp[0][0], next_dp[1][1]) = max(1 + 0, 5) = 5.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Maximum profit with 1 transaction is buying at 1 and selling at 5 -> profit 4 [OK]

Hint: Trace dp arrays backward to find max profit [OK]

Common Mistakes:

• Confusing holding and not holding states
• Off-by-one errors in indexing transactions
• Misreading the final dp state to return

2. Consider the following Python code implementing the bidirectional BFS with state compression to find the shortest path visiting all nodes. Given the input graph = [[1,2,3],[0],[0],[0]], what is the final returned shortest path length?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Initialize queues and visited states

   For n=4 nodes, all_visited=15 (binary 1111). Each node starts in q1 with mask having only that node visited, and in q2 with mask having all nodes except that node visited.

2. Step 2: Trace BFS expansions

   From q1, starting at each node, BFS explores neighbors updating visited masks. The shortest path visiting all nodes in this star graph is 3 edges (e.g., 1->0->2->3).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Star graph shortest path length visiting all nodes is 3 edges [OK]

Hint: Star graph shortest path visiting all nodes equals 3 edges [OK]

Common Mistakes:

• Confusing number of nodes with number of edges in path
• Off-by-one errors in BFS distance counting
• Misinterpreting bitmask updates

3. The following code attempts to find the minimum window substring but contains a subtle bug:

def min_window_buggy(s: str, t: str) -> str:
    if not s or not t:
        return ""
    t_count = [0] * 128
    window_count = [0] * 128
    for c in t:
        t_count[ord(c)] += 1
    have, need = 0, sum(1 for x in t_count if x > 0)
    res, res_len = [-1, -1], float('inf')
    left = 0
    for right in range(len(s)):
        c = s[right]
        window_count[ord(c)] += 1
        if t_count[ord(c)] > 0 and window_count[ord(c)] == t_count[ord(c)]:
            have += 1
        while have == need:
            if (right - left + 1) < res_len:
                res = [left, right]
                res_len = right - left + 1
            window_count[ord(s[left])] -= 1
            # BUG: Missing decrement of 'have' when window_count falls below t_count
            left += 1
    left, right = res
    return s[left:right+1] if res_len != float('inf') else ""

Which line contains the bug?

medium

A. Line where window_count[ord(s[left])] is decremented

B. Line where have is incremented when window_count matches t_count

C. Line where left pointer is incremented inside the while loop

D. Line where t_count array is initialized from string t

Solution

1. Step 1: Identify decrement of window_count

   When shrinking the window, window_count for s[left] is decremented, but the code does not check if this causes window_count to fall below t_count.

2. Step 2: Missing decrement of 'have'

   Without decrementing 'have' when window_count falls below required count, the while loop condition remains true incorrectly, causing wrong results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug is missing update of 'have' after decrementing window_count [OK]

Hint: Must update 'have' when window_count falls below required count [OK]

Common Mistakes:

• Forgetting to decrement 'have' when shrinking window
• Incorrectly updating pointers without adjusting counts

4. Suppose the problem is modified so that the path can reuse nodes multiple times (cycles allowed). Which of the following statements about adapting the maximum path sum algorithm is correct?

hard

A. The existing recursive approach works without changes because it already considers all paths.

B. The problem reduces to finding the maximum sum cycle in a graph, which can be solved by the same recursion.

C. We can simply remove the max(..., 0) checks to allow negative gains and reuse nodes.

D. We must detect and avoid cycles, possibly using memoization or graph algorithms, since the tree is no longer acyclic.

Solution

1. Step 1: Recognize that allowing node reuse introduces cycles, so the structure is no longer a tree.

   The original recursion assumes acyclic structure and no repeated nodes.

2. Step 2: Understand that to handle cycles, the algorithm must detect and avoid infinite recursion, typically via memoization or graph cycle detection.

   Standard tree recursion breaks down without cycle checks.

3. Step 3: Note that removing max(..., 0) or reusing nodes without cycle detection leads to infinite loops or incorrect sums.

   Maximum sum cycle detection is a different problem requiring graph algorithms.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Cycle detection and memoization are necessary for graphs with cycles [OK]

Hint: Cycles require cycle detection and memoization [OK]

Common Mistakes:

• Assuming tree recursion works unchanged
• Removing zero cutoff to allow reuse
• Confusing max path sum with max cycle sum

5. Suppose the elevation map array can contain negative heights representing below sea level bars. Which modification to the two-pointer approach is necessary to correctly compute trapped water?

hard

A. Modify the water accumulation step to add max(0, left_max - height[left]) and max(0, right_max - height[right]) to avoid negative water addition.

B. Adjust the algorithm to treat negative heights as zero when calculating trapped water but keep original values for max updates.

C. Use prefix and suffix max arrays instead of two-pointer approach because two-pointer fails with negative heights.

D. Ignore negative heights since water cannot be trapped below zero height bars.

Solution

1. Step 1: Understand negative heights impact

   Negative heights can cause (max_height - height) to be larger than expected, possibly negative if not handled carefully.

2. Step 2: Modify water accumulation

   Using max(0, left_max - height[left]) ensures no negative water is added even if height is negative, preserving correctness.

3. Step 3: Why other options fail

   Ignoring negatives loses trapped water info; treating negatives as zero inconsistently updates max heights; prefix/suffix arrays still need careful handling.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Clamping water addition to non-negative values prevents incorrect negative water [OK]

Hint: Clamp water added to max(0, max_height - height) to handle negatives [OK]

Common Mistakes:

• Ignoring negative heights
• Incorrect max height updates
• Assuming two-pointer approach cannot handle negatives