Snapshot Array

Snapshot Array

What is this problem about?

"Snapshot Array" is a system design-oriented coding problem that asks you to implement a data structure that supports three main operations: setting a value at a specific index, taking a "snapshot" of the current array state, and retrieving the value of an index at a specific snapshot ID.

The catch is efficiency. Taking a snapshot should not involve copying the entire array, as that would be extremely slow and memory-intensive ($O(N)$ per snapshot). Instead, the challenge is to store only the changes (deltas) and retrieve them quickly even after thousands of snapshots have been taken.

Why is this asked in interviews?

Companies like Databricks, Apple, and Google use this problem to test a candidate's ability to balance time and space complexity. It requires moving beyond simple arrays and thinking about how to version data. It tests knowledge of Hash Tables and Binary Search, and more importantly, it assesses how you can combine these tools to create a custom, high-performance data structure. It mimics real-world scenarios like version control systems or database snapshots.

Algorithmic pattern used

The optimal algorithmic pattern involves using a list of lists or a list of dictionaries. Each index in the main array stores a history of its changes. For example, array[index] could be a list of pairs: [(snapshot_id, value)]. When set(index, val) is called, you record the change for the current snapshot. When get(index, snap_id) is called, you perform a Binary Search on the history for that specific index to find the value that was present at or before the requested snap_id.

Example explanation

1. Initialize an array of size 3. history = [[(0,0)], [(0,0)], [(0,0)]], snap_id = 0.
2. set(0, 5): history[0] becomes [(0,5)].
3. snap(): returns 0. Increment snap_id to 1.
4. set(0, 6): history[0] becomes [(0,5), (1,6)].
5. get(0, 0): Binary search in history[0] for snap_id 0. Result: 5.
6. get(0, 1): Binary search in history[0] for snap_id 1. Result: 6.

Common mistakes candidates make

A major pitfall is trying to copy the entire array during the snap() operation, which leads to a Time Limit Exceeded error. Another mistake is forgetting that the get operation must return the value at the most recent snapshot that is less than or equal to the requested ID, not necessarily the exact ID. Some candidates also struggle with the binary search logic, specifically handling the case where an index was never modified during a particular snapshot.

Interview preparation tip

Mastering the "Snapshot Array interview question" requires being comfortable with "Binary Search on a list of pairs." This is a common pattern for versioning and time-series data problems. Practice implementing bisect_right or a similar custom binary search that finds the largest element less than or equal to a target. Also, think about the space complexity: we only store $O(\text{number of sets})$ space, which is much better than $O(\text{snapshots} \times \text{array length})$.