网上流传的百度笔试题目部分附有答案。但一家之言,难免偏颇;我也提提自己的意见。
更多百度笔试题汇总参见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)有更快的速度和更低的空间消耗。
- 大小: 14.6 KB
分享到:
相关推荐
资源名称:Python源码剖析——深度探索动态语言核心技术资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
单片机课程设计题目2011——学生版 很好的东西的
配色应用实例剖析——橙色,配色应用实例剖析——橙色,配色应用实例剖析——橙色,
数据挖掘考试题目——关联分析分享.pdf
互联网企业投资战略分析——以阿里巴巴为例.pdf互联网企业投资战略分析——以阿里巴巴为例.pdf互联网企业投资战略分析——以阿里巴巴为例.pdf互联网企业投资战略分析——以阿里巴巴为例.pdf互联网企业投资战略分析...
我国B2C电商产业的发展现状分析——基于SCP范式.pdf
商业分析全攻略——用数据分析方法解决商业问题视频教程下载,课程分为5个部分讲解。 一、前言 1、商业分析、数据分析、数据挖掘、人工智能的关联与区别 2、数据分析从业者,如何走上商业分析之路 3、产品、运营、...
金融数量分析——基于MATLAB编程
编译原理语法分析——LL(1)分析表的实现.pdf编译原理语法分析——LL(1)分析表的实现.pdf编译原理语法分析——LL(1)分析表的实现.pdf编译原理语法分析——LL(1)分析表的实现.pdf编译原理语法分析——LL(1)分析表的...
寻找皇冠上的钻石——全球股票市场历史估值与回报率分析
编译原理语法分析——LL(1)分析表的实现.docx编译原理语法分析——LL(1)分析表的实现.docx编译原理语法分析——LL(1)分析表的实现.docx编译原理语法分析——LL(1)分析表的实现.docx编译原理语法分析——LL(1)分析表...
课程分享—商业分析全攻略——用数据分析方法解决商业问题视频教程下载,课程分为5个部分讲解。 一、前言 1、商业分析、数据分析、数据挖掘、人工智能的关联与区别 2、数据分析从业者,如何走上商业分析之路 3、...
数据挖掘考试题目——关联分析.docx
C#软件项目开发全程剖析——全面透视SharpDevelop软件的开发内幕.pdf Christian Holm (德)Mike KrUger Bernhard Spuida 著 薛兴涛 袁勤勇 译 C# 软件项目开发 SharpDevelop软件开发
直播零售与传统互联网零售对比分析——基于用户购物体验角度.pdf
基于SCP框架的中国互联网广告行业分析——垄断与反垄断.pdf
跨境电商人才需求分析——以安徽省为例.pdf
实验报告——数据库的简单查询和连接查询, 包括实验的基本要求,实验目的,试验运行要求,实验原理,实验步骤,实验内容,实验数据,实验总结。此报告仅供学习交流使用!
数据挖掘考试题目——关联分析.pdf