Snapshot - Google

https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58

实现三个functions， get, set, take snapshots。其实就是一个长度为N的Array。Set可以设置Index i的值，每次take snapshot， version + 1，并且记录下当前version下 Array里面的值。然后get方法可以得到某一个Version下，每一个Index的Array的值。就是非常Naive的方法，在Chromebook上写完了。写完之后有一个变量名Typo被指出。口头跑了Test case。Follow up 时空复杂度，并且要节省空间。

举例

初始 100001

take a snapshot 返回sid 1

改变成 100201.

take a snapshot 返回sid 2

这时lookup get（3，1）（ get(index, snapshotID)）应该返回0而不是2，这是version control的原理可是关键在怎么存最省空间

可以参考视频压缩，每隔若干帧保存一份完整的图像，期间只保存delta。重建图像的时候，从最近的full snapshot开始，然后apply 每个version的delta

类似LC 981？ - Google Snap （高频）

第二轮是面经高频题，Google Snapshot

就是一个array，然后这个array有不同的版本数，然后有不同的函数，比如set(int index, int val)，get(int index, int version), snapshot()。比如说我先

set(1,1)，set(0,0)，set(2,2)，这样我有一个[0,1,2]，然后snapshot()之后系统里会记住version 1的array是[0,1,2]，然后set(1,0)，array就变成[0,0,2]，这个时候如果get(1,1)得到的是1，但get(1,2)得到的是0。

思路：

1. 模拟过程，用map存下snapshot即可,主要要和面试官交流得到各种异常的处理方式

包括数组长度是否固定，idx是否一定合法，version不存在是返回最近的还是抛出异常等等

2. hash map嵌套treemap，牺牲了一些时间，但是如果一些idx在某些version一直没用过可以节省空间

code：

Provider: null

class Snapshot {
int version = 1;
int length;
Map<Integer, TreeMap<Integer, Integer>> map = new HashMap<>();
public Snapshot(int length) {
this.length = length;
for(int i = 0 ; i < length ; i++) {
map.put(i, new TreeMap<>());
}
}
public void set(int idx, int val) {
// sanity check and exception process
map.get(idx).put(version, val);
}
public int get(int idx, int version) {
// sanity check and exception process
Integer key = map.get(idx).floorKey(version);
if(key == null) return Integer.MIN_VALUE;
return map.get(idx).get(key);
}
public void snapshot() {
version++;
}
}

假如我在[0,0,2]再叫snapshot(), 那[0,1,2] 的reference 就會不見了?

这里用了treeMap。题意中是否要求如果输入了不存在的版本号，那么就返回这个版本号的lower_bound？如果没有这个要求那么treeMap是能用hashMap取代的