LFU Cache

📋

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: passpublic class LFUCache { public LFUCache(int capacity) {} public int get(int key) { return 0; } public void put(int key, int value) {} }class LFUCache { public: LFUCache(int capacity) {} int get(int key) { return 0; } void put(int key, int value) {} };class LFUCache { constructor(capacity) {} get(key) { return -1; } put(key, value) {} }

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
    }
}

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

Focus on handling edge cases like zero capacity and single element caches to solidify your base implementation.

Review your eviction logic carefully; ensure frequency and recency are both considered correctly.

Optimize your data structures to achieve O(1) average time per operation using frequency buckets and doubly linked lists.

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]

⏱ Performance - must finish in 2000ms

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.

💡 Simulate each operation step-by-step, tracking frequencies and recency.

💡 Remember to evict the least frequently used key, and if tie, the least recently used among them.

💡 Update frequency on both get and put for existing keys; evict only when capacity is full.

Why it failed: Incorrect output likely due to not updating frequencies on get or put, or evicting wrong key when frequencies tie. Fix by maintaining frequency counts and recency order per frequency bucket.

✓ Correctly handles frequency updates, eviction by LFU and LRU tie-break.

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]

⏱ Performance - must finish in 2000ms

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.

💡 Track frequencies and recency carefully after each operation.

💡 Eviction should remove the key with lowest frequency and oldest usage.

💡 Update frequency on get and put for existing keys to maintain correct eviction order.

Why it failed: Failing this test means eviction logic does not handle ties by recency or frequency updates on get/put are incorrect. Fix by using frequency buckets with ordered keys.

✓ Correctly handles eviction with frequency ties and updates frequencies on gets and puts.

t2_01edge

Input{"capacity":0,"operations":["put","get","put","get"],"arguments":[[1,1],[1],[2,2],[2]]}

Expected[null,-1,null,-1]

⏱ Performance - must finish in 2000ms

Capacity zero means cache cannot store any items. All puts do nothing, all gets return -1.

💡 Check if capacity zero is handled explicitly.

💡 No items should be stored or retrieved when capacity is zero.

💡 Return -1 on all gets and ignore puts if capacity is zero.

Why it failed: Cache stores items despite zero capacity, causing wrong get results. Fix by returning immediately in put if capacity == 0.

✓ Correctly handles zero capacity by ignoring puts and returning -1 on gets.

t2_02edge

Input{"capacity":1,"operations":["put","put","get","put","get"],"arguments":[[1,10],[1,20],[1],[2,30],[1]]}

Expected[null,null,20,null,-1]

⏱ Performance - must finish in 2000ms

Single element cache. put(1,10), then put(1,20) updates value and frequency. get(1) returns updated 20. put(2,30) evicts key 1. get(1) returns -1.

💡 Check if put updates existing key's value and frequency.

💡 Eviction should happen only when inserting new key and capacity is full.

💡 Ensure frequency increments on put for existing keys.

Why it failed: Failing means put does not update existing key or frequency, or eviction logic is incorrect. Fix by updating value and frequency on existing keys in put.

✓ Correctly updates existing keys and evicts when capacity exceeded.

t2_03edge

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

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

⏱ Performance - must finish in 2000ms

After inserting keys 1 and 2, inserting key 3 evicts key 1 (freq=1, least recently used). get(1) returns -1, get(2) returns 2.

💡 Eviction must remove least frequently used and least recently used key.

💡 Track recency among keys with same frequency.

💡 Check eviction order carefully when frequencies tie.

Why it failed: Eviction removes wrong key when frequencies tie. Fix by tracking recency order within frequency buckets.

✓ Eviction correctly removes least recently used key among those with lowest frequency.

t3_01corner

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

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

⏱ Performance - must finish in 2000ms

Greedy trap test: naive eviction by recency only. After get(1), freq(1)=2, freq(2)=1. put(3,3) evicts key 2 (lowest freq). get(1) returns -1 if eviction wrong, else 1. get(3) returns 3.

💡 Do not evict based on recency alone; frequency must be considered first.

💡 Use frequency buckets to find LFU keys before considering recency.

💡 Fix eviction to remove key with lowest frequency, then least recently used among them.

Why it failed: Eviction based on recency only causes wrong key removal. Fix by implementing frequency-based eviction with recency tie-break.

✓ Correctly evicts least frequently used key, breaking ties by recency.

t3_02corner

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

Expected[null,null,null,10,2,-1]

⏱ Performance - must finish in 2000ms

0/1 vs unbounded confusion test: put with existing key updates value and frequency. put(1,10) updates key 1's value and freq. get(1) returns 10, get(2) returns 2, get(3) returns -1.

💡 Ensure put updates existing key's value and increments frequency.

💡 Do not treat put as unbounded insert; only one instance per key allowed.

💡 Fix put to update value and frequency if key exists.

Why it failed: Treating put as unbounded insert causes duplicates or wrong frequency. Fix by updating existing key's value and frequency in put.

✓ Correctly updates existing keys on put without duplicates.

t3_03corner

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

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

⏱ Performance - must finish in 2000ms

Off-by-one frequency update test: After get(1) and get(2), freq(1)=2, freq(2)=2, freq(3)=1. put(4,4) evicts key 3 (lowest freq). get(1) returns -1 if off-by-one error, else 1. get(3) returns 3 or -1 accordingly.

💡 Check frequency increment happens exactly once per get or put.

💡 Avoid off-by-one errors in frequency updates.

💡 Fix frequency update logic to increment frequency correctly.

Why it failed: Off-by-one frequency update causes wrong eviction or get results. Fix frequency increment logic to update frequency exactly once per access.

✓ Frequency updates correctly reflect usage counts.

t4_01performance

Input{"capacity":100,"operations":["put","put","put","put","put","put","put","put","put","put","get","get","get","get","get","get","get","get","get","get","put","put","put","put","put","put","put","put","put","put","get","get","get","get","get","get","get","get","get","get","put","put","put","put","put","put","put","put","put","put","get","get","get","get","get","get","get","get","get","get","put","put","put","put","put","put","put","put","put","put","get","get","get","get","get","get","get","get","get","get","put","put","put","put","put","put","put","put","put","put","get","get","get","get","get","get","get","get","get","get","put","put","put","put","put","put","put","put","put","put","get","get","get","get","get","get","get","get","get","get"],"arguments":[[1,1],[2,2],[3,3],[4,4],[5,5],[6,6],[7,7],[8,8],[9,9],[10,10],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11,11],[12,12],[13,13],[14,14],[15,15],[16,16],[17,17],[18,18],[19,19],[20,20],[11],[12],[13],[14],[15],[16],[17],[18],[19],[20],[21,21],[22,22],[23,23],[24,24],[25,25],[26,26],[27,27],[28,28],[29,29],[30,30],[21],[22],[23],[24],[25],[26],[27],[28],[29],[30],[31,31],[32,32],[33,33],[34,34],[35,35],[36,36],[37,37],[38,38],[39,39],[40,40],[31],[32],[33],[34],[35],[36],[37],[38],[39],[40],[41,41],[42,42],[43,43],[44,44],[45,45],[46,46],[47,47],[48,48],[49,49],[50,50],[41],[42],[43],[44],[45],[46],[47],[48],[49],[50],[51,51],[52,52],[53,53],[54,54],[55,55],[56,56],[57,57],[58,58],[59,59],[60,60],[51],[52],[53],[54],[55],[56],[57],[58],[59],[60]]}

Expectednull

⏱ Performance - must finish in 2000ms

Large test with 100 capacity and 200 operations to verify O(1) average time complexity per operation within 2 seconds.

💡 Use hash maps combined with frequency linked lists for O(1) operations.

💡 Avoid sorting or scanning all keys on eviction.

💡 Maintain frequency buckets and recency order within buckets.

Why it failed: Brute force or sorting on eviction causes TLE. Fix by implementing O(1) LFU cache using frequency buckets and doubly linked lists.

✓ Solution runs within time limit confirming O(1) average complexity.

Practice

1. What is the time complexity of the optimal space-optimized DP solution for the Best Time to Buy Sell IV problem with n days and k transactions?

medium

A. O(n * k * 2^k) due to nested recursion and state explosion

B. O(n^2 * k) because for each day it scans all previous days for transactions

C. O(k * 2^n) due to exponential subsets of transactions

D. O(n * k) because the DP iterates over days and transactions with constant holding states

Solution

1. Step 1: Identify loops in the DP code

   The DP iterates over n days in an outer loop and k transactions in an inner loop, with constant operations per iteration.

2. Step 2: Analyze recursion or nested loops

   The space-optimized DP avoids recursion stack overhead and does not scan all previous days for each day, so no quadratic factor in n.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   DP runs in O(n*k) time, matching the nested loops over days and transactions [OK]

Hint: DP loops over days and transactions only [OK]

Common Mistakes:

• Assuming quadratic time due to scanning previous days
• Confusing recursion stack space with time complexity
• Thinking exponential subsets are enumerated

2. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the edit distance problem, where the input strings have lengths m and n respectively?

medium

A. O(m * n)

B. O(m + n)

C. O(m * n * min(m, n))

D. O(3^(m + n))

Solution

1. Step 1: Identify nested loops over m and n

   The algorithm iterates over all pairs of indices (i, j) with i in [0, m) and j in [0, n), performing constant work per pair.

2. Step 2: Confirm no extra multiplicative factors

   Each cell computation is O(1), so total time is O(m * n). The recursion stack or auxiliary space does not affect time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP table size m*n and constant work per cell [OK]

Hint: DP over m*n cells -> O(m*n) time [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming exponential due to recursion without memoization

3. The following code attempts to compute the edit distance using space-optimized bottom-up DP. Which line contains a subtle bug that causes incorrect results on empty strings or boundary cases?

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    next_row = [0] * (n + 1)
    for j in range(n + 1):
        next_row[j] = n - j

    for i in range(m - 1, -1, -1):
        current = [0] * (n + 1)
        current[n] = m - i
        for j in range(n - 1, -1, -1):
            if word1[i] == word2[j]:
                current[j] = next_row[j + 1]
            else:
                current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])
        next_row = current

    return next_row[0]

medium

A. Line initializing next_row with n - j

B. Line setting current[n] = m - i

C. Line comparing word1[i] == word2[j]

D. Line computing current[j] = 1 + min(...)

Solution

1. Step 1: Check base case initialization of next_row

   next_row[j] = n - j assumes word1 is empty, so cost is insertions to get word2[j:]. This is correct.

2. Step 2: Verify if this holds for empty strings

   If word2 is empty (n=0), next_row has length 1 and next_row[0] = 0, which is correct. So initialization is correct.

3. Step 3: Check line setting current[n] = m - i

   This line sets the cost of deleting remaining characters in word1 starting at i. However, it should be current[n] = m - i, which is correct in value but the bug is that this line is executed inside the loop for i, but when word2 is empty (n=0), current[n] is current[0], which is overwritten each iteration. The subtle bug is that this line does not correctly handle the case when word2 is empty and word1 is non-empty, because the initialization should be done differently.

4. Step 4: The other lines are correct

   Comparisons and min computations are correct.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Incorrect handling of current[n] initialization causes wrong results on empty strings [OK]

Hint: Base case initialization must handle empty strings correctly [OK]

Common Mistakes:

• Confusing base case initialization for empty strings
• Mixing up indices i and j

4. The following code attempts to solve the Russian Doll Envelopes problem optimally. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 4: Sorting envelopes with key (x[0], x[1]) ascending both

B. Line 6: Extracting heights from envelopes

C. Line 8: Using bisect_left to find insertion index

D. Line 11: Replacing tails element at found index

Solution

1. Step 1: Examine sorting key

   Sorting by (width asc, height asc) allows envelopes with same width and increasing height, which breaks strict nesting rules.

2. Step 2: Correct sorting key

   Sorting by (width asc, height desc) prevents envelopes with equal width but increasing height from being counted incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing sorting to (x[0], -x[1]) fixes the bug [OK]

Hint: Sort height descending for equal widths to avoid counting duplicates [OK]

Common Mistakes:

• Sorting both width and height ascending
• Using <= instead of < in comparisons
• Not handling equal widths properly

5. Suppose the problem is modified so that digits can be reused any number of times to form expressions (e.g., "1+1+2+3" from "123"). Which modification to the backtracking algorithm correctly handles this variant without infinite loops?

hard

A. Remove the index increment in recursive calls to allow reuse of digits indefinitely

B. Add a visited set to track used indices and prevent reusing digits more than once

C. Allow recursive calls to reuse digits by not incrementing index, but limit expression length to avoid infinite recursion

D. Modify recursion to restart from index 0 after each operator insertion, but track expression length to prevent infinite loops

Solution

1. Step 1: Understand reuse implications

   Allowing reuse means digits can be chosen multiple times, so index must be reset or not incremented to allow reuse.

2. Step 2: Prevent infinite recursion

   Resetting index to 0 after operator insertion allows reuse, but expression length must be tracked and limited to avoid infinite loops.

3. Step 3: Evaluate options

   Modify recursion to restart from index 0 after each operator insertion, but track expression length to prevent infinite loops correctly resets index and tracks length. Remove the index increment in recursive calls to allow reuse of digits indefinitely causes infinite loops by never incrementing index. Add a visited set to track used indices and prevent reusing digits more than once forbids reuse. Allow recursive calls to reuse digits by not incrementing index, but limit expression length to avoid infinite recursion risks infinite recursion without explicit length limit.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Reset index with length limit prevents infinite recursion while allowing reuse [OK]

Hint: Reuse requires index reset plus recursion depth control [OK]

Common Mistakes:

• Not limiting recursion depth causing infinite loops
• Using visited set forbidding reuse