当前位置: 首页 > 面试 > 正文

百度面试题:寻找热门查询

关键字:
1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share

题目:

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

(1)请描述你解决这个问题的思路;

(2)请给出主要的处理流程,算法,以及算法的复杂度。

网上流传解答:

(1)思路:

用哈希做

(2)

首先逐次读入查询串,算哈希值,保存在内存数组中,同时统计频度(注意值与日志项对应关系)选出前十的频度,取出对应的日志串,简单不过了。

哈希的设计是关键。

很明显,排名第8和排名第11的检索串,以及排名第9和排名第12的检索串,有合并的可能。

回到笔试题目,我们对这一千万个检索串记录,应该也做一些合理的处理。比如,中文分词,或者,根据空格等特征将一个检索串分为多个。当然,这些处理结果可以视为原检索串在另一空间中的映射。

本文固定链接: http://www.chepoo.com/baidu-interview-5.html | IT技术精华网

百度面试题:寻找热门查询:等您坐沙发呢!

发表评论