狗狗加面

2 min 前刚面完。。。加面先聊了一通research相关的。

要求实现一个计时的 map 和其两个功能，set和get：
set(key, val, time)插入val和time for key
get(key,time)

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

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

st based on time，这样get是logN，不过set也是logN了。
然后就聊天，聊google的开放文化
希望能有好结果吧。。。也祝福各位

FightForTomo 发表于 2017-7-14 01:58
那就建个类放HashMap里呗。

补充内容 (2017-7-14 02:02):

嗯 我是这么做的

unordered_map<key_t, map<timestamp_t, value_t>>可以做吧。。。
觉得这道题有点像BigTable的data model

这题简单思路的话用defaultdict(list)没问题啊
set O（1） self.dict[key].append((time,val))
get O（lgn）用bs找小于get_time的最大time, 要是get_time < self.dict[key][0][0] 说明没有更小的返回None， 不然返回bs右边界对应的val不就行了
不知道理解的对不对。。。

如果用sorted list 的话，不管是ArrayList还是linkedList， set都应该是o(n), 而不是logN。 我觉得应该用TreeMap

watercup 发表于 2017-7-8 04:20
如果用sorted list 的话，不管是ArrayList还是linkedList， set都应该是o(n), 而不是logN。 我觉得应该用Tr ...

set的时间应该必是递增的吧 那样的话就是O(1)

watercup 发表于 2017-7-8 04:20
如果用sorted list 的话，不管是ArrayList还是linkedList， set都应该是o(n), 而不是logN。 我觉得应该用Tr ...

对对用heap之类的应该是（猛拍大腿

rgc588 发表于 2017-7-8 04:37
set的时间应该必是递增的吧 那样的话就是O(1)

我一开始也以为是，问了说不一定

lliu25 发表于 2017-7-8 05:04
对对用heap之类的应该是（猛拍大腿

又想了一下应该建一个bst之类的…

lliu25 发表于 2017-7-8 05:28
又想了一下应该建一个bst之类的…

TreeSet就是BST

问下楼主 你是被 interview committee review（邮件里有说） 之后再加面的吗 还是直接说你要加面的啊？ 谢谢

yi904835116 发表于 2017-7-11 19:47
问下楼主 你是被 interview committee review（邮件里有说） 之后再加面的吗 还是直接说你要加面的啊？ 谢 ...

被通知再面一轮的

yi904835116 发表于 2017-7-11 19:47
问下楼主 你是被 interview committee review（邮件里有说） 之后再加面的吗 还是直接说你要加面的啊？ 谢 ...

不好意思哈我等级还不够pm，是review committee request加面的