还剩27页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
百度笔试题及答案-百度笔试题及答案【各位读友,本文仅供参考,望各位读者知悉,如若喜欢或者需要本文,可点击下载下载本文,谢谢!】祝大家工作顺利】百度笔试题(含答案)java更多面试题,百度面试笔试题解答答案专家回答第一题简评百度的重要业务是搜索,搜索的基本原理如下编写爬虫程序到互联网上抓取网页
1.海量的网页将抓取来的网页通过抽取,以一定的
2.格式保存在能快速检索的文献系统中.把用户输入的字符串进行拆3提符合范式分析6,上述表中每个字段不可再分,一方面满足1NF;然后数据库表中的每个实例或行都是()可以被惟一地区分不存在部分依赖,id,因此满足2NF;(用户信息表)和t_user_info(主题帖信息表)不存在main_content_info任何传递依赖,至少属于BCNF;但是(回复贴信息sub_content_info表)不满足由于号在如下传递依赖3NF,id--FatherID,FatherlD--MainlD范式并不是越高越好,表只满足却更有效率,sub_content_info2NF也是当今论坛较主流的设计第三题简评如何对海量数据进行快速检索,这是搜索引擎的必需考虑的问题这又涉及到数据结构和算法因此,要想进入百度,就必须熟悉一些基本的算法和数据结构思绪及解决方案如下设计用树实现关键词到其相1TRIE应的快速词典查找id树的每一个节点为一个包含TRIE256个元素的数组,同时指针指向其下一级节点节点定义如下struct trienodeint id;struct trienode*child;}TRIENODE;假如树的某个节点的指针为TRIE说明从跟节点到当前节点的途径构成NULL,文献中的一个关键词,B在其节点的保存该关键词的假如id id;指针不为则相应为或者一个无穷NULL,id大的整数,标志从根节点到当前节点的途径不是一个完整的关键词将关键词转化为二进制无符号型char数组,即对于汉字等双字节字符视为两个无符型整数号char,每个元素的取值范围在到之间0255生成文献的树2b TRIE环节依次读取文献的每一行,对1b每一行执行环节到环节25环节读取关键词和关键词,令为2idkey环节依次读取的每一个字符,3key对每一个字符,执行环节4;环节假如该字符相应的指针为4则创建其儿子节点;NULL,环节为当前节点的相应字符置为5id关键词id根据文献生成文献3A C环节依次读取文献的每一行,1A对每一行执行环节到环节25环节分别获取当前行关键词、2ip地址和时间环节令关键词对3key=clc2…cm,cl至每个字符,执行环节U cm4环节获取根节点的第个元素指4cl针,转移到节点nodel,根据的第个元素指针,转移nodel c2到node
2...根据的第个元素,获取关nodem cm键词的id环节往文献中写入一行数据,格5c式为关键词的、地址和时间id ip生成文献的树过程时间复杂B TRIE度为其中为文献行数,为文献On*m,n bm关键词的最大长度的空间复杂度为b TRIE和含义同上,但由于实际应用中On*m,n m关键词之间也许会有很多前缀相同现象,所以实际花费空间并不会很高生成文献的时间复杂度同样为C为文献行数,为文献关键词On*m,n am a的最大长度,由于有了树之后,给定一TRIE个关键词获得其的时间复杂度为关键词长id度生成文献的过程除了树空间外C TRIE基本不需要太多额外的空间,空间复杂度为由于系统有的可用内存,占用01,1G TRIE的空间在几十兆到之间与关键词集合200M有关,因此本方法完全可行更多面试题,百度网上笔试题及答案编程编程用语言实现一个函1C revert数,它的功能是将输入的字符串在原串上倒序后返回编程编程用语言实现函数2Cvoid*memmovevoid*dest,const void函数的功能是拷贝*src,size_t nmemmoveo所指的内存内容前个字节到所指的src ndest地址上英文拼写纠错英文拼写纠错在3用户输入英文单词时,经常发生错误,我们需要对其进行纠错假设已经有一个包含了对的英文单词的词典,请你设计一个拼写纠错的程序请描述你解决这个问题的思绪;请给出重要的解决流程,算法,以及算法的复杂度;请描述也许的改善寻找热门查询寻找热门4查询搜索引擎会通过日记文献把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为字节假设目前1-255有一千万个记录,这些查询串的重复度比较高,虽然总数是千万,但假如除去反复后,不超1过百万个一个查询串的反复度越高,说明3查询它的用户越多,也就是越热门请你记录最热门的个查询串,规定使用的内存不能10超过请描述你解决这个问题的思绪;请1G给出重要的解决流程,算法,以及算法的复杂度集合合并集合合并给定一个字符串的5集合,格式如{aaa bbbccc},{bbb ddd},{eee规定将其中交集不为空fff},{ggg},{dddhhh}的集合合并,规定合并完毕后的集合之间无交集,例如上例应输出{aaa bbbccc dddhhh},请描述你解决这个问题的思绪;{eee fff,{ggg请给出重要的解决流程,算法,以及算法的复杂度请描述也许的改善题IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII1char*revertchar*str{int n=strlenstr;int i=0;char c;fori=0;i{c=str;str=str;题str=c;}return str;}lllllllllllllllllllllllllllllllllll2void*memmovevoid*dest,const void*src,size_t n{assertdest!=Osrc!=0;char*temp=char*dest;char*ss=char*src;inti=0;for;i{*temp=*ss;}return temp;}题思绪字典lllllllllllllllllllllllllllllllllllllllllllllllll31以字母键树组织,在用户输入同时匹配流2程每输入一个字母沿字典树向下一层,a若可以顺利下行,则继续至结束,给出结果;b若该处不能匹配,纠错解决,给出拼写建议,;继续至a算法.在字典中查找单词.在字典中查11找单词字典采用叉树组织,每个节点相应27一个字母,查找就是一个字母一个字母匹配.算法时间就是单词的长度,纠错算法,纠错算法情况:当输入的k.22最后一个字母不能匹配时就提醒犯错,简化犯()错解决,动态提醒也许解决方法:当前a字母前缺少了一个字母搜索树上两层到当前()的匹配作为建议;当前字母拼写错误b当前字母的键盘相邻作为提醒;根据分析字典()()特性和用户单词已输入部分选择a,b解决复杂性分析影响算法的效率重要是字典的实现与纠错解决包)字典的实现已有成熟的()算法,改善不大,也不会成为瓶颈;纠b错策略要简朴有效,如前述情况,是线性复杂()()度;改善改善策略选择最是重要,33可以采用记录学习的方法改善()题思IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII41()()绪思绪用哈希做思绪一方面逐12次读入查询串,算哈希值,保存在内存数组中,同时记录频度选出前十的频度,取出相应的日志串,简朴但是了哈希的设计是关键题思绪IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIH5先将集合按照大小排列后,优先考虑小的集合是否与大的集合有交思绪集有就合并,假如小集合与所有其他集合都没有交集,则独立独立的集合在下一轮的比较中不用考虑这样就可以尽量减少字符串的比较次数当所有集合都独立的时候,就终止解决流程解决流程,将集合按照大小1排序,组成集合合并待解决列表选择最小的
2.集合,找出与之有交集的集合,假如有,合并之;假如无,则与其它集合是独立集合,从待解决列表中删除.反复直到待解决列表为空3算法:算法将集合按照大小从小到大排序,lo组成待解决的集合列表取出待解决集合2O列表中最小的集合,对于集合的每个元素,依>次在其他集合中搜索是否有此元素存在1若存在,则将此小集合与大集合合并,并根据>大小插入相应的位置转若不存在,则32O在该集合中取下一个元素假如无下一个元素,即所有元素都不存在于其他集合则表白此集合独立,从待解决集合列表中删除并加入结果集合列表转假如待解决集合列33O表不为空,转假如待解决集合列表为空,成功退出,则2结果集合列表就是最终的输出算法复杂度分析算法复杂度分析假设集合的个数为n,最大的集合元素为排序的时间复杂度可以m达成然后对于元素在其他集合中查找,n*logn最坏情况下为*查找一个集合是否与其他集m合有交集的最坏情况是合并的时m*m*n-1间复杂度不会超过查找集合有交集的最坏情况所以最终最坏时间复杂度为Om*m*n*n需要说明的是此算法的平均时间复杂度会很低,由于无论是查找还是合需要说明的是并,都是处在最坏情况的概率很小,并且排序后优先用最小集合作为判断是否独立的对象,优先与最大的集合进行比较,这些都最大的回避了最坏情况也许的改善也许的改善也33许的改善一方面可以实现将每个集合里面的字符串按照字典序进行排列,这样就可以将查找以及合并的效率增高此外,也许采用恰当的数据结构也可以将成关键字去文献系统中查询并返回结果由以上点可见,字符串的分析,抽取3在搜索引擎中的地位是何等重要因此,百度的笔试面试题中,出现这样的题就变得理所当然了以下是该题的实现,代码如java下程序代码程序代码import*;import*;import*;在下测试通过/***@author tzy**/public classFileNameStat{〃要己录的文献private StringsrcPath;t途径〃用于记录的private MapstatMap;mappublic FileNameStatStringsrcPath软件开发网=srcPath;查找以及合并等操作的效率得到提高百度月日网上笔试题及答案仅供参考n4百度月日网上笔试题及答案n4编程用语言实现一个函数,它的功能1C revert是将输入的字符串在原串上倒序后返回编程2用语言实现函数C void*memmovevoid*dest,const void*src,size_tn memmoveo函数的功能是拷贝所指的内存内容前src n个字节到所指的地址上dest英文拼写纠错3在用户输入英文单词时,经常发生错误,我们需要对其进行纠错假设已有一个包含了对的英文单词的词典,请你设计一个拼写纠错的程序请描述你解决这个问题的思绪;请给出重要的解决流程,算法,以及算法的复杂度;请描述也许的改善寻找热门查询4搜索引擎会通过日记文献把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为字节假设目前有一千万个1-255记录,这些查询串的反复度比较高,虽然总数是千万,但假如除去反复后,不超过百万13个一个查询串的反复度越高,说明查询它的O用户越多,也就是越热门请你记录最热门的个查询10串,规定使用的内存不能超过IGo请描述你解决这个问题的思绪;请给出重要的解决流程,算法,以及算法的复杂度集合合并5给定一个字符串的集合,格式如{aaa bbbccc},{bbb ddd},{eee fff},{ggg},{dddhhh规定将其中交集不为空的集合合并,规定合并完毕后的集合之间无交集,例如上例应输出{aaa bbbccc dddhhh},{eeefff},{ggg}请描述你解决这个问题的思绪;请给出重要的解决流程,算法,以及算法的复杂度请描述也许的改善IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII1题1char*revertchar*strint n=strlenstr;int i=0;char c;fori=0;i{c=str;str=str;str=c;return str;lllllllllllllllllllllllllllllllllll题2void*memmovevoid*dest,const void*src,size_t nassertdest!=Osrc!=O;char*temp=char*dest;char*ss=char*src;inti=0;for;i{*temp++=*ss++;return temp;lllllllllllllllllllllllllllllllllllllllllllllllll题3思绪1字典以字母键树组织,在用户输入同时匹配2流程每输入一个字母沿字典树向下一层,若可以顺利下行,则继续至结束,a给出结果;若该处不能匹配,纠错解决,给出拼写建b;议,继续至a算法•在字典中查找单词1字典采用叉树组织,每个节点相应一个27字母,查找就是一个字母一个字母匹配.算法时间就是单词的长度k..纠错算法2情况:当输入的最后一个字母不能匹配时就提醒犯错,简化犯错解决,动态提醒也许解决方法当前字母前缺少了一个字母搜索树上两a层到当前的匹配作为建议;当前字母拼写错误当前字母的键b盘相邻作为提醒;根据分析字典特性和用户单词已输入部分选择解决a,b复杂性分析:影响算法的效率重要是字典的实现与纠错解决字典的实现已有成熟的算法,改善不大,也不会成为瓶颈;纠错策略要简朴有效,如前述情况,是线b性复杂度;改善3策略选择最是重要,可以采用记录学习的方法改善IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII题4⑴思绪用哈希做2一方面逐次读入查询串,算哈希值,保存在内存数组中,同时记录频度选出前十的频度,取出相应的日记串,简朴但是了哈希的设计是关键IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII题5思绪先将集合按照大小排列后,优先考虑小的集合是否与大的集合有交集有就合并,假如小集合与所有其他集合都没有交集,则独立独立的集合在下一轮的比较中不用考虑这样就可以尽量减少字符串的比较次数当所有集合都独立的时候,就终止解决流程,将集合按照大小排序,组成集合合并待解1决列表.选择最小的集合,找出与之有交集的集合,2假如有,合并之;假如无,则与其它集合是独立集合,从待解决列表中删除.反复直到待解决列表为空3算法将集合按照大小从小到大排序,组成待解lo决的集合列表取出待解决集合列表中最小的集合,对于2集合的每个元素,依次在其他集合中搜索是否有此元素存在>若存在,则将此小集合与大集合合并,1并根据大小插入相应的位置转3>若不存在,则在该集合中取下一个元素2假如无下一个元素,即所有元素都不存在于其他集合则表白此集合独立,从待解决集合列表中删除并加入结果集合列表转3假如待解决集合列表不为空,转32假如待解决集合列表为空,成功退出,则结果集合列表就是最终的输出算法复杂度分析假设集合的个数为最大的集合元素为n,m排序的时间复杂度可以达成n*logn然后对于元素在其他集合中查找,最坏情况下为*m查找一个集合是否与其他集合有交集的最坏情况是m*m*n-lstatMap=new TreeMapO;/*获得要记录的的文献名*/URLpublic StringgetFileNameString urlStringURLurl=null;String filePath=null;String fileName=null;try url=new URLurlString;filePath=;int index=O;ifindex=/»!=-l fileN ame=index+1;;elsefileName=}合并的时间复杂度不会超过查找集合有交集的最坏情况所以最终最坏时间复杂度为Om*m*n*n需要说明的是:此算法的平均时间复杂度会很低,由于无论是查找还是合并,都是处于最坏情况的概率很小,并且排序后优先用最小集合作为判断是否独立的对象,优先与最大的集合进行比较,这些都最大的回避了最坏情况也许的改善:3一方面可以实现将每个集合里面的字符串按照字典序进行排列,这样就可以将查找以及合并的效率增高此外,也许采用恰当的数据结构也可以将查找以及合并等操作的效率得到提高【各位读友,本文仅供参考,望各位读者知悉,如若喜欢或者需要本文,可点击下载下载本文,谢谢!】祝大家工作顺利】catchMalformedURLException ereturnfileName;/*记录指定文献名的个数*/publicvoid statStringfilename Integercount=null;iffilename!=null count=Integerfilename;count=new Integer+1;}else count=new Integerl;}filename,count;/*记录的主方法*/public voidstart throwsFileNotFoundExceptionJOExceptionBufferedReader bfin=newBufferedReadernew FileReader;String temp=null;whiletemp=!=nullstatgetFileNametemp;/*输出记录结果*/public voidresultIterator it=.iterator;whileentry=;空文献名”:+.equak”“的个数是+;}public staticvoid mainStringargsthrows ExceptionFileNameStatfns=new〃指定成待记录文献FileNameStat;0;0;第二题简评这道题也与百度的业务有关,百度现在除了搜索外,尚有贴吧,知道,博客等重要产品同时也在积极的探索社区化,涉及前不久宣布进军电子商务领域,搜索之外的这些产品,其重要功能的实现重要是对数据库的操作因此,想进入百度,也需要对数据库有一定的结识实现思绪及数据库设计该论坛重要有两个实体对象,用户和帖子;L对于帖子对象,有一个问题回复的帖子是否应当跟主题帖子存放在同一个表里?考虑到天天更新万帖子,说明帖1子数比较多,为了方便主题的呈现,我一般都把主题贴和回帖分别放在不同的表中,把主题贴和回帖分开可以提高(查询效率万的访问量天天)30按照中的思绪,该论坛由两个对2,1象(用户和帖子)变成三个实体对象,分别是用户,主题帖子,回复帖子;上述三个对象存在三个关系,3,分别是用户-主题帖,一个用户可以发个或多个帖子,一个帖子相应一个用户(一对多关系),主题帖--回复帖一个主题有个或多个回复帖子,一个回复帖子相应一个主题(一对多关系);用户-回复贴一个用户可以回个或0多个帖,一个帖子相应一个用户(一对多关系)还存在对回复贴的回复,这个考虑用来表达fatherld由于三个关系“用户-主题帖,主题4,帖-回复帖,用户-回复贴”都是一对多关系,根据表设计一般原则,可以将这两个关系独立建立表,也可以不此外建表而将一对多的关系体现在实体表中;然而,表间的连接查询是非常耗资源的,所以应尽量减少表间连接,那么对三个关系不应当分别建表,而是把用户的作为主题表和回帖表的外键,把主题id贴作为回帖表的外键id鉴于以上考虑,该论坛的三个表如5,下所示表名用户信息表t_user_info字段名类型缺省值中文含义约束备注用户编号id IntPRIAuto_increment用户名Name Varchar30Email Varchar50Phone Varchar30Addr Varchar200其他字段略,根据需要添加表名主题帖信息表main_content_info字的名类型缺省值中文含义约束备注贴编号id IntPRIAuto_increment发帖标题Title Varchar200发帖内容Content Text用户编号外键UserID Int其他字段略,根据需要添加表名回复贝占信sub_content_info息表字段名类型缺省值中文含义约束备注贴编号id IntPRIAuto_increment发帖标题Title Varchar200Content Text发帖内容键UserID Int用户编号外FatherlD Int父编号外键MainlD Int主题帖编号其他字段略,根据需要添加。