亚马逊面试探查

Question

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

我在一个博客上发现了这个问题，但是我不能理解答案。答案是:哈希表+ min-heap

我理解为什么哈希表而不是min-heap部分，有人能帮我吗？

Answer 1

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

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

• Create a new element x with x.key=word and x.count=1.
• Add x to the hash-table。O(1).
• Add x连接到max-heap。O(lgn).

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

hash-table中的

• Find x。到x.count++.

的O(1).

• Update x.count

当需要检索top 10 trending words时：

从max-heap执行

• Extract 10次。10*O(lgn)=O(10*lgn)=O(lgn).

如您所见，所有需要的操作最多在O(lgn)中完成。

Answer 2

如果您只想保留前10位，那么使用max-heap就太过分了。将这10个条目保存在一个排序的数组中会更简单、更快。

对于排序，只需从数组底部开始使用插入排序即可。你必须检查候选人是否已经在前十名中，如果需要的话，更新它的位置。