Snapshot Array

▶

Steps

setup

Initialize SnapshotArray with length 3

Create the SnapshotArray object with length 3. Each index initializes a linked list with one node representing snap_id -1 and value 0, indicating the initial state before any snapshots.

💡 This initialization ensures every index has a baseline value to return if no sets have been made before a snapshot.

Line:

self.snap_id = 0
self.data = [[(-1, 0)] for _ in range(length)]

💡 Each index starts with a sentinel node to represent the initial zero value before any snapshots.

insert

Set index 0 to value 5

Perform set(0, 5). Since the last recorded snap_id for index 0 is -1, which is less than current snap_id 0, append a new node with (0, 5) to index 0's linked list.

💡 Appending a new node records the value change at the current snapshot id, preserving history.

Line:

if self.data[index][-1][0] == self.snap_id:
    self.data[index][-1] = (self.snap_id, val)
else:
    self.data[index].append((self.snap_id, val))

💡 New values at a new snap_id are appended to the history list, enabling efficient snapshot tracking.

expand

Take a snapshot, increment snap_id

Call snap(), which increments snap_id from 0 to 1, then returns the previous snap_id 0 as the snapshot identifier.

💡 Incrementing snap_id marks a new snapshot point in time for future sets and gets.

Line:

self.snap_id += 1
return self.snap_id - 1

💡 snap_id increments after each snapshot, enabling versioning of the array state.

insert

Set index 0 to value 6 after snapshot

Perform set(0, 6). The last recorded snap_id for index 0 is 0, which is less than current snap_id 1, so append a new node (1, 6) to index 0's linked list.

💡 Appending a new node after a snapshot records the updated value for the new snapshot id.

Line:

if self.data[index][-1][0] == self.snap_id:
    self.data[index][-1] = (self.snap_id, val)
else:
    self.data[index].append((self.snap_id, val))

💡 Each snapshot id has its own recorded value if changed, preserving history for queries.

compare

Start get(0, 0): binary search initialization

Begin get(0, 0). Initialize binary search pointers left=0 and right=4 on index 0's linked list nodes.

💡 Binary search starts by setting boundaries to cover all nodes in the linked list for the index.

Line:

left = 0
right = len(arr) - 1

💡 Setting initial search boundaries is essential for binary search correctness.

compare

Binary search mid calculation and comparison

Calculate mid = (left + right) // 2 = 2. Compare node at mid (snap_id -1) with requested snap_id 0. Since -1 ≤ 0, move left to mid + 1 = 3.

💡 Binary search compares mid node's snap_id to target to decide which half to search next.

Line:

mid = (left + right) // 2
if arr[mid][0] <= snap_id:
    left = mid + 1
else:
    right = mid - 1

💡 Binary search narrows down the search space by comparing mid node's snap_id with target.

compare

Binary search mid calculation and comparison second iteration

Calculate mid = (left + right) // 2 = 3. Compare node at mid (snap_id 0) with requested snap_id 0. Since 0 ≤ 0, move left to mid + 1 = 4.

💡 Binary search continues to narrow down the search space by comparing mid node's snap_id with target.

Line:

mid = (left + right) // 2
if arr[mid][0] <= snap_id:
    left = mid + 1
else:
    right = mid - 1

💡 Binary search converges on the correct node by updating pointers based on comparisons.

compare

Binary search mid calculation and comparison final iteration

Calculate mid = (left + right) // 2 = 4. Compare node at mid (snap_id 1) with requested snap_id 0. Since 1 > 0, move right to mid - 1 = 3.

💡 Binary search narrows down to the correct node by adjusting right pointer when mid snap_id is greater than target.

Line:

mid = (left + right) // 2
if arr[mid][0] <= snap_id:
    left = mid + 1
else:
    right = mid - 1

💡 Binary search ends when left > right, with right pointing to the correct node.

traverse

Return value 5 for get(0, 0)

After binary search, return the value 5 stored at snap_id 0 for index 0, which is the value at the time of the snapshot.

💡 Returning the correct historical value confirms the snapshot array's correctness.

Line:

return arr[i][1]

💡 The get operation returns the value corresponding to the requested snapshot id.

reconstruct

Final state summary

The snapshot array has three indices, each with their linked list of (snap_id, value) pairs. Index 0 has three nodes showing initial 0, then 5 at snap 0, then 6 at snap 1. The final answer for get(0, 0) is 5.

💡 This final state confirms the snapshot array's internal structure and correctness of the returned value.

💡 The linked list structure efficiently stores only changes, and snapshots provide versioning for queries.

import bisect

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0  # STEP 1: Initialize snap_id
        self.data = [[(-1, 0)] for _ in range(length)]  # STEP 1: Initialize data with sentinel nodes

    def set(self, index: int, val: int) -> None:
        # STEP 2 and 4: Append or update value for current snap_id
        if self.data[index][-1][0] == self.snap_id:
            self.data[index][-1] = (self.snap_id, val)  # Update last value if same snap_id
        else:
            self.data[index].append((self.snap_id, val))  # Append new value

    def snap(self) -> int:
        self.snap_id += 1  # STEP 3: Increment snap_id
        return self.snap_id - 1  # Return previous snap_id

    def get(self, index: int, snap_id: int) -> int:
        arr = self.data[index]
        # STEP 5: Binary search for largest snap_id <= requested snap_id
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid][0] <= snap_id:
                left = mid + 1
            else:
                right = mid - 1
        return arr[right][1]  # STEP 6: Return value

# Driver code
if __name__ == '__main__':
    snapshotArr = SnapshotArray(3)  # STEP 1
    snapshotArr.set(0,5)  # STEP 2
    snap_id = snapshotArr.snap()  # STEP 3
    snapshotArr.set(0,6)  # STEP 4
    print(snap_id)  # Output: 0
    print(snapshotArr.get(0, snap_id))  # Output: 5  # STEP 5 and 6

📊

Snapshot Array - Watch the Algorithm Execute, Step by Step

Watching each operation step-by-step reveals how the snapshot array efficiently tracks changes over time without duplicating the entire array, which is hard to grasp from code alone.

initialize

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:-1

Value:0

append

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:0

Value:5

increment_snap_id

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:0

Value:5

Result: 0

append

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:0

Value:5

→

Snap id:1

Value:6

binary_search_init

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:0

Value:5

→

Snap id:1

Value:6

binary_search_compare

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:0

Value:5

→

Snap id:1

Value:6

binary_search_compare

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:0

Value:5

→

Snap id:1

Value:6

binary_search_compare

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:0

Value:5

→

Snap id:1

Value:6

return_value

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:0

Value:5

→

Snap id:1

Value:6

Result: 5

final_state

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:-1

Value:0

→

Snap id:0

Value:5

→

Snap id:1

Value:6

Result: 5

Key Takeaways

✓ SnapshotArray uses a linked list per index to store only changes at each snapshot id, avoiding full array copies.

This is hard to see from code alone because the data structure is abstracted as lists of tuples, but the visualization shows the linked list nodes explicitly.

✓ The snap() method increments the snapshot id, which acts as a version number for all subsequent sets and gets.

Understanding snap_id as a global version counter clarifies how snapshots are tracked over time.

✓ The get() method uses binary search on the linked list to efficiently find the value at or before the requested snapshot id.

This binary search step is subtle in code but critical for performance; the visualization highlights the search process.

Practice

1. You need to design a data structure that supports inserting elements (including duplicates), removing one occurrence of an element, and retrieving a random element--all in average O(1) time. Which approach best guarantees these time complexities?

easy

A. Use a simple list and perform linear search for removals.

B. Use a balanced binary search tree to maintain elements and their counts.

C. Use a hash map to store element to indices mapping, combined with a list to store elements, updating indices on insert and remove.

D. Use a queue to track insertion order and a hash set for membership checks.

Solution

1. Step 1: Understand the operations required

   Insert, remove (one occurrence), and getRandom must all be average O(1), even with duplicates.

2. Step 2: Evaluate approaches

   A simple list with linear search (A) leads to O(n) removals. Balanced BST (C) has O(log n) operations. Queue and hash set (D) do not support random access efficiently. Hash map + list with index tracking (B) supports O(1) insert, remove, and getRandom by maintaining indices of duplicates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map + list with index tracking enables O(1) average operations [OK]

Hint: Hash map + list with index tracking enables O(1) ops [OK]

Common Mistakes:

• Assuming balanced BST can do O(1) getRandom
• Using linear search for removal
• Ignoring duplicates in data structure

2. Given the following LFUCache code snippet and operations, what is the return value of cache.get(2) after these operations?

cache = LFUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)

Assume the LFUCache uses the optimal approach shown.

easy

A. -1

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace cache state after each operation

   After put(1,1) and put(2,2), cache has keys 1 and 2 with freq=1. get(1) increments freq of key 1 to 2. Then put(3,3) triggers eviction of key with min freq=1, which is key 2 (least recently used among freq=1). Key 2 is evicted.

2. Step 2: Evaluate get(2)

   Key 2 was evicted, so get(2) returns -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Key 2 evicted before get(2) call, so returns -1 [OK]

Hint: Evicted keys return -1 on get [OK]

Common Mistakes:

• Forgetting eviction removes key 2
• Assuming get(2) returns old value
• Confusing frequency increments

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 the checkOut operation in the optimal UndergroundSystem implementation that uses a linked list for check-ins, assuming n is the number of active check-ins at the time of checkout?

medium

A. O(1) because the linked list head always points to the correct check-in node

B. O(n) due to updating route data hash map entries

C. O(log n) because the linked list is sorted by check-in time

D. O(n) because it may need to traverse the linked list to find the matching check-in node

Solution

1. Step 1: Identify linked list traversal

   The checkOut method traverses the linked list from head to find the node with matching id, which can take up to O(n) time.

2. Step 2: Analyze route data update

   Updating the hash map for route data is O(1) average, so it does not dominate complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Traversal over n nodes dominates, so O(n) time [OK]

Hint: Linked list traversal dominates checkOut time [OK]

Common Mistakes:

• Assuming O(1) because head is used directly

5. Identify the bug in the following LRU Cache implementation snippet that causes incorrect eviction behavior when capacity is exceeded:

def put(self, key: int, value: int) -> None:
    if key in self.cache:
        self._remove(self.cache[key])
    node = Node(key, value)
    self._add(node)
    self.cache[key] = node
    if len(self.cache) > self.capacity:
        lru = self.head.next  # Bug here
        self._remove(lru)
        del self.cache[lru.key]

medium

A. Evicting the node at head.next instead of tail.prev

B. Removing node from cache before adding new node

C. Not updating the cache dictionary after eviction

D. Not checking if capacity is zero before eviction

Solution

1. Step 1: Understand eviction logic

   Eviction must remove the least recently used node, which is at tail.prev, not head.next.

2. Step 2: Identify bug

   Code incorrectly evicts head.next, which is the most recently used node, causing wrong eviction.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Evicting head.next breaks LRU policy, must evict tail.prev [OK]

Hint: LRU node is at tail.prev, not head.next [OK]

Common Mistakes:

• Evicting MRU instead of LRU
• Forgetting to delete from cache dict
• Not handling zero capacity