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. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list:
Node1(val=1) -> Node2(val=2) -> Node3(val=3), where Node1.random = Node3, Node2.random = Node1, Node3.random = null.
After Step 2 (assigning random pointers), what is the value of copy_curr.random.val when copy_curr points to the copied node of Node2?

easy

A. None (null)

B. 3

C. 1

D. 2

Solution

1. Step 1: Trace Step 1 (interleaving nodes)

   Original list: 1 -> 2 -> 3 becomes 1 -> 1' -> 2 -> 2' -> 3 -> 3'.

2. Step 2: Trace Step 2 (assign random pointers)

   Node2.random = Node1, so copied Node2 (2') random = Node1.next = 1'. Thus, copy_curr.random.val = 1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   copy_curr.random points to copied Node1 with val=1 [OK]

Hint: Copied node's random points to original.random.next [OK]

Common Mistakes:

• Confusing original and copied nodes when assigning random pointers
• Off-by-one errors in stepping through interleaved list
• Assuming random pointer points to original node's val

2. You are given a doubly linked list where some nodes have a child pointer to another doubly linked list. The child lists can themselves have children, and so on. Which approach best guarantees an in-place flattening of this multilevel list into a single-level doubly linked list without using extra space?

easy

A. Iteratively traverse the list, and whenever a node has a child, splice the child list in place by connecting the child's tail to the node's next, updating pointers accordingly.

B. Use a recursive depth-first traversal that returns the tail of each flattened child list to connect nodes.

C. Apply a greedy approach that always appends child lists at the end of the main list after full traversal.

D. Use dynamic programming to store intermediate flattened sublists and merge them bottom-up.

Solution

1. Step 1: Understand the problem constraints

   The problem requires flattening a multilevel doubly linked list in-place without extra space.

2. Step 2: Identify the approach that guarantees in-place flattening without extra space

   Using a recursive depth-first traversal that returns the tail of each flattened child list allows splicing child lists correctly and efficiently without extra data structures.

3. Step 3: Evaluate other options

   Iterative splicing (Iteratively traverse the list, and whenever a node has a child, splice the child list in place by connecting the child's tail to the node's next, updating pointers accordingly.) can cause repeated tail searches leading to O(n^2) time and is less straightforward. Greedy appending (Apply a greedy approach that always appends child lists at the end of the main list after full traversal.) fails to maintain order. Dynamic programming (Use dynamic programming to store intermediate flattened sublists and merge them bottom-up.) is not applicable.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Recursive DFS approach is standard and efficient for in-place flattening [OK]

Hint: Recursive DFS returns tail to connect lists efficiently [OK]

Common Mistakes:

• Assuming iterative splicing is always best despite complexity
• Appending child lists only at the end
• Using DP which is not applicable here

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

4. What is the time complexity of performing n operations (push, pop, increment) on the optimal CustomStack implementation that uses a lazy increment array?

medium

A. O(n * k), where k is the increment size

B. O(n + k), where k is the maximum increment size

C. O(n log n), due to increment propagation

D. O(n), total for all operations combined

Solution

1. Step 1: Analyze push and pop operations

   Each push and pop is O(1) amortized, as they add or remove one element.

2. Step 2: Analyze increment operation

   Increment only updates inc array at one index, O(1) per call. Propagation happens lazily during pop, each element's increment propagated once.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All n operations combined run in O(n) total time [OK]

Hint: Lazy increments make all operations O(1) amortized, total O(n) [OK]

Common Mistakes:

• Assuming increment is O(k) per call
• Confusing total time with per-operation time

5. Suppose the data structure must now support a new operation: getRandomWeighted(), which returns a random element with probability proportional to the number of times it appears (its frequency). Which modification to the optimized Insert Delete GetRandom O(1) with duplicates data structure is correct to support this efficiently?

hard

A. Maintain a list with each element repeated as many times as its frequency; getRandomWeighted() picks uniformly from this list.

B. Use a hash map from element to frequency and sample elements proportionally using a prefix sum array updated on insert/remove.

C. Use the existing list and hash map without changes; getRandomWeighted() is same as getRandom().

D. Store frequencies in a balanced BST and perform weighted random selection by traversing the tree.

Solution

1. Step 1: Understand weighted random requirements

   getRandomWeighted() must return elements with probability proportional to their frequency.

2. Step 2: Evaluate options

   Maintain a list with each element repeated as many times as its frequency; getRandomWeighted() picks uniformly from this list. duplicates elements in list, causing O(n) space and slow updates. Use the existing list and hash map without changes; getRandomWeighted() is same as getRandom(). ignores weighting. Store frequencies in a balanced BST and perform weighted random selection by traversing the tree. adds complexity and O(log n) operations. Use a hash map from element to frequency and sample elements proportionally using a prefix sum array updated on insert/remove. maintains frequencies and prefix sums, enabling O(log n) or better weighted sampling with efficient updates.

3. Step 3: Choose best tradeoff

   Use a hash map from element to frequency and sample elements proportionally using a prefix sum array updated on insert/remove. is the most efficient and scalable approach to support weighted random sampling with dynamic updates.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Prefix sums enable efficient weighted sampling [OK]

Hint: Prefix sums on frequencies enable weighted random sampling [OK]

Common Mistakes:

• Using naive repeated list causing high space
• Ignoring frequency updates
• Assuming getRandom() suffices for weighted sampling