狗家onsite面经

恭喜！楼主是PhD吗

paavo 发表于 2018-4-8 05:41
恭喜！楼主是PhD吗

是的，phd。总算快毕业了。

idatascience 发表于 2018-4-8 05:30
楼主不好意思啊，我等级太低了，每次只能加3升，只好给你两篇帖子分别加分了。厚着脸皮再问一下：可不可以 ...

其实就是一个2维的map。
c++里是map<int(row), map<int(col), int(val)>>。map在c++里的实现是红黑树，平衡二叉树的一种。
然后给定一个矩形区域(left, top, right, bottom)，你可以在row里调用map.lower_bound(left)，这样你就找到了行要开始遍历的地方。接下来在每个row里，你有另外一个map，同样去找到col开始的地方就可以了。

股票那题是不是用两个map，维持 prices 和 time stamps, 这样的话更新操作是O(lg n) ， 查询操作是O(1)。有更快的方法么？

markpen 发表于 2018-4-8 07:23
股票那题是不是用两个map，维持 prices 和 time stamps, 这样的话更新操作是O(lg n) ， 查询操作是O(1)。有 ...

就是这样。紫薯紫薯。

actionlee 发表于 2018-4-8 07:28
就是这样。紫薯紫薯。

题意不太清楚，如果只有一支股票，stream in 的都是<timestamp, price>这样的pair，那么维护max/min，只用2个变量不是就够了吗？ 为什么还需要2个map?

rhwfyf 发表于 2018-4-8 07:36
题意不太清楚，如果只有一支股票，stream in 的都是这样的pair，那么维护max/min，只用2个变量不是就够了 ...

因为同一个timestamp会有好几个price，以最近一个为准。所以你是要修改value的。

actionlee 发表于 2018-4-8 07:39
因为同一个timestamp会有好几个price，以最近一个为准。所以你是要修改value的。

所以map1, key是timestamp, value是price。map2, key是price, value是timestamp。
找最大最小的价格，就是在map2中找最大最小key。
找最近的价格，就是在map1中找最大key对应的price？

rhwfyf 发表于 2018-4-8 07:49
所以map1, key是timestamp, value是price。map2, key是price, value是timestamp。
找最大最小的价格，就 ...

是的，就是这样的。

actionlee 发表于 2018-4-8 08:06
是的，就是这样的。

这样的话怎么做的查询O(1)的？