亚马逊采访问题

有一个很大的文件正在动态变化。我们不断在其中添加一些词语。你将如何跟踪每个时刻的前10个热门词汇？亚马逊采访问题

我在博客中发现了这个问题，但我无法理解答案。答案是：散列表+分堆

我明白为什么hashtable但不是最小堆部分，有人可以帮助我吗？

2012-08-26 rplusg

你通常需要一个小堆来记录最高的N个答案，因为在每个阶段你都有一个候选答案，并且你想知道它是否比最小答案中的最差答案更好 - 如果它是，从最小堆中删除最差的答案N并插入候选人。拥有 - 直观 - 最大堆使得选择最佳答案变得非常容易，但是在决定是否接受新的候选答案时，这不是你想要的。（请记住，当你提取最前N个答案时，他们将首先以N中最差的那个答案出现）。 – mcdowella

如果是top 10 trending words那么您应该使用max-heap以及hash-table。

当一个新单词将被添加到然后该文件：

Create一个新元素x与x.key=wordx.count=1和。
Addx到hash-table。 O(1)。
Addx到max-heap。 O(lgn)。

当现有字被添加到然后该文件：

Find在hash-tablex。 O(1)。
Updatex.count至x.count++。

当有需要取回top 10 trending words则：从max-heap

Extract 10倍。 10*O(lgn)=O(10*lgn)=O(lgn)。

正如您所看到的，所有需要的操作都在最多O(lgn)完成。

来源

2012-08-27 05:38:02

你会想使用分钟堆：当一个不在前10的现有词成为前10时，删除min将是一致的时间。 – aw626

“在max-heap中更新x.count到x.count ++” - 不应该是'O（n）'？你必须先在'max-heap'中找到'x'，但你不知道它在哪里。一旦找到它，增加它并冒泡就是一个'O（lgn）'操作。 –

@ B-Con：由于'max-heap'和'hash-table'指向相同的元素'x'，因此不需要在哈希表中再次找到它。我会解决这个问题，谢谢。 –

如果你只想保持前10名，那么使用最大堆是矫枉过正。保持排序数组中的10个条目将更简单和更快。

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

来源

2012-08-28 07:05:20 salva

如果你不保留其他条目，没有新的条目会进入前10名。 –

@KarolyHorvath：显然你仍然需要哈希表来计算每个条目的点击数。我的观点是，使用最小堆管理前10个条目是过度的。一个简单的排序数组会更好地执行，并且实现也会更简单。实际上，对于增量更新的top-N（除非你有大量关系），排序后的数组总是会比min-hep更好。 – salva

亚马逊采访问题

回答

相关问题