扫码关注微信公众号

回复“面试手册”,获取本站PDF版

回复“简历”,获取高质量简历模板

回复“加群”,加入程序员交流群

回复“电子书”,获取程序员类电子书

当前位置: 场景题 > 海量数据高频面试题 > 2.寻找热门查询,300万个查询字符串中统计最热门的10个查询

题目详细描述:搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来,每个查询床的长度不超过 255 字节。假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门),请你统计最热门的10个查询串,要求使用的内存不能超过1G。

这也就是热榜的简单实现,当然实际的热榜会复杂很多,毕竟还要考虑一部分人要撤热搜或降热度等需求。

方法一:分治+HashMap

还是前面的老方法,先用Hash映射将查询字符串映射到多个小文件中,然后用HashMap统计每个小文件中查询字符串出现的频率(key为热门字符串,value为频率),找到每个小文件中的频率最高的top10,最后通过一个小顶堆统计所有小文件中的top10。

方法二:直接用HashMap

题目中写道,去重后只有300w条数据,每条查询不超过255字节,一共是700多M,小于1G。所以可以直接遍历查询字符串,并存入到HashMap中(key为热门字符串,value为频率),通过小顶堆找到频率最高的top10

方法三:前缀树

只是把方法二中的HashMap换成了前缀树,在遍历字符串时,在前缀树中查找该字符串,如果找到,则将节点中保存的当前前缀的次数加1,没有找到,则为这个字符串构建新结点,并将新构建的结点中的次数置为1。最后还是通过小顶堆找到频率最高的top10


点击面试手册,获取本站面试手册PDF完整版