亚麻 onsite

论坛匿名用户 发表于 2019/05/29 13:57:01


kindle组，你是面react native那个组吗？

好像是的，我是做app的，但是这个职位好像full stack. 感觉做app 亚麻都不问相关知识的。

littlechen32 发表于 2019/05/29 15:24:00
问下4题使用treemap做的，按照freq排序还是 普通map + PriorityQueue ？

他给的方法是sliding window，不过我没想出来，我是用map+heap做的，treemap提了一下但是没有实现

补充内容 (2019-5-29 23:02):
time box用sliding window，抱歉没说清楚

论坛匿名用户 发表于 2019-5-29 23:01
他给的方法是sliding window，不过我没想出来，我是用map+heap做的，treemap提了一下但是没有实现

补充 ...

请问sliding windows 在这种情况下如何实现呢？ 谢谢 想半天没想出来。

补充内容 (2019-6-7 20:05):
要把所有元素按照 时间排序么？ 这样动态排序的话，用的是什么类型的数据结构呢。因为这个是个streaming的数据啊

build heap不是nlgn吗， call n 次lgn 啊

Wu_kong 发表于 2019-6-7 21:49
build heap不是nlgn吗， call n 次lgn 啊

资料贴在这里：https://www.geeksforgeeks.org/time-complexity-of-building-a-heap/
也可以看看网上别的讲解。我的理解是build heap和heapify不太一样，具体计算可以看一下资料。

ninepig 发表于 2019-6-7 20:02
请问sliding windows 在这种情况下如何实现呢？ 谢谢 想半天没想出来。

补充内容 (2019-6-7 20:05):

肯定还是需要一个队列来存储stream的，比如每进来一个数据就放在队尾，这样生成的队列是按照timestamp排序的，用map + heap就可以把所有的purchase进行排序。但是，有time-box的时候就需要选定特定的时间，比如他会要求返回一个小时内的purchase的排序结果，按照常规做法就是在stream里面把一个小时内的数据filter出来，这样做的时间复杂度不好，因为如果这样的query很多，不断的添加新的data进入队列，每次都要filter一个小时内的数据，所以就用sliding window，添加新的数据时超过一个小时就移动一下window，保证window内的数据是在一个小时以内的。这样只需要处理window两侧的数据，不需要把所有的数据过一遍filter，时间复杂度就好很多了。当然map + heap还是需要的。我不太会讲题，可能写的不太清楚，不过也没找到网上的讲解。。。

论坛匿名用户 发表于 2019-6-8 00:00
肯定还是需要一个队列来存储stream的，比如每进来一个数据就放在队尾，这样生成的队列是按照timestamp排 ...

哦哦 太谢谢，这样我就知道了。因为我一开始没懂是按照时间顺序进来的~

lz你是mobile engineer. 感觉goole search这题不太像OOD啊。。。。倒是像distributed system 设计。。。。。能稍微展开讲讲这题的要求么？

楼主timeline是怎么样的啊

wliu051234 发表于 2019/06/11 09:13:21
楼主timeline是怎么样的啊

我的timeline没太大意义，基本上是hm等我准备好面试的，面完马上就发offer了