我最近遇到了一个面试问题：
Given a continuous twitter feed, design an algorithm to return the 100 most
frequent words used at this minute, this hour and this day.
我正在考虑一个系统，其哈希映射word -> count链接到当前分钟、小时和天的 3 个最小堆。
每条传入的消息都经过标记、清理，并在哈希映射中更新字数（如果单词已经存在，则在堆中增加键）
如果堆中不存在任何单词（并且堆大小 == 100），请检查它们是否frequency > min value在堆中，如果是，则提取最小并插入堆中。
有没有更好的方法来做到这一点？
你的算法是一个好的开始，但它不会产生正确的结果。问题在于，您描述它们的哈希表是一条单行道：一旦添加了一个单词，它就会永远被计算在内。
您需要按照您描述的方式组织的1440(24*60)哈希映射数组；word+count这些是您的每分钟计数。您需要两个额外的哈希图 - 用于小时和天的滚动总计。
在哈希映射上定义两个操作 -add和subtract，其语义是合并相同单词的计数，并在计数降至零时删除单词。
每分钟您都会启动一个新的哈希映射，并从提要中更新计数。在一分钟结束时，将该哈希图放入当前分钟的数组中，将其添加到一小时和一天的滚动总数中，然后从每小时运行总数中减去一小时前的哈希图，并从每日运行总数中减去 24 小时前的哈希图。
最后，您需要一种方法来生成给定哈希映射的前 100 个单词。这应该是一项微不足道的任务 - 将项目添加到条目数组中word+count，按计数排序，并保留前 100 个。
dasblinkenlight 很好地指出了未将项目排除在哈希图中的错误。
不过，还有一件事要补充，要实际计算给定分钟/小时/天的前 K 个单词，使用分区 (O(n)) 比排序 (O(nlgn)) 更快：
HTH。