Scale Engineer

Snapshot Array

Med
#1079Time: - **Constructor**: O(L) to initialize the array. - **`set`**: O(1). - **`snap`**: O(L) due to the array copying. - **`get`**: O(1) for HashMap lookup.Space: O(S * L), where S is the number of snapshots and L is the array length. This is because for each of S snapshots, we store a full copy of the array of length L.7 companies
Patterns
Design
Algorithms
Binary Search
Data structures
ArrayHash Table
Companies
NvidiaSnowflakeCoupangDatabricks

Prompt

Implement 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 we called snap() minus 1.
  • int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

 

Example 1:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

 

Constraints:

  • 1 <= length <= 5 * 104
  • 0 <= index < length
  • 0 <= val <= 109
  • 0 <= snap_id < (the total number of times we call snap())
  • At most 5 * 104 calls will be made to set, snap, and get.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach is the most straightforward and intuitive. We maintain a current version of the array. Every time snap() is called, we create a complete, deep copy of the current array and store it in a map, using the snap_id as the key. This ensures that we have a perfect record of the array's state for each snapshot.

Algorithm

  • Initialize current_array of size length, a HashMap<Integer, int[]> snapshots, and snap_id = 0.
  • set(index, val): Update current_array[index] = val.
  • snap():
    1. Create a copy: int[] copy = Arrays.copyOf(current_array, length).
    2. Store the copy: snapshots.put(snap_id, copy).
    3. Return snap_id++.
  • get(index, snap_id):
    1. Retrieve the snapshot: int[] snapshot_array = snapshots.get(snap_id).
    2. Return snapshot_array[index].

Walkthrough

In this method, we use a simple integer array, let's call it current_array, to store the most recent state of the data. A HashMap<Integer, int[]> named snapshots is used to store the historical versions of the array, where the key is the snap_id and the value is the array state at that snapshot. A counter snap_id tracks the number of snapshots taken.

  • SnapshotArray(length): Initializes current_array of the given length with zeros, initializes the snapshots map, and sets snap_id to 0.
  • set(index, val): Updates the value in current_array at the given index. This is a constant time operation.
  • snap(): This is the core of this approach. It creates a deep copy of current_array and stores it in the snapshots map with the current snap_id. It then increments snap_id and returns the ID of the snapshot just created. The copy operation takes time proportional to the length of the array.
  • get(index, snap_id): Retrieves the array corresponding to the given snap_id from the snapshots map and then returns the element at the specified index.
import java.util.Arrays;import java.util.HashMap;import java.util.Map; class SnapshotArray {    private int[] current_array;    private Map<Integer, int[]> snapshots;    private int snap_id;     public SnapshotArray(int length) {        current_array = new int[length];        snapshots = new HashMap<>();        snap_id = 0;    }     public void set(int index, int val) {        current_array[index] = val;    }     public int snap() {        int[] copy = Arrays.copyOf(current_array, current_array.length);        snapshots.put(snap_id, copy);        return snap_id++;    }     public int get(int index, int snap_id) {        int[] snapshot_array = snapshots.get(snap_id);        return snapshot_array[index];    }}

Complexity

Time

- **Constructor**: O(L) to initialize the array. - **`set`**: O(1). - **`snap`**: O(L) due to the array copying. - **`get`**: O(1) for HashMap lookup.

Space

O(S * L), where S is the number of snapshots and L is the array length. This is because for each of S snapshots, we store a full copy of the array of length L.

Trade-offs

Pros

  • Simple to understand and implement.

  • set and get operations are very fast (O(1)).

Cons

  • snap() operation is slow, with a time complexity of O(L), where L is the length of the array.

  • Extremely high space complexity (O(S * L), where S is the number of snapshots), making it infeasible for large inputs.

Solutions

class SnapshotArray { private List < int []>[] arr ; private int idx ; public SnapshotArray ( int length ) { arr = new List [ length ]; Arrays . setAll ( arr , k -> new ArrayList <>()); } public void set ( int index , int val ) { arr [ index ]. add ( new int [] { idx , val }); } public int snap () { return idx ++; } public int get ( int index , int snap_id ) { var vals = arr [ index ]; int left = 0 , right = vals . size (); while ( left < right ) { int mid = ( left + right ) >> 1 ; if ( vals . get ( mid )[ 0 ] > snap_id ) { right = mid ; } else { left = mid + 1 ; } } return left == 0 ? 0 : vals . get ( left - 1 )[ 1 ]; } } /** * Your SnapshotArray object will be instantiated and called as such: * SnapshotArray obj = new SnapshotArray(length); * obj.set(index,val); * int param_2 = obj.snap(); * int param_3 = obj.get(index,snap_id); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem