Leetcode: Snapshot Array

This question is asked at Google, Rubrik, Goldman Sachs, and a handful of other companies. 

They wanted me to implement a SnapShort Array that supports the following interface: 

SnapShotArray(int length) initializes array-like data structure with a length where each element is initially set to 0. 

Set sets the element at a given index to a value, snap() takes the snapshot of the array and snap_id which is the number of times we call the snap() function minus 1. Get() returns the value o an index at the time we take the snapshot

Now let's see the commands that go subsequent to this. 

Here's the Input: 

["SnapshotArray", "set", "snap", "set", "get"]

[[3], [0, 5], [], [0, 6], [0,0]]

So the first command sets the length of the snapshot array to be equal to 3. 

Second command sets array[0] = 5.

Third command takes the snap and return snap_Id to be equal to 0. 

Then it sets array[0] to equal 6, then get the value of array[0] with snap_id = 0. We return 5 at the end. 

There are 2 alternative ways we can do this: Binary Search and HashMap. 

In Binary Search, Instead of Copying the whole array, we only record the changes of Set. Instead of recording the history of the entire array, we need to record the history of each cell. So here's the Pseudocode for each method:

SnapShotArray with the length integer parameter: 

We initialize a new array of trees of length and put corresponding elements inside of the tree. 

Set Method with the Index and Value:  

Add. the value to the index of the tree. 

Snap Method: 

Increments the snap id. 

Get Method: 

Returns the TreeMap Index entry at the snap id. 

TreeMap does this in Java, but let's see what does this in C++. 

Here's the C++ class:

class SnapshotArray {

private: 

    //initialize a map filled with trees 

    map<int, map<int, int>> snaps;

    int snapId = 0; 

public: 

    //map filled with trees, every map inside will just start with 0. Set the snaps at the array index to the map.

    SnapshotArray(int length) {

        for(int i = 0; i < length; i++) {

            map<int, int> mp; 

            mp[0] = 0;

            snaps[i] = mp; 

        }

    }

    //set the map value of this array. 

    void set(int index, int val) {

        snaps[index][snapId] = val;

    }

//increment the snap id, indicating the number of times we call snap(). 

public int snap() {

    return snap_id++; 

}

    //get the value at the index and the snap id which will return second value. This is where we binary search the time point. 

    int get(int index, int snap_id) {

        auto it = snaps[index].upper_bound(snap_id); 

        it = it - 1;

        return it -> second; 

    }

};

In auto, these variables allocates memory automatically upon entry to that block and free the occupied memory upon exit from that block.

Why is the solution -1? This is because the value might be updated several times before you take another snap, and you want to retrieve the last value with the snap_id so you go to snap_id + 1 and add -1 in the final solution. We're assuming we add new elements to the front of the tree.