Problem Explanation

The problem is about implementing a custom array-like data structure named "SnapshotArray" with the following features:

• It is initialized with a given length and initially, each element equals 0.
• A "set" method sets the value at the given index in the array.
• A "snap" method takes a snapshot of the current state of the array and returns a snapshot_id, which is essentially a count of how many times the snap method was called minus 1.
• A "get" method retrieves the value at a certain index in a particular snapshot, identified by its snap_id.

We are also given some constraints:

• The maximum length of the array is 50000 and maximum number of calls to set, snap, get would also be 50000.
• For method set, value to be set is between 0 and 1 billion
• The index parameter in set and get methods is within the array length
• snap_id in the get method will be less than the total number of calls to the snap method.

The main challenge in this problem is to implement the snap method efficiently, as we could not copy the entire array every time we take a snapshot due to the large maximum array length. The solution to this problem involves using the concept of delayed-write and taking advantage of the fact that our array is sparse (most of the elements are zeros unless we change them by calling the set method).

Solution Explanation

We could represent our SnapshotArray by a list of list of pairs, where each list of pairs represents an index position in the array. In each list of pairs, each pair contains a snapshot id and the value set at that snapshot. For example, if we have a SnapshotArray of length 5 and we set index 3 to be 7 at snap_id 2, then our data would be like: [[],[],[],[(2,7)],[],[]].

When we call the set method, we first check if the latest snapshot (the last element in the list of pairs at the given index) has the same id as the current snap_id. If it is, then we update the value in the latest pair, otherwise we add a new pair with the current snap_id and the given value.

The snap method simply returns the current snap_id and increases the snap_id by 1.

For the get method, we use binary search to find the largest snap_id that is less or equal to the given snap_id in the list of pairs at the given index.

Let's see an example of how this solution works:

Example

Say we have the following sequence of operations:

1
2
3snapshotArray = SnapshotArray(5)
4snapshotArray.set(3,7)
5snapshotArray.snap()
6snapshotArray.set(0,5)
7snapshotArray.snap()
8snapshotArray.get(3,0)
9snapshotArray.get(0,1)

After initializing SnapshotArray:

1
2
3snap_id = 0
4snapshots = [[],[],[],[],[]]

After calling set(3,7):

1
2
3snap_id = 0
4snapshots = [[],[],[],[(0,7)],[],[]]

After calling snap():

1
2
3snap_id = 1
4snapshots = [[],[],[],[(0,7)],[],[]]

After calling set(0,5):

1
2
3snap_id = 1
4snapshots = [[(1,5)],[],[],[(0,7)],[],[]]

After calling snap():

1
2
3snap_id = 2
4snapshots = [[(1,5)],[],[],[(0,7)],[],[]]

When calling get(3,0), we need to find the largest snap_id in the third list that is less or equal to 0, which is 0. Therefore, the return value is 7.

When calling get(0,1), we need to find the largest snap_id in the first list that is less or equal to 1, which is 1. Therefore, the return value is 5.

Solution in Python

1
2python
3class SnapshotArray(object):
4
5    def __init__(self, length):
6        self.snap_id = 0
7        self.array = [[(0, 0)] for _ in range(length)]
8
9    def set(self, index, val):        
10        if self.array[index][-1][0] == self.snap_id:
11            self.array[index][-1] = (self.snap_id, val)
12        else:
13            self.array[index].append((self.snap_id, val))
14
15    def snap(self):
16        self.snap_id += 1
17        return self.snap_id - 1
18
19    def get(self, index, snap_id):
20        i = len(self.array[index]) - 1
21        while i > 0 and self.array[index][i][0] > snap_id:
22            i -= 1
23        return self.array[index][i][1]

Solution in Java

1
2java
3class SnapshotArray {
4    
5    private int snapId;
6    private Map<Integer, TreeMap<Integer, Integer>> array;
7
8    public SnapshotArray(int length) {
9        this.snapId = 0;
10        this.array = new HashMap<>();
11        for (int i = 0; i < length; i++) {
12            this.array.put(i, new TreeMap<>(){{put(0, 0);}});
13        }
14    }
15
16    public void set(int index, int val) {
17        this.array.get(index).put(this.snapId, val);
18    }
19
20    public int snap() {
21        return this.snapId++;
22    }
23
24    public int get(int index, int snapId) {
25        return this.array.get(index).floorEntry(snapId).getValue();
26    }
27}

Solution in JavaScript

1
2javascript
3class SnapshotArray {
4    
5    constructor(length) {
6        this.snapId = 0;
7        this.array = Array.from({ length }, () => [[0, 0]]);
8    }
9
10    set(index, val) {
11        const pairs = this.array[index];
12        if (pairs[pairs.length - 1][0] === this.snapId)
13            pairs[pairs.length - 1][1] = val;
14        else
15            pairs.push([this.snapId, val]);
16    }
17
18    snap() {
19        return this.snapId++;
20    }
21
22    get(index, snapId) {
23        const pairs = this.array[index];
24        let left = 0, right = pairs.length;
25        while (left < right)
26            {
27                const mid = left + Math.floor((right - left) / 2);
28                if (pairs[mid][0] <= snapId)
29                    left = mid + 1;
30                else
31                    right = mid;
32            }
33        return pairs[right - 1][1];
34    }
35}

Solution in C++

1
2c++
3class SnapshotArray {
4public:
5    SnapshotArray(int length): snapshots(length), snap_id(0) {
6        for (auto& snapshot : snapshots)
7            snapshot.emplace_back(make_pair(0, 0));
8    }
9    
10    void set(int index, int val) {
11        pair<int, int>& lastSnapshot = snapshots[index].back();
12        if (snap_id == lastSnapshot.first)
13            lastSnapshot.second = val;
14        else
15            snapshots[index].push_back(make_pair(snap_id, val));
16    }
17    
18    int snap() {
19        return snap_id++;
20    }
21    
22    int get(int index, int snap_id) {
23        const vector<pair<int, int> >& snapshot = snapshots[index];
24        auto it = lower_bound(snapshot.begin(), snapshot.end(), make_pair(snap_id + 1, 0));
25        return prev(it)->second;
26    }
27    
28private:
29    vector<vector<pair<int, int> > > snapshots;  // Snapshots for each index
30    int snap_id;  // Current snapshot id
31};

Solution in C#

1
2csharp
3public class SnapshotArray {
4
5    private int snapId;
6    private List<Dictionary<int, int>> list;
7
8    public SnapshotArray(int length) {
9        this.snapId = 0;
10        this.list = new List<Dictionary<int, int>>();
11        for (int i = 0; i < length; i++)
12        {
13            this.list.Add(new Dictionary<int, int>() { { 0, 0 } });
14        }
15    }
16
17    public void Set(int index, int val) {
18        if (!this.list[index].ContainsKey(this.snapId))
19            this.list[index][this.snapId] = val;
20        else
21            this.list[index].Add(this.snapId, val);
22    }
23
24    public int Snap() {
25        return this.snapId++;
26    }
27
28    public int Get(int index, int snapId) {
29        while (!this.list[index].ContainsKey(snapId))
30            snapId--;
31        return this.list[index][snapId];
32    }
33}

Summary

In conclusion, the problem demanded an efficient implementation of an array-like data structure capable of taking snapshots of its various states. By using the "delayed-write" principle and the fact that our array is sparse, we can implement a data structure with memory-efficient snapshots.

In all given solutions, we maintained a list of pairs, where each pair represents a pair of a snapshot id and the corresponding array value at that snapshot. We took advantage of binary search in the get method to find the query result efficiently.

These multiple solutions in Python, Java, JavaScript, C++ and C#, demonstrate that the similar logic can be molded to suit and work with different languages. The choice of a language for implementation can based on various factor such as the supporting infrastructure, team's familiarity with the language and problem specific requirements like performance and memory usage etc.

It can be a great start to practice more problems related to custom or specialized data structure, as it is a good way to enhance absolutely essential programming skills like problem solving, logical thinking and attention to details.