百度笔试题目剖析——寻找热门查询

 

网上流传的百度笔试题目部分附有答案。但一家之言，难免偏颇；我也提提自己的意见。

 

更多百度笔试题汇总参见http://summerbell.iteye.com/blog/486677（百度笔试题汇总）

以及http://summerbell.iteye.com/blog/492343（百度笔试题目剖析——拼写纠错）

 

题目：

 

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

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

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

 

网上流传解答：

 

(1)思路：

用哈希做

(2)

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

 

哈希的设计是关键。

 

我的剖析：

先看看今天google的“飙升搜索”：

 

 

 

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

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

这样，我们可能得到的“飙升搜索”结果类似下图：

 

……
8	有映煮妇26/有映煮妇 26
9	剑噬天下/剑噬天下 快眼看书
……

 

         考虑中间遴选算法的复杂度，哈希显然并不是最优的选择。可以考虑后缀树或者后缀树组。据说这两大法宝也是ACM竞赛必备~

 

         后缀树的时间复杂度为O(n)，而后缀数组的时间复杂度为O(nlogn)。但后缀数组的空间消耗要更小。我在2年前的一篇论文< Web Search Results Clustering Based on a Novel Suffix Tree Structure >中使用一种改进的后缀树结构进行web搜索结果聚类。比Ukkonen的后缀树构建算法(On-line construction of suffix trees)有更快的速度和更低的空间消耗。

评论

1 楼 weishuguangeye 2011-03-28  

hehe !