假设我们想要一个系统在最后一小时内保持在推文中出现前k个频繁的单词.怎么设计呢？
我可以提出hashmap,heap,log或MapReduce,但我找不到一种非常有效的方法来做到这一点.
实际上这是一个采访中的问题.
首先,我使用哈希图来计算每个单词的频率.我还保留了一个日志,所以随着时间的推移,我可以倒数最老的单词频率.
然后我保留了一个长度为K(Top K数组)的入口数组和一个数字N,它是数组中最小的计数数.
每次出现一个新单词时,我都会更新计数hashmap并获取这个新单词的计数.如果它大于N,我会发现这个单词是否在数组中.如果是,我更新数组中的条目.如果没有,我删除数组中的最小条目并将新单词插入其中.(相应地更新N)
这是问题,我的方法无法处理删除.我可能需要迭代整个计数hashmap以找到新的顶级K.
而且,正如面试官所说,系统应该非常快速地获得结果.我想几台机器一起工作,每台机器都需要一些文字.但是,如何组合结果也成为一个问题.
algorithm ×1