Versioned Integer Array with Snapshots and Point-in-Time Reads
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
Build a fixed-length array of integers that remembers its history. Every element starts at 0. You can change elements, take numbered snapshots of the whole array, and later ask what value any element had at the moment a given snapshot was taken.
Because the grader calls a single function, the operations are supplied as a list and processed in order.
### Function Signature
```python
def run_snapshot_array(length: int, ops: List[str], args: List[List[int]]) -> List[int]:
```
### Rules
- `ops[i]` names the i-th operation and `args[i]` holds its arguments:
- `"set"` with `args[i] = [index, value]` assigns `value` to position `index` of the live (current) array. It produces no output.
- `"snap"` with `args[i] = []` records a snapshot of the live array and outputs its snapshot id. Ids count up from 0: the first snapshot is 0, the second is 1, and so on.
- `"get"` with `args[i] = [index, snap_id]` outputs the value that position `index` held when snapshot `snap_id` was taken.
- A snapshot reflects every `"set"` that came before it and none that came after it. If an index is set several times between two snapshots, the later snapshot sees only the last of those values.
- A position that was never set before a snapshot reads as 0 in that snapshot.
- Return a single list holding the outputs of every `"snap"` and every `"get"`, in the order the operations appear. The result is fully determined by the input.
### Constraints
- `1 <= length <= 5 * 10^4`
- `1 <= len(ops) == len(args) <= 5 * 10^4`
- Each `ops[i]` is one of `"set"`, `"snap"`, `"get"`.
- For `"set"`: `0 <= index < length` and `0 <= value <= 10^9`.
- For `"get"`: `0 <= index < length` and `0 <= snap_id < s`, where `s` is the number of `"snap"` operations that appear before this `"get"`.
### Examples
**Example 1**
```text
Input: length = 3
ops = ["set", "snap", "set", "get"]
args = [[0, 5], [], [0, 6], [0, 0]]
Output: [0, 5]
```
Position 0 holds 5 when snapshot 0 is taken. The later change to 6 does not affect snapshot 0.
**Example 2**
```text
Input: length = 2
ops = ["snap", "snap", "get", "set", "get", "snap", "get", "get"]
args = [[], [], [1, 1], [1, 4], [1, 1], [], [1, 2], [0, 2]]
Output: [0, 1, 0, 0, 2, 4, 0]
```
Snapshots 0 and 1 are taken before any change, so position 1 reads 0 in snapshot 1 both before and after it is set to 4. Snapshot 2 sees the 4, and position 0 was never set.
**Example 3**
```text
Input: length = 1
ops = ["set", "set", "snap", "set", "get"]
args = [[0, 3], [0, 7], [], [0, 9], [0, 0]]
Output: [0, 7]
```
Only the last value set before snapshot 0 counts, and the set to 9 happens after it.
Overview: A coding problem about a fixed-length integer array that supports point updates, numbered snapshots of the whole array, and reads of any position as of an earlier snapshot, processed as a list of operations. It tests designing a versioned data structure that stays fast and memory-efficient when snapshots are frequent.
