发布于 2014-12-30 06:53:27 | 362 次阅读 | 评论: 0 | 来源: 网友投递
百度(Baidu)中文搜索引擎
百度（Nasdaq简称：BIDU）是全球最大的中文搜索引擎，2000年1月由李彦宏、徐勇两人创立于北京中关村，致力于向人们提供“简单，可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”，象征着百度对中文信息检索技术的执著追求。
本文为大家整理分享的是一份2015百度校招笔试题－机器学习/数据挖掘工程师，感兴趣的同学参考下。
笔试时间：2014-9-20
笔试职位：机器学习/数据挖掘工程师
笔试城市：天津、深圳、南京等
一. 简答题
1. new 和 malloc 的区别。
2. hash冲突是指什么?怎么解决?给两种方法，写出过程和优缺点。
3. 命中的概率是 0.25，若要至少命中一次的概率不小于 0.75，则至少需要几次?
二. 算法设计题
1. 用C/C++写一个归并排序。
数据结构为struct Node{int v; Node *next};
接口为 Node * merge_sort(Node *);
2. 设计S型层次遍历树的算法，比如根节点是第一层，第二层从左至右遍历，第三层从右至左遍历，第四层再从左至右遍历，以此类推。
举例：应依次输出 1 2 3 6 5 4 7 8 9。
3. 一个url文件，每行是一个url地址，可能有重复。
(1)统计每个url的频次，设计函数实现实现。
(2)设有10亿url，平均长度是20，现在机器有8G内存，怎么处理，写出思路。
三. 系统设计题
自然语言处理中的中文分词问题，前向最大匹配算法(FMM)。
注：题目举例说明了FMM的基本思想。
(1)设计字典的数据结构 structdictnote。
(2)用C/C++实现FMM，可选接口为
int FMM(vector iLetters, dictnode*iRoot, vector *oResults);
其中 iLetters 为待分词的句子，比如 {“小”，“明”，“今”，“天”，“买”，“了”，“i”，“p”，“o”，“n”，“e”，“6”}，
iRoot 是字典， oResults 保存输出结果，即分词的位置。也可以自己设计接口。
(3)收集了一些手机品牌的字典，如{iphone,诺基亚}。
现在要求查找包含这些手机品牌的网页，比如包含 iphone6, 诺基亚 9973 等。
怎么修改FMM实现这个功能，可以写伪代码。