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. Consider the following Python code implementing the optimal CustomStack with lazy increments. After executing the sequence of operations below, what is the output of the last pop() call?

cs = CustomStack(3)
cs.push(1)
cs.push(2)
cs.increment(2, 5)
print(cs.pop())

easy

A. 2

B. 7

C. 6

D. 1

Solution

1. Step 1: Trace the increment operation

   After pushing 1 and 2, stack = [1, 2], inc = [0, 0, 0]. increment(2, 5) sets inc[1] += 5 -> inc = [0, 5, 0].

2. Step 2: Trace the pop operation

   pop() removes top element at index 1 (value 2). Since i=1 > 0, inc[0] += inc[1] -> inc[0] = 0 + 5 = 5. Result = stack.pop() + inc[1] = 2 + 5 = 7. inc[1] reset to 0.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Increment applied lazily, pop returns 7 [OK]

Hint: Increment applies to inc array index k-1, added on pop [OK]

Common Mistakes:

• Forgetting to propagate increments down on pop
• Adding increments directly to popped element only

2. Given the following code snippet for flattening a multilevel doubly linked list, what is the value of curr.val after the first iteration of the outer while loop when the input list is: 1 - 2 - 3, where node 2 has a child list 4 - 5?

easy

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Initialize curr to head (node with val=1)

   First iteration: curr.val = 1, no child, so move to next node.

2. Step 2: After first iteration, curr moves to node with val=2

   Thus, after the first iteration, curr.val is 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   curr.val is 1 after first iteration of the loop [OK]

Hint: curr starts at head with val=1 and moves after processing [OK]

Common Mistakes:

• Assuming curr.val changes before moving
• Confusing iteration count with node value

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

4. Suppose the AllOne data structure is extended to allow keys to be reused after removal (i.e., keys can be reinserted after their count reaches zero). Which modification is necessary to maintain O(1) operations and correctness?

hard

A. Do nothing special; existing code handles reuse correctly

B. Maintain a separate reuse queue to track keys that can be reinserted

C. Reset key's count to zero and keep it in the data structure to track reuse

D. Ensure keys are fully removed from all buckets and mappings upon count zero, then treat reuse as new insertion

Solution

1. Step 1: Understand reuse implications

   Keys removed at count zero must be fully deleted to avoid stale references.

2. Step 2: Ensure reuse is treated as new insertion

   On reuse, key is inserted fresh with count 1, requiring clean removal previously.

3. Step 3: Confirm O(1) operations

   Full removal and fresh insertion maintain O(1) updates and correctness.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Proper removal prevents duplicates and stale buckets [OK]

Hint: Full removal before reuse ensures correctness and O(1) ops [OK]

Common Mistakes:

• Keeping keys with zero count in data structure causes bugs

5. Suppose the data stream allows duplicate numbers to be removed after insertion, requiring support for removeNum(num). Which modification to the balanced two heaps approach is necessary to maintain correct median retrieval?

hard

A. Use a balanced binary search tree instead of heaps to allow efficient removals.

B. Ignore removals and only add numbers, as removals break the heap structure.

C. Rebuild both heaps from scratch after every removal to maintain heap properties.

D. Add a delayed deletion map to mark elements for lazy removal and prune heaps during addNum and findMedian.

Solution

1. Step 1: Understand removal challenges

   Heaps do not support efficient arbitrary removals, so direct removal breaks heap properties.

2. Step 2: Use lazy deletion

   Maintain a delayed deletion map to mark elements for removal and prune them lazily during heap operations, preserving heap structure and efficiency.

3. Step 3: Avoid costly rebuilds

   Rebuilding heaps on every removal is inefficient; ignoring removals is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Lazy deletion with pruning maintains correctness and efficiency [OK]

Hint: Lazy deletion map enables efficient removals in heaps [OK]

Common Mistakes:

• Rebuilding heaps on every removal
• Ignoring removals breaks correctness