狗狗加面

knight0clk 发表于 2017-7-17 12:22
楼主，python没有BST library，那怎么实现？另外你说“tricky部分是，set调用多次，不一定time递增调用， ...

嗯，是的。当时比较紧张题没看清，以为就是lookup。

bearicc 发表于 2017-7-14 00:12
不错，set O(1) get O(logn)，就是不知道map of map会不会太浪费空间。

set还是lgN吧，毕竟对每个key来说要保持所有timestamp始终是排好序的

请问楼主有结果了吗？

楼主请问你是面全职还是intern？phd的intern对coding的要求和research是怎么样的呢？

jon.wang 发表于 2017-9-16 05:36
楼主请问你是面全职还是intern？phd的intern对coding的要求和research是怎么样的呢？

intern。其实差不多吧，除非去brain（猜的）

这题简单思路的话用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不就行了
不知道理解的对不对。。。

nickdgu 发表于 2017-9-18 01:19
这题简单思路的话用defaultdict(list)没问题啊
set O（1） self.dict[key].append((time,val))
get O（lg ...

主要是他好像没听说过defaultdict这个方法，我解释了一下他默认了可以用。

想用trie...key就是time的string...这样逻辑多一些，不过复杂度是constant，set也是一样