亚麻西雅图5月24号Hiring Event

谢谢楼主分享！请问第4轮是最后写了代码完全实现了minHeap吗？

user123456 发表于 2019-6-6 15:13
谢谢楼主分享！请问第4轮是最后写了代码完全实现了minHeap吗？

对啊，一开始被要求写我也很虚的，后面举了些具体的例子来做demo就写出来了，主要的就是写insert 的percolate up， pop的percolate down。

xi3047 发表于 2019-6-6 15:06
首先这个问题可以理解为一个incoming data stream， 你如果只用hashmap的话 那每次去取topID是不是要遍历 ...

lz，请问第二题，你的意思是用heap 维护 时间的排序么，如果时间一样的话，再按照出现的频率排？那他题目给定的date 应该是个frame么？

ninepig 发表于 2019/06/06 19:30:13


lz，请问第二题，你的意思是用heap 维护 时间的排序么，如果时间一样的话，再按照出现的频率排？那他题目给定的date 应该是个frame么？

Timeframe面试官给的很模糊，我当时跟面试官假设是当做一天一天来做的，方便写代码…

xi3047 发表于 2019-6-6 15:06
首先这个问题可以理解为一个incoming data stream， 你如果只用hashmap的话 那每次去取topID是不是要遍历 ...

如果只是求一个最大频率的id，那我只需要一个变量记录下当前频率最大的id，stream进来一个id以后这个id的频率加1，看一下有没有比当前最大频率的id大，如果大就替换，这样不需要heap，而且是o(1)啊

fx_xj 发表于 2019-6-6 23:22
如果只是求一个最大频率的id，那我只需要一个变量记录下当前频率最大的id，stream进来一个id以后这个id的 ...

最大频率的一个可以这样做当然没问题啊，但你不要考虑scalability的问题，如果是top 10, top K 的话 你怎么做。其实有很多方法可以和面试官讨论的

xi3047 发表于 2019-6-7 02:08
最大频率的一个可以这样做当然没问题啊，但你不要考虑scalability的问题，如果是top 10, top K 的话 你怎 ...

我前段时间就遇到了这个问题
top k的话
stream出现的元素会改变id的频率，但频率改变并不能让heap里对应的id的位置改变，如果要保持排序需要重新offer一个(id ,频率)的节点，这样heap里其实有很多相同id的duplicate。选top k 的时候也要用一个set接住heap poll出来的东西，直到有k个不同的id poll出来，是这个思路吗？

fx_xj 发表于 2019-6-7 03:05
我前段时间就遇到了这个问题
top k的话
stream出现的元素会改变id的频率，但频率改变并不能让heap里对 ...

heap 是 要按照hashmap<id, frequency> override comparator的，就用同样的Key(ID)就行了

xi3047 发表于 2019-6-7 05:18
heap 是 要按照hashmap override comparator的，就用同样的Key(ID)就行了

这样的话要先把这个时间段内的frequency统计完才能放到heap里，而不能一边改变一边放到heap里是吧？我就是想如果每个id的frequency是动态变化的，那id在heap里的位置是不会自动更新的

LZ有消息了吗？