网上流传的百度笔试题目部分附有答案。但一家之言,难免偏颇;我也提提自己的意见。
更多百度笔试题汇总参见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
分享到:
相关推荐
### 百度往年实习生笔试题目解析 #### 一、公交车站牌设计 **设计要点:** 1. **信息清晰易读:** 设计时需确保站牌上的信息(包括车次、路线、方向等)清晰易读。考虑到不同人群的需求(如老年人、视力不佳者)...
【标题】:“百度地图POI数据——北京” 这个标题揭示了我们所讨论的主题是关于百度地图的POI(Point of Interest)数据,具体聚焦于北京市的区域。POI数据是地图服务中的一个重要组成部分,它包含了地图上的兴趣点...
课程分享—商业分析全攻略——用数据分析方法解决商业问题视频教程下载,课程分为5个部分讲解。 一、前言 1、商业分析、数据分析、数据挖掘、人工智能的关联与区别 2、数据分析从业者,如何走上商业分析之路 3、...
寻找皇冠上的钻石——全球股票市场历史估值与回报率分析
通过上述知识点的总结和分析,我们可以看出广东移动2010年的笔试题目涵盖了英语语言能力和行政职业能力测试两大方面,不仅要求考生具备扎实的语言基础,还需要具备较强的逻辑思维能力和数据分析能力。备考过程中,...
C#软件项目开发全程剖析——全面透视SharpDevelop软件的开发内幕.pdf Christian Holm (德)Mike KrUger Bernhard Spuida 著 薛兴涛 袁勤勇 译 C# 软件项目开发 SharpDevelop软件开发
直播零售与传统互联网零售对比分析——基于用户购物体验角度.pdf
在“时间序列分析——基于R(第2版)案例数据”中,我们将会深入探讨如何利用R语言进行有效的时序分析。R语言是一种强大的开源编程环境,特别适合于数据分析、统计计算和图形绘制。以下是关于这个主题的一些关键知识...
在本项目案例中,我们将深入探讨如何使用Python编程语言调用百度API来开发一个简单的翻译工具,即"小小翻译器"。这个项目旨在帮助初学者理解API接口的使用,以及如何将这些接口集成到实际应用中。以下是关于这个主题...
【C# ArcGIS Engine基础开发教程(5)——学习地图查询】 在GIS系统中,地图查询和统计是不可或缺的功能模块。地图查询分为两种主要类型:空间查询和属性查询。空间查询涉及在地图上划定特定区域,查找该区域内满足...
网页设计配色应用实例剖析——橙色系.txt
互联网行业网络营销策略分析——以百度企业为例 随着国家经济社会的高速发展和政府政策的大力支持,互联网行业在市场上占据较大的份额,搜索引擎营销也慢慢进入人们的视野,越来越多的商家希望通过与搜索引擎公司...
《ASP网站整站程序源码——易捷域名查询系统实例开发》 在互联网技术日新月异的今天,网站开发已经成为一项重要的技能。ASP(Active Server Pages)是一种经典的服务器端脚本语言,常用于构建动态网页。这个压缩包...
迅雷面试笔试题目涉及到多个知识点,包括算法、数据结构、编程实现、逻辑推理等。针对提供的内容,我们可以深入分析其中的技术要点。 **1. 数据库查询优化** 题目中提出了一个问题:如何使得90%的查询能在100毫秒...
实验报告“贵州大学数据库实验报告——数据库的组合查询和统计查询”主要涵盖了SQL Server查询分析器的使用,以及SQL语言中涉及的查询语句、分组、统计、计算和组合查询的操作方法。以下是对这些知识点的详细说明: ...
Visual C++权威剖析——MFC原理、机制与开发实例pdf电子书
通过对2015年、2014年和2013年的笔试题目的分析,我们可以了解中兴对求职者期望的知识点和技能要求。 首先,计算机科学基础是必不可少的。这包括但不限于数据结构(如数组、链表、栈、队列、树、图等)、算法(排序...
【SQL结构化查询语言详解】 SQL(Structured Query Language)是一种用于管理和处理关系数据库的标准语言,它的功能强大,其中聚合分析是统计和分析数据的核心部分。本篇将深入讲解SQL中的聚合函数及其应用。 **...
重庆大学数值分析实验——何光辉
基于陕西省2012年投入产出表,利用相关数据进行投入产出分析,从成本推动的角度测算煤炭价格上涨100%时对各经济部门价格水平的影响效应,分别探讨了煤炭价格波动对各产业经济影响的传导路径,进而分析其对经济的影响机制...