亚马逊采访概率

Question

有一个很大的单词文件正在动态变化.我们不断在其中添加一些词语.您如何在每个时刻跟踪前10个趋势词？

我在博客中发现了这个问题,但我无法理解答案.答案是:哈希表+最小堆

我理解为什么hashtable而不是min-heap部分,有人可以帮助我吗？

Answer 1

如果是,top 10 trending words那么你应该使用max-heapa 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 words:

• Extract10次​​起max-heap.10*O(lgn)=O(10*lgn)=O(lgn).

如您所见,所有需要的操作最多都在完成O(lgn).