狗家onsite面经

paavo

恭喜！楼主是PhD吗

actionlee

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

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

actionlee

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

markpen

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

actionlee

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

就是这样。紫薯紫薯。

rhwfyf

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

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

actionlee

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

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

rhwfyf

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

actionlee

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

是的，就是这样的。

blactangeri

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

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