网上流传的百度笔试题目部分附有答案。但一家之言,难免偏颇;我也提提自己的意见。
更多百度笔试题汇总参见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
分享到:
相关推荐
通过上述知识点的总结和分析,我们可以看出广东移动2010年的笔试题目涵盖了英语语言能力和行政职业能力测试两大方面,不仅要求考生具备扎实的语言基础,还需要具备较强的逻辑思维能力和数据分析能力。备考过程中,...
直播零售与传统互联网零售对比分析——基于用户购物体验角度.pdf
互联网发展对快递业影响因素分析——基于主成分分析的方法.pdf
【C# ArcGIS Engine基础开发教程(5)——学习地图查询】 在GIS系统中,地图查询和统计是不可或缺的功能模块。地图查询分为两种主要类型:空间查询和属性查询。空间查询涉及在地图上划定特定区域,查找该区域内满足...
网页设计配色应用实例剖析——橙色系.txt
财务共享服务中心在企业中的应用分析——以国美电器集团为例-论文.zip
实验报告“贵州大学数据库实验报告——数据库的组合查询和统计查询”主要涵盖了SQL Server查询分析器的使用,以及SQL语言中涉及的查询语句、分组、统计、计算和组合查询的操作方法。以下是对这些知识点的详细说明: ...
Visual C++权威剖析——MFC原理、机制与开发实例pdf电子书
通过对2015年、2014年和2013年的笔试题目的分析,我们可以了解中兴对求职者期望的知识点和技能要求。 首先,计算机科学基础是必不可少的。这包括但不限于数据结构(如数组、链表、栈、队列、树、图等)、算法(排序...
【SQL结构化查询语言详解】 SQL(Structured Query Language)是一种用于管理和处理关系数据库的标准语言,它的功能强大,其中聚合分析是统计和分析数据的核心部分。本篇将深入讲解SQL中的聚合函数及其应用。 **...
这份"百度笔试面试题目及答案1"资源包含了一份文档(百度题目1.doc)和一个名为merge.cpp的源代码文件,它们分别涵盖了编程技术和面试技巧方面的知识点。 首先,让我们深入探讨编程题目。merge.cpp很可能是一个实现...
《寻找信息王国的朋友——了解信息技术设备》是一篇针对初学者的教学文档,旨在引导学生认识信息技术设备,探索计算机的发展历程,并熟悉计算机的基本操作。本课的主要目标包括以下几点: 1. **寻找信息技术设备**...
【标题】:“短视频APP的营销推广模式分析——以抖音为例” 【描述】:该文档深入探讨了短视频应用,特别是抖音的营销推广策略,包括病毒式营销、娱乐营销、事件营销和互动营销,同时也指出了存在的问题,如内容...
而“JAVAWML信息查询与后端信息发布系统实现——WML信息查询设计(源代码+论文)”文件则提供了完整的源代码和相关的学术论文,供学习者研究和分析。 7. 毕业设计/Java毕设:此项目作为一个毕业设计,体现了学生在...
数值分析——三次样条的matlab的实验代码
韩崇昭的《随机系统概论——分析、估计与控制》
通过对同业存单的特点、发展历程、市场现状的分析,以及对不同规模及类型的发行人在定价方面的差别的研究,本文尝试寻找存单发行定价的规律及影响因素,并基于此对以城农商行为代表的中小型银行定价策略提出建议。...
使用网源数据——上海餐饮数据,通过excel进行数据分析。餐饮是生活中必不可少的一部分,在这些众多的餐馆中,总体来讲,我国餐饮业在经营管理、运营模式、发展思路等方面还存在着很大的差距,餐饮消费市场稳定且...
《14.C#软件项目开发全程剖析——全面透视SharpDevelop软件的开发内幕》是一本深入探讨C#软件项目开发过程的专著,尤其侧重于开源IDE(集成开发环境)SharpDevelop的开发内幕。这本书旨在为读者揭示从项目规划、设计...
本压缩包文件包含了来自百度、腾讯等知名公司的面试和笔试题目,涵盖范围广泛,涉及了软件开发、算法设计、网络技术、操作系统等多个领域。 一、软件开发 软件开发是IT公司的核心业务之一,因此面试中常常会考察...