狗家onsite面经

blactangeri 发表于 2018-4-8 13:15
这样的话怎么做的查询O(1)的？

你访问的就是map.begin() /map.rbegin().
这些都是常数时间。
不过update要log n。

谢谢楼主的分享！没有System Design吗？

actionlee 发表于 2018-4-7 20:42
这道题和leetcode上的Number of Corner Rectangle是类似的做法。把所有的点按照y坐标存到一个hash表里， ...

lz or其他人能简单说下1.5的方法么。。多谢了！

yunliang2014 发表于 2018-4-8 14:03
谢谢楼主的分享！没有System Design吗？

没有的，new grad纯coding。

不是特别明白，这里的online stream这个input的type是string么？怎么分割价格和timestamp呢？又如何把timestamp从string转换为time呢？

actionlee 发表于 2018-4-8 14:01
你访问的就是map.begin() /map.rbegin().
这些都是常数时间。
不过update要log n。

请问你price-》time的map，如果有多个同样的price怎么办

blactangeri 发表于 2018-4-9 08:08
请问你price-》time的map，如果有多个同样的price怎么办

你可以再在每个price下面弄个hash表，或者简单点，用pair为key来表示price和time，

idatascience 发表于 2018-4-9 04:43
不是特别明白，这里的online stream这个input的type是string么？怎么分割价格和timestamp呢？又如何把times ...

online的一个stream，每个stream的element是pair<long, int>，第一个是时间，第二个是price。

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

我觉得map2改成一个multiset<price>比较好
如果输入的timestamp是乱序的，那可能存在这样的一种输入：
t=3, p=1000 #1000是最大price，map2[1000] = 3
....中间经历一些别的输入
t=3, p=5 # 时刻3的价格修订为5，map2[5]=3，实际上1000这个价格已经失效了，但是此时取map2的最大值还会取到1000

用multiset的话，每次输入的(t, p)，如果t在map1中存在，说明发生价格修订，从multiset<price>中找到一个map1[t]并删除，然后insert新的p

actionlee 发表于 2018-4-9 12:22
online的一个stream，每个stream的element是pair，第一个是时间，第二个是price。

汗，不好意思，继续叨扰问一下，这个long type的time不需要再转换成time的格式吧？直接拿来用就可以了吧？这道题应该不考任何的data type吧？（实在是问太多了，楼主好人，一直在耐心回答，只能给楼主加米，表示感谢了）