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. Given the following Python code snippet implementing the AllOne data structure, what is the output of getMaxKey() after these operations?

all_one = AllOne() all_one.inc('apple') all_one.inc('banana') all_one.inc('apple') all_one.dec('banana') print(all_one.getMaxKey())

easy

A. "" (empty string)

B. "apple"

C. "banana"

D. Raises an exception

Solution

1. Step 1: Trace increments and decrements

   After inc('apple') twice, 'apple' count = 2. 'banana' incremented once then decremented once, so removed.

2. Step 2: Check getMaxKey()

   Max count bucket is 2 with 'apple'. So getMaxKey() returns 'apple'.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Only 'apple' remains with max count 2 [OK]

Hint: Max key is the one with highest count after updates [OK]

Common Mistakes:

• Forgetting to remove 'banana' after dec to zero count

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. You need to design a cache that evicts the least frequently used item when full, and among items with the same frequency, evicts the least recently used one. Which approach guarantees O(1) average time complexity for both get and put operations?

easy

A. Using a simple hash map with frequency counts and sorting keys on each eviction

B. Maintaining a frequency map of doubly linked lists to track keys by frequency and recency

C. Using a min-heap keyed by frequency and timestamp to evict the least frequently used item

D. Using a single doubly linked list ordered by frequency and recency

Solution

1. Step 1: Understand the eviction criteria

   The cache must evict the least frequently used key, and if multiple keys share the same frequency, evict the least recently used among them.

2. Step 2: Identify data structures supporting O(1) operations

   A frequency map with doubly linked lists allows grouping keys by frequency and maintaining recency order within each frequency group, enabling O(1) updates and eviction.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Frequency map + doubly linked lists is the classic LFU O(1) approach [OK]

Hint: Frequency map + doubly linked lists enable O(1) LFU cache [OK]

Common Mistakes:

• Using sorting on eviction is too slow
• Min-heap adds O(log n) overhead
• Single list can't maintain frequency and recency efficiently

4. Examine the following buggy code snippet from the AllOne data structure. Which line contains the subtle bug that causes keys to remain in multiple buckets after incrementing, leading to incorrect max/min results?

def inc(self, key: str) -> None:
    if key not in self.key_to_bucket:
        if 1 not in self.count_to_bucket:
            new_bucket = Bucket(1)
            self._insert_bucket_after(new_bucket, self.head)
        self.count_to_bucket[1].keys.add(key)
        self.key_to_bucket[key] = self.count_to_bucket[1]
    else:
        curr_bucket = self.key_to_bucket[key]
        next_count = curr_bucket.count + 1
        if next_count not in self.count_to_bucket:
            new_bucket = Bucket(next_count)
            self._insert_bucket_after(new_bucket, curr_bucket)
        self.count_to_bucket[next_count].keys.add(key)
        self.key_to_bucket[key] = self.count_to_bucket[next_count]
        # BUG: Missing removal of key from old bucket
        # curr_bucket.keys.remove(key)
        if len(curr_bucket.keys) == 0:
            self._remove_bucket(curr_bucket)

medium

A. Line removing key from old bucket's keys set (commented out)

B. Line updating key_to_bucket mapping

C. Line removing empty bucket if keys set is empty

D. Line adding key to new bucket's keys set

Solution

1. Step 1: Identify key movement between buckets

   When incrementing, key must be removed from old bucket's keys set.

2. Step 2: Locate missing removal

   The commented out line that removes the key from old bucket is missing, causing key to appear in multiple buckets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without removal, max/min queries become incorrect due to duplicate keys [OK]

Hint: Key must be removed from old bucket after increment [OK]

Common Mistakes:

• Forgetting to remove key from old bucket after increment/decrement

5. Consider the following buggy code snippet for merging two skylines. Which line contains the subtle bug that can cause incorrect skyline output?

medium

A. Line where merged.append([x, max_h]) is called unconditionally

B. Line where x, h1 = left[i] inside first if

C. Line where max_h is computed with max(h1, h2)

D. Line where i and j are incremented in the else block

Solution

1. Step 1: Identify difference from correct code

   The bug is that merged.append is called every iteration without checking if height changed, causing redundant points.

2. Step 2: Understand impact of redundant points

   Appending points even when max_h equals previous height leads to unnecessary key points, failing correctness checks.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct code appends only if height changes [OK]

Hint: Appending only on height change avoids redundant points [OK]

Common Mistakes:

• Appending every iteration regardless of height change
• Incorrect pointer increments