algorithm - 亚马逊面试问题

Question

有一个动态变化的大文件。我们不断地往里面加一些词。您将如何跟踪每时每刻的前 10 个热门词？

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

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

Answer 1

如果它是前 10 个热门词，那么您应该使用 max-heap 和 hash-table。

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

• 创建一个新元素x，带有x.key=word 和x.count=1。
• 添加 x 到哈希表。 O(1)。
• 添加 x 到max-heap。 O(lgn).

将现有单词添加到文件时:

• 在 hash-table 中找到 x。 O(1)。
• 更新 x.count 为x.count++。

当需要检索前 10 个热门词时:

• 从 max-heap 中提取 10 次。 10*O(lgn)=O(10*lgn)=O(lgn)。

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