Snapshottable List - Google Top Interview Questions

                        Solution in C++ :

class SnapshottableList {
    vector<map<int, int>> v;  // v[i] --> snap_id: val
    int snaps = -1;

    public:
    SnapshottableList(int size) {
        v.resize(size);
        for (auto &x : v) {
            x[-1] = 0;
        }
    }

    void set(int idx, int val) {
        v[idx][snaps] = val;
    }

    int snapshot() {
        snaps++;
        return snaps;
    }

    int get(int idx, int snapshotId) {
        return (--(v[idx].lower_bound(snapshotId)))->second;
    }
};
                    

                        Solution in Java :

import java.util.*;

class SnapshottableList {
    TreeMap<Integer, Integer>[] values;
    int snapshotId = 0;
    public SnapshottableList(int size) {
        values = new TreeMap[size];
        for (int i = 0; i < values.length; i++) {
            values[i] = new TreeMap<>();
        }
    }

    public void set(int idx, int val) {
        values[idx].put(snapshotId, val);
    }

    public int snapshot() {
        int ss = snapshotId;
        snapshotId++;
        return ss;
    }

    public int get(int idx, int snapshotId) {
        Map.Entry<Integer, Integer> entry = values[idx].floorEntry(snapshotId);
        return entry == null ? 0 : entry.getValue();
    }
}
                    

                        Solution in Python : 
                            
class SnapshottableList:
    def __init__(self, size):
        # for each index, store a list of (snapshot_id, val)
        self.slist = [[] for _ in range(size)]
        self.current_snapshot = 0

    def set(self, idx, val):
        l = self.slist[idx]
        if l:
            # if we already have a value for the current snapshot, overwrite it
            if l[-1][0] == self.current_snapshot:
                l[-1] = (self.current_snapshot, val)
                return
            # if the existing value is the same as the new value, no need to append a new value
            if l[-1][1] == val:
                return
        l.append((self.current_snapshot, val))

    def snapshot(self):
        res = self.current_snapshot
        self.current_snapshot += 1
        return res

    def get(self, idx, snapshotId):
        l = self.slist[idx]
        i = bisect_right(l, (snapshotId, float("inf")))
        if i == 0:
            # no snapshots <= snapshotId
            return 0
        return l[i - 1][1]