LRU Cache

▶

Steps

setup

Initialize LRUCache with capacity 2

Create dummy head and tail nodes and link them. Initialize empty cache map and set capacity to 2.

💡 Dummy nodes simplify edge cases by ensuring the list always has head and tail, even when empty.

Line:

self.capacity = capacity
self.cache = {}
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head

💡 The doubly linked list is ready to hold cache nodes between head and tail.

insert

Put key=1, value=1 into cache

Create a new node for key 1 with value 1. Add it right after head to mark it most recently used. Insert into cache map.

💡 New nodes are always added right after head to mark them as most recently used.

Line:

node = Node(1, 1)
self._add(node)
self.cache[1] = node

💡 The cache now contains one node between head and tail, representing key 1 as most recently used.

insert

Put key=2, value=2 into cache

Create a new node for key 2 with value 2. Add it right after head, pushing key 1 node back. Insert into cache map.

💡 Adding new nodes at the front keeps the most recent usage order updated.

Line:

node = Node(2, 2)
self._add(node)
self.cache[2] = node

💡 The list order is now key 2 (most recent) -> key 1 -> tail.

get

Get key=1 from cache

Key 1 is found in cache. Remove its node from current position and add it right after head to mark as most recently used.

💡 Accessing a key moves it to the front to update usage order.

Line:

node = self.cache[key]
self._remove(node)
self._add(node)
return node.val

💡 The node for key 1 moves to front, making key 2 second most recent.

insert

Put key=3, value=3 into cache (capacity exceeded)

Key 3 is new. Create node and add to front. Cache size exceeds capacity, so remove least recently used node (key 2) from tail and delete from map.

💡 When capacity is exceeded, the least recently used node at tail.prev is evicted.

Line:

node = Node(3, 3)
self._add(node)
self.cache[3] = node
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]

💡 The cache now holds keys 3 and 1, with 3 most recent and 1 second.

get

Get key=2 from cache (not found)

Key 2 was evicted previously, so it is not found in cache. Return -1.

💡 A get for a missing key returns -1 immediately.

Line:

if key not in self.cache:
    return -1

💡 Evicted keys are no longer accessible.

insert

Put key=4, value=4 into cache (capacity exceeded)

Key 4 is new. Create node and add to front. Cache size exceeds capacity, so remove least recently used node (key 1) from tail and delete from map.

💡 Eviction always removes the least recently used node at tail.prev.

Line:

node = Node(4, 4)
self._add(node)
self.cache[4] = node
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]

💡 Cache now holds keys 4 and 3, with 4 most recent.

get

Get key=1 from cache (not found)

Key 1 was evicted in previous step, so it is not found. Return -1.

💡 Cache misses return -1 immediately.

Line:

if key not in self.cache:
    return -1

💡 Evicted keys cannot be retrieved.

get

Get key=3 from cache

Key 3 is found. Remove its node from current position and add it right after head to mark as most recently used.

💡 Access moves the node to front to update usage order.

Line:

node = self.cache[key]
self._remove(node)
self._add(node)
return node.val

💡 Key 3 becomes most recently used, key 4 second.

get

Get key=4 from cache

Key 4 is found. Remove its node from current position and add it right after head to mark as most recently used.

💡 Access moves the node to front to update usage order.

Line:

node = self.cache[key]
self._remove(node)
self._add(node)
return node.val

💡 Key 4 becomes most recently used, key 3 second.

class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity  # STEP 1
        self.cache = {}          # STEP 1
        self.head = Node()       # STEP 1
        self.tail = Node()       # STEP 1
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next = nxt
        nxt.prev = prev

    def _add(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:  # STEP 6,8
            return -1
        node = self.cache[key]     # STEP 4,9,10
        self._remove(node)         # STEP 4,9,10
        self._add(node)            # STEP 4,9,10
        return node.val            # STEP 4,9,10

    def put(self, key: int, value: int) -> None:
        if key in self.cache:      # STEP 5
            self._remove(self.cache[key])
        node = Node(key, value)    # STEP 2,3,5,7
        self._add(node)            # STEP 2,3,5,7
        self.cache[key] = node    # STEP 2,3,5,7
        if len(self.cache) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]

📊

LRU Cache - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the LRU cache maintains recent usage order efficiently, which is hard to grasp from code alone.

setup

null

null

insert

null

null

Key:1

Val:1

insert

null

null

Key:1

Val:1

→

Key:2

Val:2

compare

null

null

Key:1

Val:1

→

Key:2

Val:2

Result: 1

delete

null

null

Key:1

Val:1

→

Key:3

Val:3

compare

null

null

Key:1

Val:1

→

Key:3

Val:3

Result: -1

delete

null

null

Key:1

Val:1

→

Key:3

Val:3

→

Key:4

Val:4

compare

null

null

Key:1

Val:1

→

Key:3

Val:3

→

Key:4

Val:4

Result: -1

compare

null

null

Key:3

Val:3

→

Key:4

Val:4

Result: 3

compare

null

null

Key:3

Val:3

→

Key:4

Val:4

Result: 4

Key Takeaways

✓ The doubly linked list maintains usage order with O(1) updates on access and insertion.

This is hard to see from code alone because pointer updates are subtle and happen in multiple helper functions.

✓ The hash map provides O(1) access to nodes, enabling fast get and put operations.

Visualizing the map keys alongside the list clarifies how the two data structures work together.

✓ Eviction always removes the least recently used node at the tail, maintaining cache size within capacity.

Watching eviction happen step-by-step shows why the tail.prev node is the correct candidate to remove.

Practice

1. You need to design a system that supports posting tweets and retrieving the 10 most recent tweets from a user's timeline, including tweets from users they follow. Which approach best balances efficient posting and retrieving the top recent tweets in real-time?

easy

A. Store all tweets in a global list and scan it entirely each time to find the top 10 recent tweets.

B. Maintain a linked list of tweets per user, a hashmap for followees, and use a max heap to merge the most recent tweets from followees efficiently.

C. Use a dynamic programming approach to precompute the top tweets for each user after every post.

D. Use a simple array per user and sort all tweets from followees every time the feed is requested.

Solution

1. Step 1: Understand the problem constraints

   The system must support fast posting and retrieving the top 10 recent tweets from a user's followees including themselves.

2. Step 2: Evaluate approaches

   Brute force scanning or sorting all tweets each time is inefficient. DP is not applicable here. Using linked lists per user and a max heap for merging recent tweets achieves O(1) posting and O(k log F) retrieval, where F is followees count.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linked list + hashmap + heap is the optimal pattern for this problem [OK]

Hint: Linked list + heap merges recent tweets efficiently [OK]

Common Mistakes:

• Thinking sorting all tweets each time is efficient
• Trying DP for a streaming feed problem

2. Consider the following Python code snippet for the MedianFinder class using two heaps. After adding the numbers 1, 5, and 3 in that order, what is the value of the median returned by findMedian()?

easy

A. 1.0

B. 3.0

C. 5.0

D. 2.0

Solution

1. Step 1: Insert 1

   Low heap empty, push -1 to low; low_size=1, high_size=0.

2. Step 2: Insert 5

   5 > -low[0] (which is 1), push 5 to high; low_size=1, high_size=1; heaps balanced.

3. Step 3: Insert 3

   3 <= 5 but > 1, push 3 to high; high_size=2, low_size=1; balance heaps by moving smallest from high (3) to low (-3); low_size=2, high_size=1.

4. Step 4: Find median

   low_size > high_size, median is -low[0] = 3.0.

5. Step 5: Re-examine median calculation

   After balancing, low heap has [-3, -1], high heap has [5]. Median is top of low heap = 3.0, but the question asks for median after adding 1,5,3 in order, so median is 3.0.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Median after [1,5,3] is 3.0 [OK]

Hint: Median is top of larger heap after balancing [OK]

Common Mistakes:

• Forgetting to balance heaps after insertion
• Returning wrong heap top for median

3. Consider the following Python code snippet implementing the optimized Insert Delete GetRandom O(1) with duplicates data structure. After executing the sequence of operations below, what is the return value of the final getRandom() call? Operations: insert(1), insert(1), insert(2), remove(1), getRandom()

import random

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = null
        self.next = null

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(null)
        self.tail = Node(null)
        self.head.next = self.tail
        self.tail.prev = self.head

    def append(self, val):
        node = Node(val)
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node
        return node

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def is_empty(self):
        return self.head.next == self.tail

class RandomizedCollection:
    def __init__(self):
        self.nums = []
        self.idx_map = {}

    def insert(self, val: int) -> bool:
        self.nums.append(val)
        if val not in self.idx_map:
            self.idx_map[val] = set()
        self.idx_map[val].add(len(self.nums) - 1)
        return len(self.idx_map[val]) == 1

    def remove(self, val: int) -> bool:
        if val not in self.idx_map or not self.idx_map[val]:
            return false
        remove_idx = self.idx_map[val].pop()
        last_val = self.nums[-1]
        self.nums[remove_idx] = last_val
        self.idx_map[last_val].add(remove_idx)
        self.idx_map[last_val].discard(len(self.nums) - 1)
        self.nums.pop()
        if not self.idx_map[val]:
            del self.idx_map[val]
        return true

    def getRandom(self) -> int:
        return random.choice(self.nums)

rc = RandomizedCollection()
rc.insert(1)
rc.insert(1)
rc.insert(2)
rc.remove(1)
result = rc.getRandom()

easy

A. Either 1 or 2 but 1 is twice as likely

B. 2

C. Either 1 or 2 with equal probability

D. 1

Solution

1. Step 1: Trace insertions

   After insert(1), nums=[1], idx_map={1:{0}}; after insert(1), nums=[1,1], idx_map={1:{0,1}}; after insert(2), nums=[1,1,2], idx_map={1:{0,1},2:{2}}.

2. Step 2: Trace removal of one 1

   Remove one 1: remove_idx=1 (pop from idx_map[1]). Swap last element 2 into index 1: nums=[1,2], idx_map={1:{0},2:{1}}. So now nums has one 1 and one 2.

3. Step 3: Analyze getRandom probabilities

   nums=[1,2], so getRandom picks index 0 or 1 equally. But initially there were two 1's, after removal only one remains. So 1 and 2 are equally likely, but since the original had duplicates, the final collection has one 1 and one 2.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   After removal, one 1 and one 2 remain, so 1 is as likely as 2 [OK]

Hint: Track indices and swaps carefully to find final array state [OK]

Common Mistakes:

• Forgetting to update idx_map after swap
• Assuming getRandom returns only 2
• Ignoring that one 1 remains after removal

4. Examine the following buggy code snippet for the MedianFinder class. Which line contains the subtle bug that can cause incorrect median calculation?

medium

A. Condition 'if self.low_size > self.high_size:' for balancing heaps

B. Line that pushes to high heap and increments high_size

C. Line that pushes to low heap and increments low_size

D. Condition 'elif self.high_size > self.low_size + 1:' for balancing heaps

Solution

1. Step 1: Understand balancing condition

   The heaps must be balanced so that their sizes differ by at most 1.

2. Step 2: Identify incorrect condition

   The condition 'if self.low_size > self.high_size:' moves an element from low to high even when sizes differ by only 1, causing imbalance.

3. Step 3: Correct condition

   The condition should be 'if self.low_size > self.high_size + 1:' to ensure size difference is more than 1 before balancing.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Balancing condition must check if low_size > high_size + 1 [OK]

Hint: Balance heaps only if size difference > 1 [OK]

Common Mistakes:

• Balancing heaps too aggressively
• Incorrect size difference checks

5. What is the worst-case time complexity of the in-place iterative flattening algorithm for a multilevel doubly linked list where each node may have a child list, and why?

medium

A. O(n) because each node is visited once.

B. O(n) with O(n) auxiliary space for recursion stack.

C. O(n log n) due to repeated merging of child lists.

D. O(n^2) because finding the tail of each child list requires traversing child nodes repeatedly.

Solution

1. Step 1: Identify the costly operation

   Finding the tail of each child list requires traversing that child list fully.

2. Step 2: Analyze nested traversal effect

   Since this tail-finding happens for multiple nodes, total time can be quadratic in number of nodes.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Repeated tail traversal causes O(n^2) time in worst case [OK]

Hint: Repeated tail search causes quadratic time [OK]

Common Mistakes:

• Assuming linear time because each node is visited once
• Confusing recursion stack space with iterative approach