百度笔试题及答案解析-百度笔试题及答案解析

.百度笔试题及答案-百度笔试题及答案百度java笔试题(含答案)更多面试题，百度面试笔试题解答答案专家回答：第一题简评百度的主要业务是搜索，搜索的基本原理如下1．编写爬虫程序到互联网上抓取网.页海量的网页。2．将抓取来的网页通过抽取，以一定的格式保存在能快速检索的文件系统中。感谢阅读3．把用户输入的字符串进行拆分成关键字去文件系统中查询并返回结果。谢谢阅读由以上3点可见，字符串的分析，抽取在搜索引擎中的地位是何等重要。感谢阅读因此，百度的笔试面试题中，出现这样的题就变得理所当然了。感谢阅读以下是该题的java实现，代码如下：程序代码程序代码import*;import*;.import*;/***@authortzy*在下测试通过*/感谢阅读publicclassFileNameStat{privateStringsrcPath;//要统计的谢谢阅读文件路径privateMapstatMap;//用于统计的map精品文档放心下载publicFileNameStat(StringsrcPath)感谢阅读{=srcPath;软件开发网statMap=newTreeMap();}谢谢阅读./*获得要统计的URL的文件名*/public StringgetFileName(StringurlString)精品文档放心下载{URLurl=null;StringfilePath=null;StringfileName=null;try{url=newURL(urlString);filePath=();intindex=0;if((index=(“/”))!=-1){.fileName=(index+1);else{fileName=““;}}catch(MalformedURLException精品文档放心下载e){}returnfileName;}/*统计指定文件名的个数*/publicvoidstat(Stringfilename)谢谢阅读.{Integercount=null;if((filename)!=null){count=(Integer)(filename);感谢阅读count=newInteger(()+1);}else{count=newInteger(1);}(filename,count);}/*统计的主方法*/.public void start() throws感谢阅读FileNotFoundException,IOException感谢阅读{BufferedReaderbfin=newBufferedReader(newFileReader());精品文档放心下载Stringtemp=null;while((temp=())!=null){谢谢阅读stat(getFileName(temp));}}/*输出统计结果*/publicvoidresult(){.Iteratorit=().iterator();谢谢阅读while(()){entry=()(());((().equals(““)?”空文件名”:())+精品文档放心下载“的个数是”+()); }}publicstaticvoidmain(Stringargs)throwsException精品文档放心下载{FileNameStatfns=newFileNameStat(““);//指定成待统计文件感谢阅读();();.}}第二题简评：这道题也与百度的业务有关，百度现在除了搜索外，还有贴吧，知道，博客等重要产品。同时也在积极的探索社区化，包括前不久宣布进军电子商务领域，搜索之外的这些产品，其主要功能的实现主要是对数据库的操作。因此，想进入百度，也需要对数据库有一定的认识。实现思路及数据库设计：1，该论坛主要有两个实体对象，用户和帖子;对于帖子对象，有一个问题：回复感谢阅读.的帖子是否应该跟主题帖子存放在同一个表里?考虑到每天更新10万帖子，说明帖子数比较多，为了方便主题的呈现，我一般都把主题贴和回帖分别放在不同的表中，把主题贴和回帖分开可以提高查询效率(300万的访问量每天)。精品文档放心下载2，按照1中的思路，该论坛由两个对象(用户和帖子)变成三个实体对象，分别是用户，主题帖子，回复帖子;感谢阅读3，上述三个对象存在三个关系，分别是：用户--主题帖，一个用户可以发0个或多个帖子，一个帖子对应一个用户精品文档放心下载.(一对多关系)，主题帖--回复帖：一个主题有0个或多个回复帖子，一个回复帖子对应一个主题(一对多关系);精品文档放心下载用户--回复贴：一个用户可以回0个或多个帖，一个帖子对应一个用户(一对多关系)。感谢阅读还存在对回复贴的回复，这个考虑fatherId来表示。4，由于三个关系“用户--主题帖，主题帖--回复帖，用户--回复贴”都是一对多关系，根据表设计一般原则，可以将这两个关系独立建立表，也可以不另外建表而将一对多的关系体现在实体感谢阅读.表中;然而，表间的连接查询是非常耗资源的，所以应尽量减少表间连接，那么对三个关系不应该分别建表，而是把用户的id作为主题表和回帖表的外键，把主题贴id作为回帖表的外键。感谢阅读5，鉴于以上考虑，该论坛的三个表如下所示表名：t_user_info(用户信息表)字段名类型缺省值中文含谢谢阅读义 约束 备注id Int 用户编号Auto_incrementName Varchar(30)Email Varchar(50)

PRI用户名.Phone Varchar(30)Addr Varchar(200)其他字段略，根据需要添加 表名：main_content_info(主题帖信息表)精品文档放心下载字段名类型缺省值中文含义约束备注id Int 贴编号 PRIAuto_incrementTitle Varchar(200) 发帖标题Content Text 发帖内容UserID Int 用户编号外键其他字段略，根据需要添加表名：sub_content_info(回复贴信.息表)字段名类型 缺省值 中文含义约束 备注id Int 贴编号 PRIAuto_incrementTitleVarchar(200)发帖标题ContentText发帖内容精品文档放心下载UserID Int 用户编号 外键FatherIDMainID

IntInt

父编号主题帖编号外键其他字段略，根据需要添加6，符合范式分析：.上述表中每个字段不可再分，首先满足1NF;然后数据库表中的每个实例或行都是可以被惟一地区分(id)，不存在部分依赖，因此满足2NF;感谢阅读t_user_info(用户信息表)和main_content_info(主题帖信息表)不存在任何传递依赖，至少属于BCNF;精品文档放心下载但是sub_content_info(回复贴信息表)不满足3NF,因为存在如下传递依感谢阅读赖 ：id-->FatherID,FatherID-->MainID。感谢阅读范式并不是越高越好，sub_content_info表只满足2NF却更谢谢阅读.有效率，也是当今论坛较主流的设计。第三题简评：如何对海量数据进行快速检索，这是搜索引擎的必需考虑的问题。这又涉及到数据结构和算法。因此，要想进入百度，就必须熟悉一些基本的算法和数据结构。思路及解决方案如下：感谢阅读设计用TRIE树实现关键词到其对应id的快速词典查找谢谢阅读TRIE树的每一个节点为一个包含256个元素的数组，同时指针指向其下一级节点节点定义如下：.structtrienode{int id;structtrienode*child;}TRIENODE;如果TRIE树的某个节点的指针为NULL，说明从跟节点到当前节点的路径构成文件B中的一个关键词，感谢阅读在其节点的id保存该关键词的id;如果指针不为NULL，则id对应为0或者一个无穷大的整数，标志从根节点感谢阅读到当前节点的路径不是一个完整的关键词。将关键词转化为二进制无符号char.型数组，即对于汉字等双字节字符视为两个无符号char型整数，谢谢阅读每个元素的取值范围在0到255之间。2：生成文件b的TRIE树步骤1：依次读取文件b的每一行，对每一行执行步骤2到步骤5感谢阅读步骤2：读取关键词id和关键词，令为key步骤3：依次读取key的每一个字符，对每一个字符，执行步骤4;感谢阅读步骤4：如果该字符对应的指针为NULL，则创建其儿子节点;感谢阅读步骤5：为当前节点的对应字符id.置为关键词id3：根据A文件生成C文件步骤1：依次读取文件A的每一行，对每一行执行步骤2到步骤5感谢阅读步骤2：分别获取当前行关键词、ip地址和时间步骤3：令关键词key=c1c2...cm，对c1到cm每个字符，执行步骤4谢谢阅读步骤4：获取根节点的第c1个元素指针，转移到节点node1，谢谢阅读根据node1的第c2个元素指针，转移到node2...精品文档放心下载根据nodem的第cm个元素，获取关键词的id谢谢阅读.步骤5：往文件c中写入一行数据，格式为关键词的id、ip地址和时间感谢阅读生成文件B的TRIE树过程时间复杂度为O(n*m)，其中n为文件b行数，m为文件b关键词的最大长度。TRIE的空间复杂度为O(n*m)，n和m含义同上，但由于实际应用中关键词之间可能会有很多前缀相同现象，所以实际耗费空间并不会很高。精品文档放心下载生成C文件的时间复杂度同样为O(n*m)，n为文件a行数，m为文件a关键词的最大长度，因为有了TRIE树之后，给定一个关键词获得其id的时间复杂度为关键词长度。生成C文件的过程谢谢阅读.除了TRIE树空间外基本不需要太多额外的空间，空间复杂度为O(1)，由于系统有1G的可用内存，TRIE占用的空间在几十兆到200M之间(与关键词集合有关)，因此本方法完全可行。谢谢阅读更多面试题，百度网上笔试题及答案编程：1编程：用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。编程：2编程：用C语言实现函数void*memmove(void*dest,constvoid*src,size_tn)。memmove函数的功能是拷贝src所指的内存内容前n个字感谢阅读.节到dest所指的地址上。英文拼写纠错：3英文拼写纠错：在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包含了正确英文单词的词典，请你设计一个拼写纠错的程序。请描述你解决这个问题的思路；请给出主要的处理流程，算法，以及算法的复杂度；请描述可能的改进。寻找热门查询：4寻找热门查询搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除谢谢阅读.去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。请描述你解决这个问题的思路；请给出主要的处理流程，算法，以及算法的复杂度。集合合并：5集合合并给定一个字符串的集合，格式如：{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{dddhhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaa感谢阅读cccdddhhh}，{eeefff}，{ggg}请描述你解决这个问题的思路；请给出精品文档放心下载.主要的处理流程，算法，以及算法的复杂度请描述可能的改进。精品文档放心下载////////////////////////////////1题char*revert(char*str){intn=strlen(str);inti=0;charc;for(i=0;i{c=str;str=str;str=c;}returnstr;}精品文档放心下载///////////////////////////////////2题void*memmove(void*dest,const精品文档放心下载void*src,size_tn){assert((dest!=0)&&(src!=0));char*temp=(char*)dest;char*ss=(char*)src;inti=0;for(;i{*temp=*ss;}谢谢阅读return temp; }./////////////////////////////////////////////////3题(1)思路:字典以字母键树组织，在用户输入同时匹配(2)流程:每输入一个字母：沿字典树向下一层，a）若可以顺利下行，则继续至结束，给出结果；b)若该处不能匹配，纠错处理，给出拼写建议,继续至a）；谢谢阅读算法:1.在字典中查找单词1.在字典中查找单词字典采用27叉树组织,每个节点对应一个字母,查找就是一个字母一个字母匹配.算法时间就是单词的长度k.2.纠错算法2.纠错算法情况:当输入的最后一个字母不能匹配时就提示出错,感谢阅读.简化出错处理，动态提示可能处理方法:(a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议；(b)当前字母拼写错误：当前字母的键盘相邻作为提示；根据分析字典特征和用户单词已输入部分选择(a),(b)处理复杂性分析：影响算法的效率主要是字典的实现与纠错处理(a）字典的实现已有成熟的算法，改进不大，也不会成为瓶颈；(b)纠错策略要简单有效,如前述情况，是线性复杂度；(3)改进(3)改进策略选择最是重要，可以采用统计学习的方法改精品文档放心下载进 。////////////////////////////////////////感谢阅读.//////4题(1)思路(1)思路：用哈希做思路(2)首先逐次读入查询串，算哈希值，保存在内存数组中，同时统计频度选出前十的频度，取出对应的日志串，简单不过了。哈希的设计是关键。////////////////////////////////////////感谢阅读//////////5题思路：先将集合按照大小排列后,优先考虑小的集合是否与大的集合有交思路集。有就合并，如果小集合与所有其他集合都没有交集，则独立。独立的集合在下一轮的比较中不用考虑。这样就可以尽量减少字符串的比较次数。当所有集合都独立的时候，就终止。谢谢阅读.处理流程：处理流程：1.将集合按照大小排序，组成集合合并待处理列表2.选择最小的集合，找出与之有交集的集合，如果有，合并之；如果无，则与其它集合是独立集合，从待处理列表中删除。3.重复直到待处理列表为空算法：算法：1。将集合按照大小从小到大排序,组成待处理的集合列表。2。取出待处理集合列表中最小的集合，对于集合的每个元素，依次在其他集合中搜索是否有此元素存在：1>若存在，则将此小集合与大集合合并，并根据大小插入对应的位置。转3。2>若不存在，则感谢阅读.在该集合中取下一个元素。如果无下一个元素，即所有元素都不存在于其他集合。则表明此集合独立，从待处理集合列表中删除。并加入结果集合列表。转3。3。如果待处理集合列表不为空，转2。如果待处理集合列表为空，成功退出，则结果集合列表就是最终的输出。算法复杂度分析：算法复杂度分析：假设集合的个数为n，最大的集合元素为感谢阅读排序的时间复杂度可以达到n*log(n)然后对于元素在其他集合中查找，最坏情况下为*m查找一个集合是否与其他集合有交集的最坏情况是m*m*(n-1)合并的时间复杂度不会超谢谢阅读.过查找集合有交集的最坏情况。所以最终最坏时间复杂度为O(m*m*n*n)需要说明谢谢阅读的是：此算法的平均时间复杂度会很低，因为无论是查找还是合需要说明的是并，都是处于最坏情况的概率很小，而且排序后优先用最小集合作为判断是否独立的对象，优先与最大的集合进行比较，这些都最大的回避了最坏情况。(3)可能的改进：(3)可能的改进：可能的改进首先可以实现将每个集合里面的字符串按照字典序进行排列，这样就可以将查找以及合并的效率增高。另外，可能采取恰当的数据结构也可以将查找精品文档放心下载.以及合并等操作的效率得到提高。百度11月4日网上笔试题及答案(仅供参考)百度11月4日网上笔试题及答案编程：1用C语言实现一个revert函数，它的功能是将输入的字符串在原串上倒序后返回。感谢阅读2编程：用 C 语言实现函数 void *.memmove(void*dest,constvoid*src,size_t谢谢阅读n)。memmove函数的功能是拷贝src所指的内存内容前n个字节精品文档放心下载到dest所指的地址上。英文拼写纠错：在用户输入英文单词时，经常发生错误，我们需要对其进行纠错。假设已经有一个包精品文档放心下载.含了正确英文单词的词典，请你设计一个拼写纠错的程序。请描述你解决这个问题的思路；请给出主要的处理流程，算法，以及算法的复杂度；请描述可能的改进。寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串谢谢阅读的长度为1-255字节。假设目前有一千.万个记录，这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过精品文档放心下载百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。请描述你解决这个问题的思路；谢谢阅读请给出主要的处理流程，算法，以及算法的复杂度。5集合合并：.给定一个字符串的集合，格式如：{aaabbbccc}，{bbbddd}，{eeefff}，{ggg}，{dddhhh}精品文档放心下载要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应感谢阅读输出{aaabbbcccdddhhh}，{eeefff}，{ggg}感谢阅读请描述你解决这个问题的思路；请给出主要的处理流程，算法，以及算法的复杂度.请描述可能的改进。////////////////////////////////1感谢阅读1题char*revert(char*str){intn=strlen(str);inti=0;charc;for(i=0;i{c=str;str=str;str=c;}.returnstr;}///////////////////////////////////谢谢阅读2题void*memmove(void*dest,const精品文档放心下载void*src,size_tn){assert((dest!=0)&&(src!=0));char*temp=(char*)dest;char*ss=(char*)src;inti=0;谢谢阅读for(;i{*temp++=*ss++;}.returntemp;}////////////////////////////////////////谢谢阅读/////////3题(1)思路:字典以字母键树组织，在用户输入同时匹配(2)流程:.每输入一个字母：沿字典树向下一层，a）若可以顺利下行，则继续至结束，给出结果；b)若该处不能匹配，纠错处理，给出拼写建议,继续至a）；算法:1.在字典中查找单词字典采用27叉树组织,每个节点对应一个字母,查找就是一个字母谢谢阅读一个字母匹配.算法时间就是单词的长度k..2.纠错算法情况:当输入的最后一个字母不能匹配时就提示出错,简化出错处理，动态提示可能处理方法:精品文档放心下载(a)当前字母前缺少了一个字母：搜索树上两层到当前的匹配作为建议；谢谢阅读(b)当前字母拼写错误：当前字母的键盘相邻作为提示；精品文档放心下载根据分析字典特征和用户单词已输入部分选择(a),(b)处理感谢阅读复杂性分析：影响算法的效率主要是字典的实现与纠错处理感谢阅读.字典的实现已有成熟的算法，改进不大，也不会成为瓶颈；精品文档放心下载(b)纠错策略要简单有效,如前述情况，是线性复杂度；谢谢阅读(3)改进策略选择最是重要，可以采用统计学习的方法改进。////////////////////////////////////////谢谢阅读//////4题(1)思路：.用哈希做(2)首先逐次读入查询串，算哈希值，保存在