LFU Cache

▶

Steps

setup

Initialize LFU Cache with capacity 2

Create an empty cache with capacity 2, time counter set to 0, and no keys stored yet.

💡 Initialization sets up the data structures and counters needed to track frequencies and recency.

Line:

def __init__(self, capacity: int):
    self.capacity = capacity
    self.time = 0
    self.cache = {}

💡 Cache starts empty and ready to store up to 2 keys with frequency and timestamp tracking.

insert

Put key=1, value=1 into cache

Insert key 1 with value 1. Since cache is empty, add key with frequency 1 and timestamp 1.

💡 First insertion sets frequency to 1 and increments time to track recency.

Line:

self.time += 1
self.cache[key] = (value, 1, self.time)

💡 New keys start with frequency 1 and the current time to mark insertion order.

insert

Put key=2, value=2 into cache

Insert key 2 with value 2. Cache has space, so add key with frequency 1 and timestamp 2.

💡 Adding a second key fills the cache to capacity, both with freq=1 but different timestamps.

Line:

self.time += 1
self.cache[key] = (value, 1, self.time)

💡 Both keys have same frequency but different timestamps to break ties on eviction.

get

Get key=1 from cache

Access key 1, found in cache. Increase its frequency from 1 to 2 and update timestamp to 3.

💡 Getting a key updates its frequency and recency, reflecting increased usage.

Line:

value, freq, _ = self.cache[key]
self.time += 1
self.cache[key] = (value, freq + 1, self.time)
return value

💡 Frequency increment shows key 1 is now more frequently used than key 2.

insert

Put key=3, value=3 into cache (eviction needed)

Cache full. Find LFU keys: key 2 with freq=1 is least frequent. Evict key 2 and insert key 3 with freq=1 and time=4.

💡 Eviction chooses key with lowest frequency and oldest timestamp to maintain LFU policy.

Line:

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)

💡 Eviction respects frequency first, then recency to break ties.

get

Get key=2 from cache (not found)

Attempt to get key 2, but it was evicted. Return -1.

💡 Cache miss returns -1 and does not update cache state.

Line:

if key not in self.cache:
    return -1

💡 Evicted keys are no longer accessible.

get

Get key=3 from cache

Access key 3, found in cache. Increase frequency from 1 to 2 and update timestamp to 5.

💡 Frequency and timestamp update reflect recent access, increasing key 3's priority.

Line:

value, freq, _ = self.cache[key]
self.time += 1
self.cache[key] = (value, freq + 1, self.time)
return value

💡 Key 3 now has same frequency as key 1 but more recent timestamp.

insert

Put key=4, value=4 into cache (eviction needed)

Cache full. Both keys 1 and 3 have freq=2. Evict least recently used key 1 (time=3). Insert key 4 with freq=1 and time=6.

💡 When frequencies tie, eviction chooses the least recently used key.

Line:

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)

💡 Eviction respects recency as a tie-breaker among equal frequency keys.

get

Get key=1 from cache (not found)

Attempt to get key 1, but it was evicted. Return -1.

💡 Evicted keys cannot be retrieved, confirming eviction correctness.

Line:

if key not in self.cache:
    return -1

💡 Eviction permanently removes keys from cache.

get

Get key=3 from cache

Access key 3, increase frequency from 2 to 3 and update timestamp to 7.

💡 Frequency increment shows key 3 is now most frequently used.

Line:

value, freq, _ = self.cache[key]
self.time += 1
self.cache[key] = (value, freq + 1, self.time)
return value

💡 Key 3's frequency surpasses key 4, making it least likely to be evicted next.

get

Get key=4 from cache

Access key 4, increase frequency from 1 to 2 and update timestamp to 8.

💡 Frequency update reflects recent access, increasing key 4's priority.

Line:

value, freq, _ = self.cache[key]
self.time += 1
self.cache[key] = (value, freq + 1, self.time)
return value

💡 Key 4 frequency now 2, less than key 3's 3, so key 4 is more likely to be evicted next.

import time

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity  # STEP 1
        self.time = 0
        self.cache = {}

    def get(self, key: int) -> int:
        if key not in self.cache:  # STEP 6,9
            return -1
        value, freq, _ = self.cache[key]
        self.time += 1  # STEP 4,7,10,11
        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  # STEP 2,3,5,8
        if key in self.cache:  # STEP 4 (not used in example)
            _, freq, _ = self.cache[key]
            self.cache[key] = (value, freq + 1, self.time)
            return
        if len(self.cache) == self.capacity:
            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)

if __name__ == '__main__':
    cache = LFUCache(2)
    cache.put(1, 1)      # STEP 2
    cache.put(2, 2)      # STEP 3
    print(cache.get(1))  # STEP 4
    cache.put(3, 3)      # STEP 5
    print(cache.get(2))  # STEP 6
    print(cache.get(3))  # STEP 7
    cache.put(4, 4)      # STEP 8
    print(cache.get(1))  # STEP 9
    print(cache.get(3))  # STEP 10
    print(cache.get(4))  # STEP 11

📊

LFU Cache - Watch the Algorithm Execute, Step by Step

Watching each operation lets you understand how frequency and recency combine to decide which key to evict, which is hard to grasp from code alone.

setup

Result: []

insert

i

1

0

Result: []

insert

1

0

i

2

1

Result: []

compare

i

1

0

2

1

Result: [1]

delete

1

0

right

3

1

Result: [1,null]

compare

1

0

3

1

Result: [1,null,-1]

compare

1

0

i

3

1

Result: [1,null,-1,3]

delete

left

3

0

right

4

1

Result: [1,null,-1,3,null]

compare

3

0

4

1

Result: [1,null,-1,3,null,-1]

compare

i

3

0

4

1

Result: [1,null,-1,3,null,-1,3]

compare

3

0

i

4

1

Result: [1,null,-1,3,null,-1,3,4]

Key Takeaways

✓ LFU eviction depends on both frequency and recency, with frequency as primary and recency as tie-breaker.

This dual criteria is hard to see from code alone but becomes clear when watching eviction decisions step-by-step.

✓ Each get operation increases frequency and updates timestamp, changing eviction priority dynamically.

Seeing frequency and timestamp updates visually helps understand how usage patterns affect cache state.

✓ Eviction scans all keys to find the LFU and LRU key, demonstrating the brute force approach's cost and logic.

Watching the candidate selection and eviction clarifies why this approach is less efficient but conceptually straightforward.

Practice

1. Given a list of unique words, you need to find all pairs of distinct indices (i, j) such that the concatenation of words[i] + words[j] forms a palindrome. Which approach guarantees an optimal solution in terms of time complexity for large inputs?

easy

A. Brute force nested loops checking all pairs and verifying palindrome by concatenation

B. Building a Trie of reversed words and tracking palindrome suffixes to find pairs efficiently

C. Dynamic programming to find palindromic substrings and then pairing indices accordingly

D. Greedy approach by sorting words and pairing those with matching prefixes and suffixes

Solution

1. Step 1: Understand brute force limitations

   Brute force checks all pairs, resulting in O(n^2 * k) time, which is inefficient for large n.

2. Step 2: Recognize Trie-based optimization

   Building a Trie of reversed words allows prefix matching and palindrome suffix tracking, reducing redundant checks and achieving O(n * k^2) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Trie-based approach is known optimal for palindrome pairs [OK]

Hint: Trie with palindrome suffixes optimizes palindrome pair search [OK]

Common Mistakes:

• Assuming brute force is acceptable for large inputs
• Confusing palindrome substring DP with pair finding
• Believing greedy prefix-suffix matching suffices

2. What is the time complexity of the optimal binary search partition approach to find the median of two sorted arrays of sizes m and n (m ≤ n)?

medium

A. O(log(min(m, n)))

B. O(m + n)

C. O(log(m + n))

D. O(log(m))

Solution

1. Step 1: Identify which array is binary searched

   The algorithm always binary searches the smaller array of size m.

2. Step 2: Analyze binary search complexity

   Binary search on array of size m takes O(log m) time. Since m ≤ n, this is O(log(min(m, n))).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search on smaller array yields O(log(min(m,n))) [OK]

Hint: Binary search on smaller array size defines complexity [OK]

Common Mistakes:

• Assuming O(m + n) due to merging intuition
• Confusing log(m + n) with log(min(m, n))
• Ignoring that binary search is only on smaller array

3. 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

4. Suppose the problem is modified so that characters in t can be reused unlimited times (i.e., the window must contain at least one occurrence of each character in t, but counts do not matter). Which modification to the sliding window algorithm correctly solves this variant?

hard

A. Keep frequency counts but ignore decrementing counts when shrinking window

B. Sort s and t and use two pointers to find minimal substring containing all chars

C. Use the original frequency counting approach but reset counts after each valid window

D. Use a set to track which characters from t are present in the window, and shrink when all are present

Solution

1. Step 1: Understand the variant

   Since counts do not matter and characters can be reused unlimited times, we only need to check presence of each unique character from t in the window.

2. Step 2: Modify tracking data structure

   Using a set to track which characters from t are currently in the window is sufficient. When the set contains all unique chars, the window is valid.

3. Step 3: Shrink window accordingly

   Shrink the window while maintaining presence of all required characters in the set.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Tracking presence with a set fits the reuse variant [OK]

Hint: Presence tracking with set suffices when counts don't matter [OK]

Common Mistakes:

• Continuing to track exact counts unnecessarily
• Resetting counts incorrectly
• Sorting strings which breaks substring property

5. Suppose the problem is modified so that the same letter cell on the board can be used multiple times within the same word search path (i.e., reuse of cells is allowed). Which modification to the optimal backtracking with Trie approach correctly handles this variant without causing infinite loops?

hard

A. Use a separate visited set to track cells per path and allow revisiting after backtracking

B. Remove the in-place marking of visited cells and rely solely on Trie pruning

C. Keep the in-place marking but reset visited cells only after exploring all neighbors

D. Modify the Trie to store counts of allowed cell reuse and decrement on each visit

Solution

1. Step 1: Understand reuse impact on visited marking

   Allowing reuse means cells can be revisited, so marking cells as visited must be carefully managed to avoid infinite loops.

2. Step 2: Identify correct marking strategy

   Using a separate visited set per path allows revisiting cells after backtracking, preventing infinite loops while supporting reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Separate visited set per path safely handles cell reuse [OK]

Hint: Track visited cells per path to allow safe reuse [OK]

Common Mistakes:

• Removing marking causes infinite loops
• Using global visited set without reset
• Modifying Trie for cell reuse incorrectly