/**
* 1146. Snapshot Array
* Implement a SnapshotArray that supports the following interface:
*
* SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.
* void set(index, val) sets the element at the given index to be equal to val.
* int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
* int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id
*
* Example 1:
*
* Input: [“SnapshotArray”,”set”,”snap”,”set”,”get”]
* [[3],[0,5],[],[0,6],[0,0]]
* Output: [null,null,0,null,5]
* Explanation:
* SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
* snapshotArr.set(0,5); // Set array[0] = 5
* snapshotArr.snap(); // Take a snapshot, return snap_id = 0
* snapshotArr.set(0,6);
* snapshotArr.get(0,0); // Get the value of array[0] with snap_id = 0, return 5
*/
Please see the solution on github at: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/SnapshotArray.java
This is a simple question but is interesting in that it has several practical use cases.
Observation: We want to update array items with a concept similar to a transaction log in databse such that we can view the previous version of the values if needed. The concept is simple, store the original values in array. Add updates to an overlap map. Create a new map after each snap. Reason to store items in a map is that the original indexes may be very wide while overlays maybe only for a few indexes, so don’t need to create a new array per snap. Even a generic map is a fairly memory intensive object, depending on the number of items in the array, could be more efficient to use an overlay data structure similar to a linked list.
Logic:
- Initially update elements in the array
- Per snap, increment a snap id
- Get a map based on the snap id and update values in the map
- For read start from the map referring to the snap index and walk back to starting array to find the latest value for that index
Here is the code:
int[] snapShotArray;
int snapShotId = -1;
Map<Integer, Map<Integer, Integer>> snapShotMap = new HashMap<>();
public SnapshotArray(int length) {
snapShotArray = new int[length];
}
public void set(int index, int val) {
if (snapShotId == -1) {
snapShotArray[index] = val;
} else {
Map<Integer, Integer> snapMap = snapShotMap.computeIfAbsent(snapShotId, (l) -> new HashMap<>());
snapMap.put(index, val);
}
}
public int snap() {
snapShotId++;
return snapShotId;
}
public int get(int index, int snap_id) {
snap_id--;
while (snap_id > -2) {
if (snap_id == -1) {
return snapShotArray[index];
} else {
Map<Integer, Integer> map = snapShotMap.get(snap_id);
if (null != map) {
Integer val = map.get(index);
if (val != null) {
return val;
}
}
}
snap_id--;
}
return -1;
}