Interview Prepchallenge-problemshardAmazonGoogleFacebook

LFU Cache

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

📋

Problem

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.

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.

Edge cases: capacity = 0 → all puts should not store anything, all gets return -1put with existing key → should update value and frequencymultiple keys with same frequency → evict least recently used among them

</>

IDE

class LFUCache:
    def __init__(self, capacity: int):
        pass
    def get(self, key: int) -> int:
        pass
    def put(self, key: int, value: int) -> None:
        pass

class LFUCache:
    def __init__(self, capacity: int):
        # Write your solution here
        pass
    def get(self, key: int) -> int:
        pass
    def put(self, key: int, value: int) -> None:
        pass

public class LFUCache {
    public LFUCache(int capacity) {
        // Write your solution here
    }
    public int get(int key) {
        return -1;
    }
    public void put(int key, int value) {
        // Write your solution here
    }
}

class LFUCache {
public:
    LFUCache(int capacity) {
        // Write your solution here
    }
    int get(int key) {
        return -1;
    }
    void put(int key, int value) {
        // Write your solution here
    }
};

class LFUCache {
    constructor(capacity) {
        // Write your solution here
    }
    get(key) {
        return -1;
    }
    put(key, value) {
        // Write your solution here
    }
}

0/9

Common Bugs to Avoid

Wrong: Evicts wrong key when multiple keys have same frequencyEviction logic ignores recency tie-break and evicts any LFU key arbitrarily✅ Maintain recency order within each frequency bucket using a linked list and evict the least recently used key among LFU keys

Wrong: get returns outdated value after put updates existing keyput does not update value or frequency for existing keys✅ In put, if key exists, update its value and increment frequency and recency accordingly

Wrong: Cache stores items despite zero capacity, get returns values instead of -1No explicit check for zero capacity in put and get✅ Return immediately in put if capacity == 0 and always return -1 in get if capacity == 0

Wrong: Solution times out on large inputEviction implemented by scanning all keys or sorting on each put✅ Use frequency buckets and doubly linked lists to achieve O(1) average time per operation

Wrong: Frequency updates off by one causing wrong eviction or get resultsFrequency increment logic is incorrect or missing on get or put✅ Increment frequency exactly once per get or put for existing keys

✓

Test Cases

t1_01basic

Input

{"capacity":2,"operations":["put","put","get","put","get","get","put","get","get","get"],"arguments":[[1,1],[2,2],[1],[3,3],[2],[3],[4,4],[1],[3],[4]]}

Expected[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.

t1_02basic

Input

{"capacity":3,"operations":["put","put","put","get","put","get","get","get"],"arguments":[[2,2],[1,1],[3,3],[2],[4,4],[1],[3],[4]]}

Expected[null,null,null,2,null,-1,3,4]

Cache capacity 3. After put(2,2), put(1,1), put(3,3), all keys have freq=1. get(2) returns 2 and freq(2)=2. put(4,4) evicts key 1 (freq=1, least recently used among freq=1). get(1) returns -1 (evicted). get(3) returns 3 freq=2. get(4) returns 4 freq=2.

Practice

(1/5)

1. You need to design a data structure that supports incrementing and decrementing string keys, and retrieving a key with the maximum or minimum count, all in constant time. Which approach best guarantees O(1) time complexity for all these operations?

easy

A. Using a balanced binary search tree keyed by counts to maintain order of keys

B. Using a hash map to store counts and scanning all keys to find max/min when requested

C. Maintaining a doubly linked list of buckets, each bucket holding keys with the same count, plus hash maps for quick access

D. Using a priority queue to track max and min keys with lazy updates

3. Examine the following buggy code snippet from the AllOne data structure. Which line contains the subtle bug that causes keys to remain in multiple buckets after incrementing, leading to incorrect max/min results?

def inc(self, key: str) -> None:
    if key not in self.key_to_bucket:
        if 1 not in self.count_to_bucket:
            new_bucket = Bucket(1)
            self._insert_bucket_after(new_bucket, self.head)
        self.count_to_bucket[1].keys.add(key)
        self.key_to_bucket[key] = self.count_to_bucket[1]
    else:
        curr_bucket = self.key_to_bucket[key]
        next_count = curr_bucket.count + 1
        if next_count not in self.count_to_bucket:
            new_bucket = Bucket(next_count)
            self._insert_bucket_after(new_bucket, curr_bucket)
        self.count_to_bucket[next_count].keys.add(key)
        self.key_to_bucket[key] = self.count_to_bucket[next_count]
        # BUG: Missing removal of key from old bucket
        # curr_bucket.keys.remove(key)
        if len(curr_bucket.keys) == 0:
            self._remove_bucket(curr_bucket)

medium

A. Line removing key from old bucket's keys set (commented out)

B. Line updating key_to_bucket mapping

C. Line removing empty bucket if keys set is empty

D. Line adding key to new bucket's keys set

LFU Cache

Start learning this pattern below

Practice

Solution

Step 1: Understand operation requirements

Step 2: Evaluate approaches

Final Answer:

Quick Check:

Solution

Step 1: Understand the eviction policy

Step 2: Identify data structure supporting O(1) operations

Final Answer:

Quick Check:

Solution

Step 1: Identify key movement between buckets

Step 2: Locate missing removal

Final Answer:

Quick Check:

Solution

Step 1: Analyze push and pop operations

Step 2: Analyze increment operation

Final Answer:

Quick Check:

Solution

Step 1: Understand tweet reuse impact

Step 2: Adjust data structures

Final Answer:

Quick Check: