2023年百度笔试题及答案百度笔试题及答案.docx
《2023年百度笔试题及答案百度笔试题及答案.docx》由会员分享,可在线阅读,更多相关《2023年百度笔试题及答案百度笔试题及答案.docx(28页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、百度笔试题及答案-百度笔试题及答案【各位读友,本文仅供参考,望各位读 者知悉,如若喜欢或者需要本文,可点 击下载下载本文,谢谢!】祝大家工作顺利】百度java笔试题(含答案)更多面试题,百度面试笔试题解答答案专家回答:第一题简评百度的重要业务是搜索,搜索的基 本原理如下1 .编写爬虫程序到互联网上抓取 网页海量的网页。2 .将抓取来的网页通过抽取,以 一定的格式保存在能快速检索的文献系 统中。3 .把用户输入的字符串进行拆提6,符合范式分析:上述表中每个字段不可再分,一方 面满足1NF;然后数据库表中的每个实例或行 都是可以被惟一地区分(id),不存在部分 依赖,因此满足2NF;t_user_
2、info (用户信 息表)和 main_content_info (主题帖信息表)不存 在任何传递依赖,至少属于BCNF;但是sub_content_info (回复贴信 息表)不满足3NF,由于号在如下传递依 赖:id- - FatherID, FatherlD - - MainlD。范式并不是越高越好, sub_content_info表只满足2NF却更有效 率,也是当今论坛较主流的设计。第三题简评:如何对海量数据进行快速检索,这 是搜索引擎的必需考虑的问题。这又涉 及到数据结构和算法。因此,要想进 入百度,就必须熟悉一些基本的算法和 数据结构。 思绪及解决方案如下:1:设计用TRIE树实
3、现关键词到 其相应id的快速词典查找TRIE树的每一个节点为一个包含 256个元素的数组,同时指针指向其下一 级节点节点定义如下:struct trienode(int id;struct trienode * child; TRIENODE;假如TRIE树的某个节点的指针为 NULL,说明从跟节点到当前节点的途径 构成文献B中的一个关键词,在其节点的id保存该关键词的id; 假如指针不为NULL,则id相应为。或 者一个无穷大的整数,标志从根节点到当前节点的途径不是一个完整 的关键词。将关键词转化为二进制无符号 char型数组,即对于汉字等双字节字符 视为两个无符号char型整数,每个元素的
4、取值范围在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=clc2cm, 对cl至U cm每个字符,执行环节4环节4:获取根节点的第cl个元 素指针,转移到节点nodel,根
5、据nodel的第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文献的过程
6、 除了 TRIE树空间外基本不需要太多额 外的空间,空间复杂度为0(1),由于系 统有1G的可用内存,TRIE占用的空间 在几十兆到200M之间(与关键词集合有 关),因此本方法完全可行。更多面试题,百度网上笔试题及答 案编程:1编程:用C语言实现一个 revert函数,它的功能是将输入的字符 串在原串上倒序后返回。编程:2编 程:用C语言实现函数void * memmove(void *dest,const void *src,size_t n)o memmove 函数的功能是 拷贝src所指的内存内容前n个字节 到dest所指的 地址上。英文拼写纠 错:3英文拼写纠错:在用户输入英 文单词
7、时,经常发生错误,我们需要对 其进行纠错。假设已经有一个包含了对 的英文单词的词典,请你设计一个拼写 纠错的程序。请描述你解决这个问题的 思绪;请给出重要的解决流程,算法, 以及算法的复杂度;请描述也许的改 善。寻找热门查询:4寻找热门查询 搜索引擎会通过日记文献把用户每次检 索使用的所有检索串都记录下来,每个 查询串的长度为1-255字节。假设目前有一千万个记录,这些查询串的重复度 比较高,虽然总数是1千万,但假如除 去反复后,不超过3百万个。一个查 询串的反复度越高,说明查询它的用户 越多,也就是越热门。请你记录最热 门 的10个查询串,规定使用的内存不能 超过1G。请描述你解决这个问题的
8、思 绪;请给出重要的解决流程,算法,以 及算法的复杂度。集合合并:5集合 合并给定一个字符串的集合,格式如: aaa bbb ccc, bbb ddd, eee fff, ggg, dddhhh规定将其中交集不为 空的集合合并,规定合并完毕后的集合 之间无交集,例如上例应输出aaa bbb ccc ddd hhh, eee fff), ggg)请描述 你解决这个问题的思绪;请给出重要的 解决流程,算法,以及算法的复杂度 请 描述也许的改善。IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII 1 题 char *revert(char * str) int n=strlen(str
9、); int i=0; char c; for(i=0;i c=str; str=str;str=c; return str; lllllllllllllllllllllllllllllllllll 2 题 void * memmove(void *dest,const void *src,size_tn) assert(dest!=O)&(src !=0); char * temp=(char * )dest; char * ss=(char * )src; int i=0; for(;i *temp =*ss ; return temp; lllllllllllllllllllllllll
10、llllllllllllllllllllllll 3题(1)思绪:字典以字母键树组织,在 用户输入同时匹配(2)流程:每输入一 个字母:沿字典树向下一层,a)若可 以顺利下行,则继续至结束,给出结果; b)若该处不能匹配,纠错解决,给出拼 写建议,继续至a);算法:1.在字典中查找单词1.在字典 中查找单词字典采用27叉树组织,每 个节点相应一个字母,查找就是一个字母 一个字母匹配.算法时间就是单词的长度k. 2,纠错算法2,纠错算法 情况:当输 入的最后一个字母不能匹配时就提醒犯 错,简化犯错解决,动态提醒也许解决 方法:(a)当前字母前缺少了一个字母:搜 索树上两层到当前的匹配作为建议;(
11、b) 当前字母拼写错误:当前字母的键盘相 邻作为提醒;根据分析字典特性和用户 单词已输入部分选择(a),(b)解决复杂性 分析:影响算法的效率重要是字典的实 现与纠错解决包)字典的实现已有成熟 的算法,改善不大,也不会成为瓶颈;(b) 纠错策略要简朴有效,如前述情况,是线 性复杂度;(3)改善(3)改善 策略选择 最是重要,可以采用记录学习的方法改 善。IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII4 题 (1)思绪(1)思绪:用哈希做思绪(2) 一 方面逐次读入查询串,算哈希值,保存 在内存数组中,同时记录频度 选出前 十的频度,取出相应的日志串
12、,简朴但 是了。哈希的设计是关键。 IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIH 5 题 思绪:先将集合按照大小排列后,优先考 虑小的集合是否与大的集合有交思绪 集。有就合并,假如小集合与所有其他 集合都没有交集,则独立。独立的集合在下一轮的比较中不用考虑。这样就可 以尽量减少字符串的比较次数。当所有 集合都独立的时候,就终止。解决流程:解决流程:1 ,将集合按照 大小排序,组成集合合并待解决列表2. 选择最小的集合,找出与之有交集的集 合,假如有,合并之;假如无,则与其 它集合是独立集合,从待解决列表中删 除。3.反复直到待解决列表为空算
13、法: 算法:lo将集合按照大小从小到大排 序,组成待解决的集合列表。2O取出待 解决集合列表中最小的集合,对于集合 的每个元素,依次在其他集合中搜索是 否有此元素存在:1若存在,则将此小 集合与大集合合并,并根据大小插入相 应的位置。转3O 2若不存在,则在 该集合中取下一个元素。假如无下一个 元素,即所有元素都不存在于其他集 合。则表白此集合独立,从待解决集合 列表中删除。并加入结 果集合列表。转 3O 3。假如待解决集合列表不为空,转2。假如待解决集合列表为空,成功退 出,则结果集合列表就是最终的输出。 算法复杂度分析:算法复杂度分析:假 设集合的个数为n,最大的集合元素为 m排序的时间复
14、杂度可以达成n*log(n) 然后对于元素在其他集合中查找,最坏 情况下为*m查找一个集合是否与其他 集合有交集的最坏情况是m*m*(n-1) 合并的时间复杂度不会超 过查找集合 有交集的最坏情况。所以最终最坏时间 复杂度为O(m*m*n*n)需要说明的是:此算法的平均时间复杂度会很 低,由于无论是查找还是合 需要说明的 是 并,都是处在最坏情况的概率很小, 并且排序后优先用最小集合作为判断是 否 独立的对象,优先与最大的集合进行 比较,这些都最大的回避了最坏情况。 (3)也许的改善:(3)也许的改善:也许 的改善一方面可以实现将每个集合里 面的字符串按照字典序进行排列,这样 就可以将查找以及
15、合并的效率增高。此 外,也许采用恰当的数据结构也可以将 成关键字去文献系统中查询并返回结 果。由以上3点可见,字符串的分析, 抽取在搜索引擎中的地位是何等重要。因此,百度的笔试面试题中,出现 这样的题就变得理所当然了。以下是该题的java实现,代码如下:程序代码程序代码import *;import *;import *;/* * author tzy *在下测试通过*/public class FileNameStatprivate String srcPath;要t己录的文 献途径private Map statMap;用于记录的mappublic FileNameStat(String
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2023 百度 笔试 答案
限制150内