我最近遇到了这个采访问题:
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名.