发布于 2014-09-26 10:40:01 | 888 次阅读 | 评论: 1 | 来源: 网友投递
百度(Baidu)中文搜索引擎
百度（Nasdaq简称：BIDU）是全球最大的中文搜索引擎，2000年1月由李彦宏、徐勇两人创立于北京中关村，致力于向人们提供“简单，可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”，象征着百度对中文信息检索技术的执著追求。
2015百度校招用户行为分析研发工程师笔试题，感兴趣的同学参考下。
一、 简答题（本题共30分）
1. 当前计算机系统一般会采用层次结构来存储数据，请介绍下典型的计算机存储系统一般分为哪几个层次，为什么采用分层存储数据能有效提高程序的执行效率？（10分）
2. Unix/Linux系统中僵尸进程是如何产生的？有什么危害？为何避免？（10分）
3. 一道选择题有如下四个选项，假设你随机选一个答案，你的答案正确的概率是那个选项？
a） 25% b）50% c）60% d）25%
请解释你选择的原因。（10分）
二、 算法与程序设计题（本题共45分）
1. 使用C/C++语言写一个函数，实现字符串的反转，要求不能用任何系统函数，且时间复杂度最小，函数原型是 char* reverse_str(char* str)。（15分）
2. 给定一个如下格式的字符串(1,(2,3),(4,(5,6),7))括号内的元素可以是数字，也可以是另一个括号，请实现一个算法消除嵌套的括号，比如把上面的表达式变成：(1,2,3,4,5,6,7)，如果表达式有误请报错。
3. 相似度计算用于衡量对象之间的相似程度，在数据挖据，自然语言处理中使一个基础性计算，在广告检索服务中往往也会判断网民检索Query和广告Adword 的主题相似度。假设Query 或者Adword 的主题属性定义为一个长度为10000 的浮点数据Pr[10000](称之为主题概率数组)，其中Pr[i]表示Query 或者Adword 属于主题Id 为i 的概率，而Query和Adword 的相似度简化定义为两者主题概率数组的内积，即sim(Query,Adword)=sum(QueryPr[i]*AdwordPr[i])(0<==i<10000).在实际应用场景中，由于大多数主题的概率都为0，所以主题概率数组往往比较稀疏，在实现时会以一个紧凑型数组topic_info_t[]的方式保存，其中100<=数组大小<=1000，并按照topic_id 递增排列，
0<=topic_id<10000,0< topic_pr<1,
Struct topic_info_t {
int topic_id;
float topic_pr;
} ;
现在给出Query 的topic_info_t 数组和N(N>=5000)个Adwords 的topic_info_t 数组，现要求出Query 与Adwords 的相似度最大值，即
max(sim(Query,Adword[i])(0<=i<N).
float max_sim(const vector<topic_info_t>& query_topic_info,
const vector<topic_info_t> adwords_topic_info[],
int adwords_number);
编写代码求时间复杂度最低的算法，并给出时间复杂度分析。(15分)
三、 系统设计题（本题共25分）
子query统计和重要子query识别
问题定义：
当query A切词后的term集是query B切词后的term集的真子集是，成query A为query B的子query，例如：
“刘德华”的切词结果为“刘德华”；
“刘德华电影”的切词结果为“刘德华 电影”；
“刘德华最新电影”的切词结果为“刘德华 最新 电影”；
“刘德华电影下载”的切词结果为“刘德华 电影 下载”；
根据以上切词结果，刘德华”是“刘德华电影”，“刘德华最新电影”, “刘德华电影下载”的子query；
“刘德华电影”是“刘德华最新电影”, “刘德华电影下载”的子query；
但是“刘德华电影下载”和“刘德华最新电影”不想不是对方的子query。
现有亿级的用户query，并且知道每个query的查询次数，要求：
（1） 列出一个query的全部子query，写出C语言实现。（15分）
（2） query中的不同term对这个query的重要形式不同的，例如“刘德华 电影 下载”中“刘德华”和“电影”的重要性比“下载”重要，因为：“刘德华 电影“所表达的查询需求，与”刘德华 下载“或者”电影 下载“相比，更接近原query的需求。根据(1)中的统计的子query数据，请给出一种思路，来计算也给query中的所有子query的重要性排序。如果认为子query数据的信息不够充分，请给出还需要哪些信息，以及获得这些信息的途径，给出算法思路描述，必要的符号和推理公式即可。（10分）
四、 统计方法（本题共20分）
假设检验是常用的统计推断方法，在大数据时代，人们可以更加容易地得到更多特征。在ab-test时，常常需要使用假设检验方法研究特征在两者样本间是否有差异。一个常见的现象是，当特征数目较多时，在同样的显著性水平下，往往更加“容易”得到“显著差异”结果。
(1). 如何看待特征数目假设检验结果的影响？
(2). 假设独立特征数目是n，如何调整各个特征的p-value，调整后的p-value真实反映特征在两组间存在差异的显著性。
(3).假设特征间分布不独立，(2)的解决方案是否需要调整，如何调整？