发布于 2014-09-25 10:20:01 | 1533 次阅读 | 评论: 1 | 来源: 网友投递
百度(Baidu)中文搜索引擎
百度（Nasdaq简称：BIDU）是全球最大的中文搜索引擎，2000年1月由李彦宏、徐勇两人创立于北京中关村，致力于向人们提供“简单，可依赖”的信息获取方式。“百度”二字源于中国宋朝词人辛弃疾的《青玉案·元夕》词句“众里寻他千百度”，象征着百度对中文信息检索技术的执著追求。
这是一个网友投递的2014年百度校园招聘软件工程师面试过程,并附有作者的答题思路和分析，感兴趣的同学参考下。
今天去面试百度了，一面感觉比较简单，百分之九十多都答上来了。坐下来面试的时候我看到了桌上我的笔试试卷，瞄到了分数，我擦，44分，这还能过笔试！然后等会有看到其他两张笔试卷，一张29分一张33分。。看来笔试给分是严格来给的。
面试官先让我做自我介绍。然后马上就谈项目了，叫我挑一个项目讲讲怎么做的，解决了什么问题。问项目我最不怕了，毕竟项目都是自己认真地完成的，也确实在做项目过程中学到了很多东西，解决了一些问题。
说完他让我写写程序，问我知道哪些排序算法，叫我写一个熟悉的排序算法。居然让我自己选择，那果断快速排序啊。如下：
void quick_sort(int array[], int begin, int end)
{
if(end > begin)
{
int pivot = begin;
int last_small = begin;
int i = end;
while(last_small != i)
{
if(array[i] <= array[pivot])
{
int temp = array[i];
array[i] = array[++last_small];
array[last_small] = temp;
}
else
i--;
}
int tmp = array[pivot];
array[pivot] = array[last_small];
array[last_small] = tmp;
quick_sort(array, begin, last_small - 1);
quick_sort(array, last_small + 1, end);
}
}
然后叫我写反转链表。。太经常问了这问题。但他一开始说不允许另外开辟地址，我还以为临时变量都不让声明，我就说这有点难。但是过一会他纠正了，临时变量是可以的。
void reversal(listNode* head)//reverse the list
{
listNode* before = NULL;
listNode *current = head;
listNode *temp = head;
while(current != NULL)
{
listNode* next = current->next;
current->next = before;
before = current;
current = next;
}
head = before;
}
问：在已排序好的数组找两个数a+b等于给定的N。
对于一个数组array，长度为size，令begin = 0，end = size - 1，判断array[begin] + array[end] 与n的大小关系，如果相等，则找到；如果小于，则begin++，如果大于，则end--，然后继续做前面判断。这样基本上效率能最快了，因为是O（n）。
问：不用第三个参数调换整数a和b
他问了之后我就说这题我会，说真的，这题要是之前不知道，要在面试的时候想出来基本不可能。要用异或操作符来做：
a = a^b;
b = a^b;
a = a^b;
然后用a= 101,b = 111测试了一下，根据上面操作a = 010;b = 101; a = 111正确。
问：堆栈区别
说了一下四点：
1）栈是连续的，堆是不连续的；2）栈元素自动释放，堆元素要手动释放；3）栈从高地址开始存储向下增长，堆相反；4）存储读取效率上栈比堆快。
接下来他看了我的笔试题试卷，主要是讨论最后一道题：如下
情景：新浪微博发布内容要求字符不超过140，但是用户如果在发布内容中有很长的url时，会认为是很多字符。所以新浪上发布内容包含一个URL时，时把他压缩成一个TinyURL（缩小）。比如：
输入：http://zhidao.baidu.com/search?ct=17&pn=0&tn=ikaslist&rn=10&word=helloworld&ie=utf-8&fr=wwwt
实际显示：http://asdfa.cn/ak78ss。（这里我只是随便举了个例子）
前面asdfa.cn是对应域名 zhidao.baidu.com，后面长长的字符串被压缩成ak78ss。
现在让你来设计TinyURL的实现，一下问题要怎么设计：
问题一：域名后面的编码如何实现？
问题二：对于已经映射过的一个URL，怎么查找已存在的TinyUrl？
问题三：有10亿个url，一个服务上存不下，需要多台服务器，怎么设计实现？
问了一个问题，说你觉得让你来设计这样一个服务，最大的问题是什么？我说是tinyurl的hash表存储，因为数据量真的非常大。他问那你要怎么存储，我说要用二次哈希吧，先根据hash值存储到对应的服务器上面，再进行hash存储。
接着他问我试卷上memcpy怎么没写？我说我当时对这个函数不了解。他叫我现在做一下这个题。我就不贴代码了，写得太烂，他说要在复制的时候考虑内存溢出问题。有兴趣的可以网上找实现代码。
后面是一道概率问题，一个山区的村子，生孩子直到生了一个男孩为止。题目就不多说了，网上不久有这道原题么？但我之前根本没看答案。所以我一开始在纸上一个劲地计算，最后发现计算不出来之后，我给了他这样的答案，说我觉得是1:1。为什么？因为生男生女概率本来就都是二分之一，无论定义怎么的规则生孩子，生男生女概率就是不会变，所以数量多了之后男女比例是1:1。我不知道他是否想要这样的答案，但我觉得我当时挺机智的。他说原理是什么呢？我说，当数量足够大的时候，概率比就是数量比。随后他爽快地说：去二面吧！