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

2. Examine the following erase method snippet from a skiplist implementation. Which line contains a subtle bug that can cause nodes to remain in higher levels after deletion, leading to incorrect search results?

medium

A. Line initializing update array with null

B. Line where curr is moved forward after search loop

C. Line updating update[i].forward[i] to skip curr

D. Line missing adjustment of self.level after deletion

Solution

1. Step 1: Identify erase steps

   Nodes are removed by updating forward pointers at each level where the node exists.

2. Step 2: Check for level adjustment

   After deletion, if top levels become empty, self.level must be decreased to avoid stale levels.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Missing level adjustment causes nodes to remain logically in higher levels [OK]

Hint: Always adjust max level after erase to remove empty top levels [OK]

Common Mistakes:

• Forgetting to update all levels
• Not decreasing max level after erase
• Incorrect pointer updates

3. Consider this buggy snippet of the optimal Twitter design's getNewsFeed method:

def getNewsFeed(self, userId: int) -> list:
    users = self.followees.get(userId, set()).copy()
    heap = []  # max heap by time

    for u in users:
        head = self.userTweets.get(u, None)
        if head:
            heapq.heappush(heap, (-head.time, head))

    result = []
    while heap and len(result) < 10:
        time, node = heapq.heappop(heap)
        result.append(node.tweetId)
        if node.next:
            heapq.heappush(heap, (-node.next.time, node.next))
    return result

What is the subtle bug in this code?

medium

A. The user's own tweets are not included because userId is not added to users set.

B. The heap is used as a min heap instead of max heap by pushing negative times.

C. The linked list nodes are not updated correctly after popping from the heap.

D. The followees set is copied unnecessarily causing performance overhead.

Solution

1. Step 1: Check inclusion of user's own tweets

   The code gets followees but never adds the userId itself to the users set, so user's own tweets are excluded.

2. Step 2: Verify heap usage and linked list traversal

   Negative times are correctly used for max heap behavior; linked list next pointers are used properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing userId in users set causes incorrect feed [OK]

Hint: User's own tweets must be explicitly included in feed [OK]

Common Mistakes:

• Forgetting to add userId to followees set
• Misusing heap sign for max heap

4. What is the time complexity of the divide and conquer approach to the Skyline Problem when given n buildings? Assume merging two skylines of total length m takes O(m) time.

medium

A. O(n²)

B. O(n)

C. O(n log n)

D. O(n * w) where w is the width of the skyline

Solution

1. Step 1: Identify divide and conquer recurrence

   The algorithm splits buildings into halves recursively, then merges skylines in O(m) time where m is proportional to n.

2. Step 2: Solve recurrence and analyze merge cost

   Recurrence is T(n) = 2T(n/2) + O(n), which solves to O(n log n). The width w does not affect complexity here.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Divide and conquer with linear merge per level -> O(n log n) [OK]

Hint: Divide and conquer recurrence T(n)=2T(n/2)+O(n) -> O(n log n) [OK]

Common Mistakes:

• Confusing width w with n
• Assuming quadratic due to nested loops

5. Suppose the Twitter design is extended so that users can post the same tweet multiple times (tweet reuse allowed). Which modification to the optimal approach is necessary to correctly handle this scenario?

hard

A. Allow multiple TweetNode instances with the same tweetId but different timestamps in the linked list and heap.

B. Use a hash set to track unique tweetIds per user to avoid duplicates in the feed.

C. Modify the heap to store tweetIds only once, ignoring repeated posts of the same tweetId.

D. Disallow posting duplicate tweetIds by rejecting posts with existing tweetIds.

Solution

1. Step 1: Understand tweet reuse impact

   Allowing duplicate tweetIds means multiple posts with same id but different times must be treated as distinct tweets.

2. Step 2: Adjust data structures

   Each post creates a new TweetNode with unique timestamp; heap and linked lists handle duplicates naturally by time ordering.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multiple nodes with same tweetId but different times must be stored separately [OK]

Hint: Treat each post as unique by timestamp, even if tweetId repeats [OK]

Common Mistakes:

• Trying to deduplicate tweets in feed incorrectly
• Rejecting duplicate posts unnecessarily