snapshot高频面经题求问~

刚在地里看到google的面经帖子，有一道snapshot的题目貌似很多人遇上了。想集思广益，看能不能想到更好的方法。

原贴：
第一轮：烙印校友。上来就做题。题目是Google

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

Version相同Index相同的值不保存，仅保存改变的值。写了代码后，在口头跑Case时，发现小Bug，并立马改正。

比较naive的做法应该就是用一个vector<vector<pair<int, int>>>，pair.first表示的version，pair.second表示的是value
这样的话set可以做到O(1)，takeSnapshot是O(n)，因为take snapshot的时候可能已经累计了很多set了，而且需要更新每个index处的version号
而get得话，应该是O(nlgn)的，因为每个位置都需要binary search寻找一个比指定version号低的value

bdhmwzfa 发表于 2018-12-11 10:16
比较naive的做法应该就是用一个vector，pair.first表示的version，pair.second表示的是value
这样的话set ...

你好！请问一下，为什么take snapshot 需要O（n）呢？如果每次调用set的时候，都把(version No., value)加到index处的vector，那takesnapshot还需要其他什么操作呢？我的理解是只要把version No.累加1就可以了，那么之后的set都会用新的version No.？求指正～

节省空间的话，设计一个structure包含version和value, 然后array每个index放list<structure>?

bdhmwzfa 发表于 2018-12-11 10:16
比较naive的做法应该就是用一个vector，pair.first表示的version，pair.second表示的是value
这样的话set ...

跟我想的很像 我会用 hashmap<index, treemap<update_version, update value> 这样因该是 o(1) set , o(n) take snapshot, get o(nlogn) 有点像是sparse vector 的概念

H4veFunC0din9 发表于 2018/12/13 01:39:08


你好！请问一下，为什么take snapshot 需要O（n）呢？如果每次调用set的时候，都把(version No., value)加到index处的vector，那takesnapshot还...

你这个做法可以，但可能会被指出空间效率不高，因为很可能累积许多的set才会有一个take snapshot，所以没必要每次都生成一个新version。传统关系型数据库MVCC的原理是每次写都自动生成version和snapshot，但是这里既然给了snapshot函数，显然只关心特定节点的值。

顶一下帖子，借楼看答案

say543 发表于 2018-12-11 15:48
跟我想的很像 我会用 hashmap

想请问一下，这样的空间复杂度是O(m*n)， m是数组长度，n是最大的版本号，有更低空间复杂度的方法吗

say543 发表于 2018-12-11 15:48
跟我想的很像 我会用 hashmap

求教这get为啥是O（nlogn）。。。

请问能解释清楚输入是什么东西吗？不同的version是什么意思？