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 an LRU Cache with capacity 2. After executing the sequence of operations below, what is the return value of cache.get(1)?

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)
cache.put(4, 4)
cache.get(1)
cache.get(3)
cache.get(4)

easy

A. 1

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace cache state after each operation

   After put(1,1) and put(2,2), cache has keys [2 (MRU), 1 (LRU)]. get(1) moves key 1 to MRU, order: [1,2]. put(3,3) evicts LRU key 2, cache: [3,1]. get(2) returns -1 (evicted). put(4,4) evicts LRU key 1, cache: [4,3].

2. Step 2: Evaluate get(1) after put(4,4)

   Key 1 was evicted, so get(1) returns -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Key 1 evicted after put(4,4), so get(1) -> -1 [OK]

Hint: Remember to update usage order on get and evict LRU on put [OK]

Common Mistakes:

• Forgetting to move accessed node to front
• Evicting wrong node
• Returning wrong value after eviction

2. Given the following addRange method snippet from the optimal RangeModule implementation, what is the value of self.starts after calling addRange(2, 6) on an initially empty RangeModule?

def addRange(self, left: int, right: int) -> None:
    i = bisect_left(self.starts, left)
    j = bisect_right(self.starts, right)

    if i != 0 and self.intervals[self.starts[i-1]] >= left:
        i -= 1
        left = min(left, self.starts[i])
    if j != 0:
        right = max(right, self.intervals[self.starts[j-1]])

    for k in self.starts[i:j]:
        del self.intervals[k]
    self.starts[i:j] = [left]
    self.intervals[left] = right

easy

A. [2, 6, 7]

B. [2, 6]

C. [2]

D. [6]

Solution

1. Step 1: Trace bisect indices on empty starts list

   Initially, self.starts = []. Calling bisect_left([], 2) returns 0, and bisect_right([], 6) returns 0.

2. Step 2: Update intervals and starts

   Since i == 0, the first if condition is skipped. Also, j == 0, so second if is skipped. No intervals to delete. Insert left=2 at self.starts[0:0], so self.starts = [2]. Interval stored as {2:6}.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Starts list after first addRange is [2] [OK]

Hint: Bisect on empty list returns 0, so starts list gets single element [OK]

Common Mistakes:

• Assuming right endpoint is also inserted in starts list

3. You are given a list of buildings represented as triplets (left, right, height). The goal is to output the skyline formed by these buildings as a list of key points where the height changes. Which algorithmic approach guarantees an optimal solution with time complexity O(n log n)?

easy

A. Divide and conquer approach that recursively merges skylines of building subsets

B. Dynamic programming approach that stores maximum heights for subproblems

C. Greedy approach that iteratively picks the tallest building at each x-coordinate

D. Brute force simulation by iterating over all x-coordinates and tracking max height

Solution

1. Step 1: Understand problem requirements

   The problem requires merging multiple building outlines into a single skyline efficiently.

2. Step 2: Evaluate algorithmic approaches

   Greedy and brute force approaches either fail to guarantee optimal time or are inefficient. Dynamic programming is not a natural fit here. Divide and conquer merges smaller skylines efficiently in O(n log n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Divide and conquer merges sorted skylines efficiently [OK]

Hint: Divide and conquer merges sorted skylines in O(n log n) [OK]

Common Mistakes:

• Thinking greedy or brute force is optimal
• Confusing DP with skyline merging

4. What is the space complexity of the optimal approach that copies a linked list with random pointers by interleaving copied nodes within the original list?

medium

A. O(1) because no extra data structures proportional to n are used

B. O(n) due to storing all copied nodes in a hash map

C. O(n) due to recursion stack in the copying process

D. O(n) because of auxiliary arrays used to track random pointers

Solution

1. Step 1: Identify auxiliary data structures

   The optimal approach does not use hash maps or arrays; it weaves copied nodes into the original list.

2. Step 2: Analyze space usage

   Only a few pointers are used; no extra space proportional to n is allocated, so space complexity is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   No hash maps or recursion stacks used [OK]

Hint: Interleaving nodes avoids extra space [OK]

Common Mistakes:

• Assuming hash map is always needed, so O(n) space
• Confusing recursion stack space with iterative approach
• Thinking auxiliary arrays are used for random pointers

5. Consider the following buggy addRange method for the RangeModule. Which line contains the subtle bug that causes incorrect interval merging?

def addRange(self, left: int, right: int) -> None:
    i = bisect_left(self.starts, left)
    j = bisect_right(self.starts, right)

    if i != 0 and self.intervals[self.starts[i-1]] > left:
        i -= 1
        left = min(left, self.starts[i])
    if j != 0:
        right = max(right, self.intervals[self.starts[j-1]])

    for k in self.starts[i:j]:
        del self.intervals[k]
    self.starts[i:j] = [left]
    self.intervals[left] = right

medium

A. Line with condition: if i != 0 and self.intervals[self.starts[i-1]] > left:

B. Line with bisect_left call: i = bisect_left(self.starts, left)

C. Line deleting intervals: for k in self.starts[i:j]: del self.intervals[k]

D. Line updating self.starts: self.starts[i:j] = [left]

Solution

1. Step 1: Analyze the condition for merging overlapping intervals

   The condition uses > instead of >=, so intervals that exactly touch at the boundary are not merged.

2. Step 2: Consequence of the bug

   This causes fragmented intervals and incorrect query results because adjacent intervals are not merged properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using > instead of >= misses boundary merges [OK]

Hint: Check interval overlap condition carefully for off-by-one errors [OK]

Common Mistakes:

• Using strict inequality instead of inclusive for merging intervals