Build an array that can remember its past. You can save a snapshot of the array and read old values later.
Write a class SnapshotArray with these methods:
SnapshotArray(length): create an array with length places. Every place starts with the value 0.set(index, val): put val in the place index.snap(): save a copy of the array as it is now, and return the snapshot id. The first snapshot has id 0, the next one has id 1, and so on.get(index, snap_id): return the value that was in place index when snapshot snap_id was taken.
Examples
Example 1:
Input
["SnapshotArray", "set", "set", "snap", "set", "snap", "get", "get", "get", "get"]
[[4], [1, 7], [2, 3], [], [1, 9], [], [1, 0], [1, 1], [2, 1], [3, 0]]
Output
[null, null, null, 0, null, 1, 7, 9, 3, 0]
Explanation
The array has 4 places, all 0. Set place 1 to 7 and place 2 to 3.
snap() saves the array and returns 0. Then place 1 is set to 9, and the next snap() returns 1.
get(1, 0) returns 7, the old value. get(1, 1) returns 9.
get(2, 1) returns 3. get(3, 0) returns 0 because place 3 was never changed.