Snapshot Array

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

Snapshot Array

Implement a SnapshotArray that supports the following operations:

Requirement

SnapshotArray(length): Initializes an array-like data structure with the given length, where each element is initially 0.
set(index, val): Sets the element at the given index to be val.
snap(): Takes a snapshot of the array and returns the snap_id.
get(index, snap_id): Returns the value at the given index, corresponding to the given snap_id.

Medium

Examples

Input: SnapshotArray(3), set(0,5), snap(), set(0,6), get(0,0)
Output: [null,null,0,null,5]

Approach 1

Level I: Full Array Copy on Snap

Intuition

Every time snap() is called, we create a full copy of the current array and store it in a List<int[]>. This is $O(1)$ for set and get, but $O(N)$ for snap.

⏱ Set: O(1), Snap: O(N), Get: O(1).💾 O(N * S) where S is number of snaps.

Detailed Dry Run

Array: [0, 0]. Set(0, 5). Snap() -> Store [5, 0]. Set(0, 6). Snap() -> Store [6, 0]. Get(0, 0) -> return 5.

java

class SnapshotArray {
    int[] curr; List<int[]> snaps = new ArrayList<>();
    public SnapshotArray(int len) { curr = new int[len]; }
    public void set(int i, int v) { curr[i] = v; }
    public int snap() { snaps.add(curr.clone()); return snaps.size() - 1; }
    public int get(int i, int s) { return snaps.get(s)[i]; }
}

Approach 2

Level II: Versioned Map (HashMap per index)

Intuition

Use Map<Integer, Integer>[] arr. Each index has a map mapping snap_id -> value. This is simpler but takes more space for small changes.

⏱ Set: O(1), Snap: O(1), Get: O(log S) where S is number of snaps.💾 O(N + S * Updates).

java

class SnapshotArray {
    TreeMap<Integer, Integer>[] arr;
    int snapId = 0;
    public SnapshotArray(int len) {
        arr = new TreeMap[len];
        for (int i = 0; i < len; i++) { arr[i] = new TreeMap<>(); arr[i].put(0, 0); }
    }
    public void set(int i, int v) { arr[i].put(snapId, v); }
    public int snap() { return snapId++; }
    public int get(int i, int s) { return arr[i].floorEntry(s).getValue(); }
}

Approach 3

Level III: List of Lists (Binary Search Optimization)

Intuition

Each index stores a list of (snap_id, value) pairs. When get(index, snap_id) is called, perform a binary search (lower bound) on the list to find the value at or before that snap_id.

⏱ Set: O(1), Snap: O(1), Get: O(log S).💾 O(N + U) where U is number of set() calls.

java

class SnapshotArray {
    List<int[]>[] arr;
    int snapId = 0;
    public SnapshotArray(int length) {
        arr = new List[length];
        for (int i = 0; i < length; i++) {
            arr[i] = new ArrayList<>(); arr[i].add(new int[]{0, 0});
        }
    }
    public void set(int index, int val) {
        int[] last = arr[index].get(arr[index].size() - 1);
        if (last[0] == snapId) last[1] = val;
        else arr[index].add(new int[]{snapId, val});
    }
    public int snap() { return snapId++; }
    public int get(int index, int snap_id) {
        List<int[]> list = arr[index];
        int l = 0, r = list.size() - 1, res = 0;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (list.get(mid)[0] <= snap_id) { res = list.get(mid)[1]; l = mid + 1; }
            else r = mid - 1;
        }
        return res;
    }
}

← Previous QuestionRange Sum Query 2D - Mutable

Next Question →Design Bounded Blocking Queue

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.