最新Facebook跪经

今天下午刚刚面完，遇到了一个国人小姐姐，看到地里最近的店面很多都是dfs，结果轮到自己考了一个SnapshotArray...
话不多说，上题

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

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

我一开始用的是hashmap，记录每个snapid和对应的array，但面试要求snap()用O(1)的时间。经过提示，应该利用tuple记录每个值和对应的snapid，类似initialize的时候(-1, 0), (-1, 0), (-1, 0)，然后比如call set(0, 6)时直接将array更新为(0, 6), (-1, 0), (-1, 0)，get(0, 0)直接return 6。对于snap()可以单独用一个variable记录call的次数。有点儿没搞懂这种方法如果类似前面例子set后是get(-1, 0)怎么办。

最后，求大米呀～




补充内容 (2019-9-24 07:25):
看到leetcode的discuss板块，一个google的onsite帖子和这道题有点儿类似：
https://leetcode.com/discuss/int ... r-Snapshottable-Map

每个index维护一个存二元组的列表，按照snap顺序排列
snap每次让当前snap cnt加一O(1)
set根据当前snap cnt存入新的二元组O(1)
get二分找到给定小于等于snap cnt的最晚插入的二元组O(logn)
大概这样？

xymiku 发表于 2019-9-20 16:27
每个index维护一个存二元组的列表，按照snap顺序排列
snap每次让当前snap cnt加一O(1)
set根据当前snap c ...

可是每次set()之后都没有存之前的那个值，如果get()想找之前的那个值该怎么办呢？

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

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

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

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

•     HashMap<Integer, TreeMap<Integer, Integer>> map = new HashMap<>();
  

lz出结果了？

List<TreeMap<Integer, Integer>> res
res.get(index).floorEntry(snapId).getValue()

我想读个书 发表于 2019-9-21 16:06
lz出结果了？

是的，周四面的，周五收到拒信

楼主什么时候投的？已经很厉害啦 看到的少有的master 简历过的