Snapshot Array

I had this on a Coinbase backend onsite where the framing was "persistent state for an idempotent ledger." The naive approach (deep-copy on every snap) is O(length) per snapshot, which kills you when length is 5 * 10^4 and snaps are 5 * 10^4. The trick is to push (snap_id, value) onto each index's history only when that index is set, and binary-search the history at get-time.

Snapshot Array

Implement a SnapshotArray that supports the following interface:

• SnapshotArray(int length) initializes an array-like data structure with length zero-initialized entries.
• void set(int index, int val) sets the element at index to be val.
• int snap() takes a snapshot of the array and returns the snap_id: the total number of times snap() was called minus 1.
• int get(int index, int snap_id) returns the value at index with the given snap_id.

Examples

Example 1:

SnapshotArray sa = new SnapshotArray(3);   // [0, 0, 0]
sa.set(0, 5);                              // [5, 0, 0]
sa.snap();                                 // returns 0; snap_id 0 captures [5, 0, 0]
sa.set(0, 6);                              // [6, 0, 0]
sa.get(0, 0);                              // returns 5 (snap_id 0)
sa.get(0, 1);                              // would error; only snap 0 exists

Example 2:

SnapshotArray sa = new SnapshotArray(2);
sa.snap();                                 // returns 0
sa.set(0, 4);
sa.snap();                                 // returns 1
sa.get(0, 0);                              // returns 0 (untouched at snap 0)
sa.get(0, 1);                              // returns 4

Constraints

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

Follow-up

Why not deep-copy on every snap()? Because deep-copy is O(length) per call and the total work explodes to O(length * snaps). The version-list trick keeps total memory in O(set_calls + length) and each get in O(log set_calls).