We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Snapshot Array

Number: 1249

Difficulty: Medium

Paid? No

Companies: Google, Databricks, Rubrik, Verkada, Microsoft, Amazon, Snowflake, Nvidia

Problem Description

Design a data structure called SnapshotArray that simulates an array which supports setting values, taking snapshots, and retrieving historical values based on a snapshot identifier. Initially, every element is 0. The methods include set(index, val) to update an element, snap() to record the current state of the array and return a snapshot id, and get(index, snap_id) to fetch the value at a given index from a particular snapshot.

Key Insights

  • Use per-index storage to maintain history of changes; record only when updates occur.
  • Each index stores a list of (snap_id, value) pairs, sorted by snap_id.
  • Utilize binary search during a get operation to efficiently find the most recent update not exceeding the provided snap_id.
  • Keep a current snap_id counter and update it with each snap() call.

Space and Time Complexity

Time Complexity:

  • set: O(1) (amortized)
  • snap: O(1)
  • get: O(log S), where S is the number of times an index was set (binary search over updates) Space Complexity: O(n + total number of set operations), since we store only updates per index.

Solution

We maintain a history for each array index as a list of pairs with each pair containing a snapshot id and its corresponding value. When setting a value, if the latest snapshot id in the history for that index matches the current snap_id, update the value. Otherwise, append a new (snap_id, value) pair. The snap() method will increment the snap_id counter and return the previous counter. The get() method performs a binary search on the history list for the given index to locate the most recent update where snap_id is less than or equal to the queried snap_id.

Code Solutions

class SnapshotArray:
    def __init__(self, length: int):
        # Initialize a history for each index with an initial value 0 at snap_id 0.
        self.data = [[(0, 0)] for _ in range(length)]
        # Current snapshot id starts at 0.
        self.snap_id = 0

    def set(self, index: int, val: int) -> None:
        # Get the history list for the index.
        history = self.data[index]
        # If the most recent set was made in the current snapshot, update it.
        if history[-1][0] == self.snap_id:
            history[-1] = (self.snap_id, val)
        else:
            # Otherwise, append a new record for this snapshot.
            history.append((self.snap_id, val))

    def snap(self) -> int:
        # Return the current snap_id then increment for the next snapshot.
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        history = self.data[index]
        # Binary search for the right-most record not exceeding snap_id.
        l, r = 0, len(history) - 1
        while l <= r:
            mid = (l + r) // 2
            if history[mid][0] <= snap_id:
                l = mid + 1
            else:
                r = mid - 1
        # r holds the latest index where the snapshot id is <= snap_id.
        return history[r][1]
        
# Example usage:
# snapshotArr = SnapshotArray(3)
# snapshotArr.set(0, 5)
# print(snapshotArr.snap())  # returns 0
# snapshotArr.set(0, 6)
# print(snapshotArr.get(0, 0))  # returns 5
← Back to All Questions