Versioned Array Snapshots
Implement a versioned array supporting snapshots. You are given two arrays operations and args describing a sequence of calls. Return an array outputs where outputs[i] is the return value of operations[i].
Operations:
SnapshotArray— constructor,args[i] = [length], initialize array of given length filled with0, returnsnull.set—args[i] = [index, val], setsarr[index] = val, returnsnull.snap—args[i] = [], takes a snapshot, returns currentsnap_id(starting at0and incrementing by one persnap).get—args[i] = [index, snap_id], returns value atindexat the time snapshotsnap_idwas taken.
snap() increments the snapshot id after capturing the current state. Every get references a snap_id that already exists.
Your function solve(operations, args) must dispatch these calls and collect outputs, using null for void returns.
Examples
Input: [["SnapshotArray","set","snap","set","get"],[[3],[0,5],[],[0,6],[0,0]]]
Output: [null,null,0,null,5]
Input: [["SnapshotArray","snap","get","set","snap","get","get"],[[1],[],[0,0],[0,10],[],[0,0],[0,1]]]
Output: [null,0,0,null,1,0,10]
Hints
Naive copy on `snap` is correct but copies `O(length)` per snapshot; use per-index history with binary search for efficiency.
For each index store list of `[snap_id, value]` pairs; `set` appends or overwrites entry for current `snap_id`.
`get(index, snap_id)` binary-searches that index history for greatest `snap_id <= requested`.
Related Problems
Versioned Array Snapshots
Implement a versioned array supporting snapshots. You are given two arrays `operations` and `args` describing a sequence of calls. Return an array `outputs` where `outputs[i]` is the return value of `operations[i]`.