algorithm - 亚马逊面试问题

Question

有一个大文件是动态变化的。我们不断地在其中添加一些词。您将如何跟踪每时每刻的前 10 个热门词汇？

我在博客中发现了这个问题，但我无法理解答案。答案是：hash table + min-heap

我明白为什么哈希表而不是最小堆部分，有人可以帮助我吗？

Answer 1

如果是，top 10 trending words那么您应该使用 amax-heap和 a hash-table。

当一个新词被添加到文件中时：

• Createx一个带有x.key=word和的新元素x.count=1。
• Add x到hash-table. O(1).
• Add x到max-heap. O(lgn).

当现有单词添加到文件中时：

• Find x在hash-table. O(1).
• Update x.count到x.count++.

当需要检索top 10 trending wordsthen 时：

• Extract从 10 次max-heap。10*O(lgn)=O(10*lgn)=O(lgn).

如您所见，所有需要的操作最多在O(lgn).

Answer 2

如果你只想保持前 10 名，那么使用最大堆就大材小用了。将 10 个条目保存在有序数组中会更简单、更快。

对于排序，只需使用从数组底部开始的插入排序。如果需要，您将必须检查候选人已经进入前十名并更新其位置的情况。