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

2. Given the following Python code for merging two skylines, and the inputs left = [[1, 3], [5, 0]] and right = [[2, 4], [6, 0]], what is the merged skyline returned by mergeSkylines(left, right)?

easy

A. [[1, 3], [2, 4], [5, 0], [6, 0]]

B. [[1, 3], [5, 0], [6, 0]]

C. [[1, 3], [2, 4], [4, 0], [6, 0]]

D. [[1, 3], [2, 4], [4, 0], [5, 0], [6, 0]]

Solution

1. Step 1: Trace first iterations of the merge loop

   Compare left[0]=(1,3) and right[0]=(2,4): 1 < 2, so x=1, h1=3, h2=0, max_h=3 -> merged=[[1,3]]

2. Step 2: Next iterations and final merge

   Next left[1]=(5,0), right[0]=(2,4): 2 < 5, x=2, h2=4, h1=3, max_h=4 -> merged=[[1,3],[2,4]]; then right[1]=(6,0) vs left[1]=(5,0): 5 < 6, x=5, h1=0, h2=4, max_h=4 (no change), then x=6, h2=0, max_h=0 -> merged=[[1,3],[2,4],[4,0],[5,0],[6,0]] after extending remaining points.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Stepwise max height updates match merged skyline [OK]

Hint: Track h1 and h2 updates carefully during merge [OK]

Common Mistakes:

• Off-by-one in indices
• Missing key points when heights change

3. What is the time complexity of the inc and dec operations in the optimized AllOne data structure that uses doubly linked list buckets and hash maps, and why?

medium

A. O(1) worst-case because all operations involve only pointer and hash map updates

B. O(1) amortized because bucket insertion and removal are constant time with hash maps

C. O(log n) due to maintaining sorted order of buckets

D. O(n) because updating buckets requires scanning keys

Solution

1. Step 1: Identify operations involved in inc/dec

   Operations include moving keys between buckets, inserting/removing buckets, and updating hash maps.

2. Step 2: Analyze complexity of each operation

   All pointer updates and hash map lookups/inserts/removals are O(1). No scanning or sorting is needed.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All operations are pointer and hash map updates, no loops over keys [OK]

Hint: Pointer and hash map ops are O(1), no scanning or sorting [OK]

Common Mistakes:

• Confusing bucket insertion as O(log n) or scanning keys as O(n)

4. Consider the following buggy code snippet for flattening a multilevel doubly linked list. Which line contains the subtle bug that can cause infinite loops or incorrect list structure?

medium

A. Missing line that sets curr.child to None after splicing

B. Line where tail is found by while tail.next:

C. Line where curr.next is set to child

D. Line where tail.next is connected to curr.next

Solution

1. Step 1: Identify the role of curr.child

   After splicing the child list, curr.child must be set to None to avoid revisiting the child.

2. Step 2: Recognize missing pointer update

   The code does not set curr.child = None, causing infinite loops or incorrect traversal.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Not clearing child pointer leads to repeated processing [OK]

Hint: Always clear child pointer after splicing [OK]

Common Mistakes:

• Forgetting to clear child pointer after splicing
• Incorrectly updating prev pointers instead

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