Snapshot Array

📋

Problem

Imagine you are building a version control system for an array where you can take snapshots and query historical values efficiently.

Design a SnapshotArray that supports the following interface: - SnapshotArray(int length): Initializes an array-like data structure with the given length. Initially, each element equals 0. - void set(index, val): Sets the element at the given index to be equal to val. - int snap(): Takes a snapshot of the array and returns the snap_id: the total number of times snap() has been called minus 1. - int get(index, snap_id): Returns the value at the given index, at the time the snapshot with snap_id was taken.

1 ≤ length ≤ 10^5At most 5 * 10^4 calls will be made to set, snap, and get.0 ≤ index < length0 ≤ snap_id < number of times snap() has been called0 ≤ val ≤ 10^9

Edge cases: Calling get on an index that was never set after initialization → returns 0Multiple sets on the same index before a snap → only the last set before snap is recordedCalling snap multiple times without any set in between → snapshots should be distinct

</>

IDE

class SnapshotArray: def __init__(self, length: int): ... def set(self, index: int, val: int) -> None: ... def snap(self) -> int: ... def get(self, index: int, snap_id: int) -> int: ...public class SnapshotArray { public SnapshotArray(int length) { // ... } public void set(int index, int val) { // ... } public int snap() { // ... } public int get(int index, int snap_id) { // ... } }class SnapshotArray { public: SnapshotArray(int length) { // ... } void set(int index, int val) { // ... } int snap() { // ... } int get(int index, int snap_id) { // ... } };class SnapshotArray { constructor(length) { // ... } set(index, val) { // ... } snap() { // ... } get(index, snap_id) { // ... } }

class SnapshotArray:
    def __init__(self, length: int):
        # Write your solution here
        pass
    def set(self, index: int, val: int) -> None:
        pass
    def snap(self) -> int:
        pass
    def get(self, index: int, snap_id: int) -> int:
        pass

public class SnapshotArray {
    public SnapshotArray(int length) {
        // Write your solution here
    }
    public void set(int index, int val) {
    }
    public int snap() {
        return 0;
    }
    public int get(int index, int snap_id) {
        return 0;
    }
}

#include <vector>
using namespace std;

class SnapshotArray {
public:
    SnapshotArray(int length) {
        // Write your solution here
    }
    void set(int index, int val) {
    }
    int snap() {
        return 0;
    }
    int get(int index, int snap_id) {
        return 0;
    }
};

class SnapshotArray {
    constructor(length) {
        // Write your solution here
    }
    set(index, val) {
    }
    snap() {
        return 0;
    }
    get(index, snap_id) {
        return 0;
    }
}

Common Bugs to Avoid

Wrong: Returning the last set value regardless of snap_idNot storing historical values per snap_id, ignoring snapshot versions.✅ Store (snap_id, val) pairs per index and binary search on get for correct snap_id.

Wrong: Returning 0 for all gets even after sets and snapsNot recording set operations or snap increments properly.✅ Ensure snap increments snap_id and set records values per index.

Wrong: Returning earlier set value instead of last set before snapNot overwriting multiple sets before snap for same index.✅ Update last set value for current snap_id before snap is taken.

Wrong: Index out of range error or wrong value for invalid snap_idNot validating snap_id in get method.✅ Check snap_id bounds and return 0 or error if invalid.

Wrong: TLE on large inputsUsing full snapshot copies or linear search on get.✅ Use hash map per index with binary search for get to achieve O(log m).

✓

Test Cases

Focus on base cases like unset indices and multiple sets before snap.

Think about binary search and overwriting sets before snap.

Optimize get operations with binary search to avoid TLE.

t1_01basic

Input{"length":3,"operations":[["set",0,5],["snap"],["set",0,6],["get",0,0]]}

Expected[0,5]

⏱ Performance - must finish in 2000ms

Initialize array length 3 with zeros. Set index 0 to 5. Snap returns snap_id=0. Set index 0 to 6. Get index 0 at snap_id 0 returns 5, the value at snapshot time.

💡 Think about how to store changes efficiently between snapshots.

💡 Use a data structure that records changes per index with snapshot ids.

💡 Store pairs of (snap_id, val) per index and binary search on get.

Why it failed: Returned wrong snap_id or value. Possibly storing full snapshots incorrectly or not recording last set before snap. Fix by storing changes per index and returning correct snapshot value.

✓ Correctly handles basic set, snap, and get operations.

t1_02basic

Input{"length":2,"operations":[["set",1,10],["snap"],["set",1,20],["snap"],["get",1,0],["get",1,1]]}

Expected[0,10,1,20]

⏱ Performance - must finish in 2000ms

Set index 1 to 10, snap returns 0. Set index 1 to 20, snap returns 1. Get index 1 at snap 0 returns 10, at snap 1 returns 20.

💡 Remember each snap increments snap_id by 1.

💡 Ensure multiple snaps without intermediate sets still produce distinct snap_ids.

💡 On get, find the latest set value at or before the requested snap_id.

Why it failed: Incorrect snap_id or get value returned. Possibly not incrementing snap_id correctly or not handling multiple snaps. Fix by incrementing snap_id on snap and binary searching sets per index.

✓ Correctly handles multiple snaps and gets.

t2_01edge

Input{"length":1,"operations":[["snap"],["get",0,0]]}

Expected[0,0]

⏱ Performance - must finish in 2000ms

Array length 1 initialized with 0. Snap returns 0. Get index 0 at snap 0 returns 0 since no set was done.

💡 Check behavior when get is called on index never set.

💡 Default values should be zero if no set before snap.

💡 Initialize each index with a default (snap_id=-1, val=0) to handle this.

Why it failed: Returned non-zero value for unset index. Fix by initializing each index with (snap_id=-1, val=0) so get returns 0 if no set.

✓ Correctly returns 0 for unset indices.

t2_02edge

Input{"length":2,"operations":[["set",0,1],["set",0,2],["snap"],["get",0,0]]}

Expected[0,2]

⏱ Performance - must finish in 2000ms

Multiple sets on same index before snap; only last set (2) recorded for snap 0.

💡 Multiple sets before snap should overwrite previous sets.

💡 Only the last set before snap counts for that snap_id.

💡 Update the value for the current snap_id before snap is taken.

Why it failed: Returned earlier set value instead of last set before snap. Fix by updating the last set value for current snap_id before snap.

✓ Correctly records only last set before snap.

t2_03edge

Input{"length":1,"operations":[["snap"],["snap"],["snap"],["get",0,0],["get",0,1],["get",0,2]]}

Expected[0,0,1,0,2,0]

⏱ Performance - must finish in 2000ms

Multiple snaps without sets produce distinct snap_ids 0,1,2. Gets return 0 as no sets done.

💡 Snap increments snap_id even if no set done.

💡 Ensure snapshots are distinct and get returns correct values.

💡 Store snap count separately and return it on snap.

Why it failed: Snap IDs not incremented correctly or get returns wrong values. Fix by incrementing snap_id on each snap and returning 0 if no set.

✓ Correctly handles multiple snaps without sets.

t3_01corner

Input{"length":3,"operations":[["set",0,1],["snap"],["set",0,2],["snap"],["set",0,3],["get",0,0],["get",0,1],["get",0,2]]}

Expected[0,1,1,2,2,3]

⏱ Performance - must finish in 2000ms

Tests correct retrieval of values for multiple snaps with sets between snaps.

💡 Check that get returns the value at or before snap_id, not after.

💡 Use binary search to find the right snapshot value per index.

💡 Return the value from the largest snap_id <= requested snap_id.

Why it failed: Returned value from snap after requested snap_id (greedy mistake). Fix by binary searching for largest snap_id <= requested snap_id.

✓ Correctly returns values for multiple snaps.

t3_02corner

Input{"length":2,"operations":[["set",0,5],["snap"],["set",0,10],["set",0,15],["snap"],["get",0,0],["get",0,1]]}

Expected[0,5,1,15]

⏱ Performance - must finish in 2000ms

Multiple sets before snap 1; only last set (15) recorded for snap 1.

💡 Ensure multiple sets before snap overwrite previous sets for that snap.

💡 Do not accumulate multiple entries for same snap_id per index.

💡 Update the last set value for current snap_id before snap.

Why it failed: Returned earlier set value for snap 1 instead of last set. Fix by overwriting last set value for current snap_id before snap.

✓ Correctly records last set before snap.

t3_03corner

Input{"length":1,"operations":[["set",0,7],["snap"],["get",0,1]]}

Expected[0,7,0]

⏱ Performance - must finish in 2000ms

Get called with snap_id that does not exist (1) returns 0 or error handled gracefully.

💡 Check bounds of snap_id in get calls.

💡 Return 0 or handle gracefully if snap_id >= current snap count.

💡 Validate snap_id before accessing snapshot data.

Why it failed: Index out of range or wrong value returned for invalid snap_id. Fix by validating snap_id and returning 0 if invalid.

✓ Gracefully handles invalid snap_id in get.

t4_01performance

Input{"length":100,"operations":[["set",0,1],["snap"],["set",1,2],["snap"],["set",2,3],["snap"],["set",3,4],["snap"],["set",4,5],["snap"],["set",5,6],["snap"],["set",6,7],["snap"],["set",7,8],["snap"],["set",8,9],["snap"],["set",9,10],["snap"],["get",0,0],["get",1,1],["get",2,2],["get",3,3],["get",4,4],["get",5,5],["get",6,6],["get",7,7],["get",8,8],["get",9,9]]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(log m) per get with m snaps must complete within 2 seconds.

💡 Use binary search to achieve O(log m) get time.

💡 Avoid storing full snapshots to save memory and time.

💡 Store changes per index with snap_id and binary search on get.

Why it failed: TLE due to O(n*m) or linear search in get. Fix by using binary search on stored snapshots per index.

✓ Algorithm runs within time limits using binary search.

Practice

1. You need to design a data structure that supports incrementing and decrementing string keys, and retrieving a key with the maximum or minimum count, all in constant time. Which approach best guarantees O(1) time complexity for all these operations?

easy

A. Using a balanced binary search tree keyed by counts to maintain order of keys

B. Using a hash map to store counts and scanning all keys to find max/min when requested

C. Maintaining a doubly linked list of buckets, each bucket holding keys with the same count, plus hash maps for quick access

D. Using a priority queue to track max and min keys with lazy updates

Solution

1. Step 1: Understand operation requirements

   Increment, decrement, getMaxKey, and getMinKey must all be O(1).

2. Step 2: Evaluate approaches

   Hash map + linear scan (B) is O(n) for max/min. Balanced BST (C) and priority queue (D) have O(log n) operations. Doubly linked list with buckets and hash maps (A) supports O(1) updates and retrievals.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bucket list + hash maps enable O(1) increments, decrements, and max/min retrievals [OK]

Hint: Bucket list + hash maps enable O(1) max/min updates [OK]

Common Mistakes:

• Thinking balanced BST or priority queue can achieve O(1) for all operations

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. The following code attempts to copy a linked list with random pointers using the optimal weaving approach. Identify the line that contains a subtle bug that can cause incorrect random pointer assignment or list corruption.

def copyRandomList(head):
    if not head:
        return None
    curr = head
    # Step 1: Insert copied nodes
    while curr:
        new_node = Node(curr.val, curr.next)
        curr.next = new_node
        curr = new_node.next
    # Step 2: Assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random  # Bug here
        curr = curr.next.next
    # Step 3: Separate lists
    curr = head
    copy_head = head.next
    copy_curr = copy_head
    while curr:
        curr.next = curr.next.next
        if copy_curr.next:
            copy_curr.next = copy_curr.next.next
        curr = curr.next
        copy_curr = copy_curr.next
    return copy_head

medium

A. Line assigning curr.next.random = curr.random

B. Line inserting copied nodes: curr.next = new_node

C. Line advancing curr in Step 1: curr = new_node.next

D. Line separating original and copied lists: curr.next = curr.next.next

Solution

1. Step 1: Analyze random pointer assignment

   The line assigns curr.next.random = curr.random, but curr.random points to original nodes, not copied nodes.

2. Step 2: Correct assignment

   It should be curr.next.random = curr.random.next to point to the copied node corresponding to curr.random.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect random pointer assignment breaks copied list correctness [OK]

Hint: Random pointer must point to copied node, not original [OK]

Common Mistakes:

• Assigning random pointer directly to original node
• Mixing original and copied nodes after weaving
• Forgetting to advance curr by two nodes

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