亚马逊面试问题

Question

有一个动态变化的大词汇文件，我们不断地向其中添加一些单词。您如何跟踪每个时刻的前10个流行词？

我在一篇博客中找到了这个问题，但我无法理解答案。 答案是：哈希表 + 最小堆。

我明白了哈希表为什么要用，但对最小堆部分不理解，有人可以帮助我吗？

- rplusg

---

通常情况下，您需要一个小根堆来跟踪最高的N个答案，因为每个阶段都有一个候选答案，并且您想知道它是否比小根堆中最差的答案更好 - 如果是，请从小根堆中删除前N个最差答案并插入候选答案。算法似乎很直观地应该用大根堆来选择最好的答案，但是在决定是否接受新的候选答案时，这是不合适的。（请记住，当您在最后提取前N个答案时，它们将首先进出排名最差的那个）。 - mcdowella

Answer 1

如果是“前十个趋势性词语”，则应该使用一个max-heap和一个hash-table。当向文件中添加新单词时，需要执行以下操作：

- 创建一个新元素x，x.key=word，x.count=1。 - 将x添加到hash-table中，O(1)。 - 将x添加到max-heap中，O(lgn)。

如果向文件中添加现有的单词，则需要执行以下操作：

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

当需要检索“前十个趋势性词语”时，需要执行以下操作：

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

可以看出，所有必要的操作都以最多O(lgn)的时间完成。

- Avi Cohen

---

当一个不在前十名的现有单词成为前十名时，您会希望使用小根堆：移除最小值的时间是一致的。 - aw626

在最大堆中将 x.count 更新为 x.count++ - 这不应该是 O(n) 吗？你必须先在最大堆中找到 x，但你不知道它在哪里。一旦找到它，增加它并将其上移是一个 O(lgn) 操作。 - B-Con

@B-Con：由于max-heap和hash-table指向相同的元素x，因此无需在哈希表中再次查找。我会修复它，谢谢。 - Avi Cohen

你需要使用最小堆（MinHeap），而不是最大堆（MaxHeap）。因此，如果堆中有k个项目，则堆的peek是最小值；其他所有项（k-1）都比peek大。现在，如果一个具有计数> peek的新单词进来了，我们想提取最小值（O(logk)），并插入新项（O(logk)）。如果新项的计数小于peek，则意味着它比堆中的任何其他项都要小（因为它是最小堆）。我们只需将该单词丢弃，因为它不会成为前k个的一部分。 - Amit

我认为我们应该使用最大堆。假设当我开始读取文件时，有一堆10个单词被重复出现，然后单词“X”在文件的其余部分中重复出现。如果我使用最小堆，单词X将永远不会进入堆中。如果整个文件已经预处理，则最小堆是正确的。如果我们从流中读取，则应该使用最大堆。 - Sandeep

Answer 2

如果您只想保留前10个，使用最大堆是过度的。将这10个条目保存在已排序的数组中将更简单、更快。

对于排序，只需从数组底部开始使用插入排序即可。您将需要检查候选项是否已经在前十名中，如果需要，则更新其位置。

- salva

---

如果您不保留其他条目，那么没有新的条目会进入前十名。 - Karoly Horvath

@KarolyHorvath：显然，您仍需要哈希表来计算每个条目的点击次数。我的观点是，使用最小堆来管理前10个条目是过度设计了。一个简单的排序数组将表现更好，实现也会更简单。实际上，对于增量更新的前N个（除非您有大量的并列），排序数组始终比最小堆表现更好。 - salva