网上流传的百度笔试题目部分附有答案。但一家之言,难免偏颇;我也提提自己的意见。
更多百度笔试题汇总参见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
分享到:
相关推荐
在本文中,我们将探讨百度笔试题中的五个不同题目,涵盖编程、英文拼写纠错、热门查询统计、集合合并等知识点,这些都是计算机科学和软件工程领域中常见的问题。 首先,让我们看看第一道编程题。题目要求使用C语言...
【百度笔试题目解析】 在百度的笔试面试中,主要考察的技术知识集中在数据结构、算法、存储结构以及数据库基础。这些是计算机科学和技术的基础,对于应聘者的技术能力评估至关重要。 1. **链表操作**:链表删除一...
互联网发展对快递业影响因素分析——基于主成分分析的方法.pdf
在“时间序列分析——基于R(第2版)案例数据”中,我们将会深入探讨如何利用R语言进行有效的时序分析。R语言是一种强大的开源编程环境,特别适合于数据分析、统计计算和图形绘制。以下是关于这个主题的一些关键知识...
### 整体网分析讲义——UCINET+软件应用知识点详解 #### 第一章 社会网络分析简介 ##### 1.1 研究社会关系的学问:社会网络分析 - **网络**:指由节点(或顶点)通过边(或线)连接起来形成的系统。在社会学中,...
本资源"时间序列分析——基于R(第2版)R程序"是一个关于如何使用R语言进行时间序列分析的教程或代码集,可能是书籍的配套源代码。第二版可能意味着它包含了更新的内容和改进的方法,适应了最新的R语言版本和时间...
详情见本人博客文章“python | 编译原理,语法分析——LL(1)文法实现 上” 详情见本人博客文章“python | 编译原理,语法分析——LL(1)文法实现 上” 详情见本人博客文章“python | 编译原理,语法分析——LL(1)...
标题与描述中的关键词“数值分析”以及提及的书籍“数值分析——钟尔杰”,为我们提供了一个清晰的主题方向:深入探讨数值分析这一数学分支的核心概念、方法及其应用领域。数值分析是一门研究如何通过计算机求解数学...
《ASP网站整站程序源码——易捷域名查询系统实例开发》 在互联网技术日新月异的今天,网站开发已经成为一项重要的技能。ASP(Active Server Pages)是一种经典的服务器端脚本语言,常用于构建动态网页。这个压缩包...
工业互联网平台对工程机械融资租赁的作用分析——基于徐工汉云平台.pdf
《各大公司模电数电笔试题目》集合了众多企业针对模拟电子技术(模电)和数字电子技术(数电)的笔试题目与解答,是应聘者准备相关领域职位的重要参考资料。模电和数电是电子工程的基础学科,对于理解和设计电子系统...
Visual C++权威剖析——MFC原理、机制与开发实例pdf电子书
Visual C++权威剖析——MFC原理、机制与开发实例pdf电子书
Visual C++权威剖析——MFC原理、机制与开发实例pdf电子书
7.1 网站流量分析工具——百度统计 214 7.1.1 百度统计简介 214 7.1.2 百度统计安装指南 216 7.1.3 百度统计功能介绍 220 7.1.4 网站分析维度 229 7.2 搜索推广帮助利器——百度推广客户端 231 7.2.1 百度推广客户端...
最新深度剖析——“工业互联网、能源互联网、工业4.0”pdf,提供“最新深度剖析——“工业互联网、能源互联网、工业4.0””免费资料下载,主要包括简要介绍工业互联网、三项集成等内容,可供学习使用。
这份"百度笔试面试题目及答案1"资源包含了一份文档(百度题目1.doc)和一个名为merge.cpp的源代码文件,它们分别涵盖了编程技术和面试技巧方面的知识点。 首先,让我们深入探讨编程题目。merge.cpp很可能是一个实现...
虽然只给出了一个文件名"baidu",但我们可以推测这是一个包含多个百度笔试题目的文档或者文件夹。可能包含不同类型的题目,如编程题、算法题、逻辑题、案例分析等,按照类别或者年份进行了整理。 综合以上信息,这...
韩崇昭的《随机系统概论——分析、估计与控制》
《C#软件项目开发全程剖析——全面透视SharpDevelop软件的开发内幕》这本书是针对C#编程语言和开源集成开发环境(IDE)SharpDevelop的一份深度解析。SharpDevelop是一款专为.NET Framework设计的IDE,它提供了丰富的...