百度面试题集锦.docx
《百度面试题集锦.docx》由会员分享，可在线阅读，更多相关《百度面试题集锦.docx（17页珍藏版）》请在冰点文库上搜索。
XX面试题集锦
XX最新面试题集锦
1、实现一个函数，对一个正整数n，算得到1需要的最少操作次数。
操作规则为：
如果n为偶数，将其除以2；如果n为奇数，可以加1或减1；一直处理下去。
例子：
func（7）=4，可以证明最少需要4次运算
n=7
n-16
n/23
n-12
n/21
要求：
实现函数（实现尽可能高效）intfunc（unsignintn）；n为输入，返回最小的运算次数。
给出思路（文字描述），完成代码，并分析你算法的时间复杂度。
答：
[cpp]viewplaincopyprint?
1.int func（unsigned int n）
2.{
3. if（n == 1）
4. return 0;
5. if（n % 2 == 0）
6. return 1 + func（n/2）;
7. int x = func（n + 1）;
8. int y = func（n - 1）;
9. if（x > y）
10. return y+1;
11. else
12. return x+1;
13.}
intfunc（unsignedintn）
{
if（n==1）
return0;
if（n%2==0）
return1+func（n/2）;
intx=func（n+1）;
inty=func（n-1）;
if（x>y）
returny+1;
else
returnx+1;
}
假设n表示成二进制有xbit，可以看出计算复杂度为O（2^x），也就是O（n）。
将n转换到二进制空间来看（比如7为111，6为110）：
-如果最后一位是0，则对应于偶数，直接进行除2操作。
-如果最后一位是1，情况则有些复杂。
**如果最后几位是?
?
?
01，则有可能为?
?
?
001，?
?
?
1111101。
在第一种情况下，显然应该-1；在第二种情况下-1和+1最终需要的步数相同。
所以在?
?
?
01的情况下，应该选择-1操作。
**如果最后几位是?
?
?
011，则有可能为?
?
?
0011，?
?
?
11111011。
在第一种情况下，+1和-1最终需要的步数相同；在第二种情况下+1步数更少些。
所以在?
?
?
011的情况下，应该选择+1操作。
**如果最后有更多的连续1，也应该选择+1操作。
如果最后剩下的各位都是1，则有11时应该选择-1；111时+1和-1相同；1111时应选择+1；大于四个1时也应该选择+1；
[cpp]viewplaincopyprint?
1.int func（unsigned int n）
2.{
3. if（n == 1）
4. return 0;
5. if（n % 2 == 0）
6. return 1 + func（n/2）;
7. if（n == 3）
8. return 2;
9. if（n&2）
10. return 1 + func（n+1）;
11. else
12. return 1 + func（n-1）;
13.}
intfunc（unsignedintn）
{
if（n==1）
return0;
if（n%2==0）
return1+func（n/2）;
if（n==3）
return2;
if（n&2）
return1+func（n+1）;
else
return1+func（n-1）;
}
由以上的分析可知，奇数的时候加1或减1，完全取决于二进制的后两位，如果后两位是10、00那么肯定是偶数，选择除以2，如果后两位是01、11，那么选择结果会不一样的，如果是*****01，那么选择减1，如果是*****11，那么选择加1，特殊情况是就是n是3的时候，选择减1操作。
非递归代码如下：
[cpp]viewplaincopyprint?
1.// 非递归写法
2.int func（int n）
3.{
4. int count = 0;
5. while（n > 1）
6. {
7. if（n % 2 == 0）
8. n >>= 1;
9. else if（n == 3）
10. n--;
11. else
12. {
13. if（n&2） // 二进制是******11时
14. n++;
15. else // 二进制是******01时
16. n--;
17. }
18. count++;
19. }
20. return count;
21.}
//非递归写法
intfunc（intn）
{
intcount=0;
while（n>1）
{
if（n%2==0）
n>>=1;
elseif（n==3）
n--;
else
{
if（n&2）//二进制是******11时
n++;
else//二进制是******01时
n--;
}
count++;
}
returncount;
}
另外一种写法如下：
[cpp]viewplaincopyprint?
1.// 非递归写法
2.int func（int n）
3.{
4. int count = 0;
5. while（n > 1）
6. {
7. if（n % 2 == 0） // n % 4等于0或2
8. n >>= 1;
9. else if（n == 3）
10. n--;
11. else
12. n += （n % 4 - 2）; // n % 4等于1或3
13. count++;
14. }
15. return count;
16.}
//非递归写法
intfunc（intn）
{
intcount=0;
while（n>1）
{
if（n%2==0）//n%4等于0或2
n>>=1;
elseif（n==3）
n--;
else
n+=（n%4-2）;//n%4等于1或3
count++;
}
returncount;
}
2、找到满足条件的数组
给定函数d（n）=n+n的各位之和，n为正整数，如d（78）=78+7+8=93。
这样这个函数可以看成一个生成器，如93可以看成由78生成。
定义数A：
数A找不到一个数B可以由d（B）=A，即A不能由其他数生成。
现在要写程序，找出1至10000里的所有符合数A定义的数。
回答：
申请一个长度为10000的bool数组，每个元素代表对应的值是否可以有其它数生成。
开始时将数组中的值都初始化为false。
由于大于10000的数的生成数必定大于10000，所以我们只需遍历1到10000中的数，计算生成数，并将bool数组中对应的值设置为true，表示这个数可以有其它数生成。
最后bool数组中值为false的位置对应的整数就是不能由其它数生成的。
3、一个大的含有50M个URL的记录，一个小的含有500个URL的记录，找出两个记录里相同的URL。
回答：
首先使用包含500个url的文件创建一个hash_set。
然后遍历50M的url记录，如果url在hash_set中，则输出此url并从hash_set中删除这个url。
所有输出的url就是两个记录里相同的url。
4、海量日志数据，提取出某日访问XX次数最多的那个IP。
回答：
如果日志文件足够的大，大到不能完全加载到内存中的话。
那么可以考虑分而治之的策略，按照IP地址的hash（IP）%1024值，将海量日志存储到1024个小文件中。
每个小文件最多包含4M个IP地址。
对于每个小文件，可以构建一个IP作为key，出现次数作为value的hash_map，并记录当前出现次数最多的1个IP地址。
有了1024个小文件中的出现次数最多的IP，我们就可以轻松得到总体上出现次数最多的IP。
5、有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。
如何按照query的频度排序？
回答：
1）读取10个文件，按照hash（query）%10的结果将query写到对应的文件中。
这样我们就有了10个大小约为1G的文件。
任意一个query只会出现在某个文件中。
2）对于1）中获得的10个文件，分别进行如下操作
-利用hash_map（query，query_count）来统计每个query出现的次数。
-利用堆排序算法对query按照出现次数进行排序。
-将排序好的query输出的文件中。
这样我们就获得了10个文件，每个文件中都是按频率排序好的query。
3）对2）中获得的10个文件进行归并排序，并将最终结果输出到文件中。
6、蚂蚁爬杆问题
有一根27厘米长的细木杆，在第3厘米，7厘米，11厘米，17厘米，23厘米这五个位置上各有一只蚂蚁，木杆很细，不能同时通过两只蚂蚁，开始时，蚂蚁的头朝向左还是右是任意的，他们只会朝前走或掉头，但不会后退，当两只蚂蚁相遇后，蚂蚁会同时掉头朝反方向走，假设蚂蚁们每秒钟可以走1厘米的距离。
求所有蚂蚁都离开木杆的最小时间和最大时间。
答案：
两只蚂蚁相遇后，各自掉头朝相反方向走。
如果我们不考虑每个蚂蚁的具体身份，这和两只蚂蚁相遇后，打个招呼继续向前走没有什么区别。
所有蚂蚁都离开木杆的最小时间为
max（min（3,27-3）,min（7,27-7）,min（11,27-11）,min（17,27-17）,min（23,27-23））=11
所有蚂蚁都离开木杆的最大时间为
max（max（3,27-3）,max（7,27-7）,max（11,27-11）,max（17,27-17）,max（23,27-23））=24
7、当在浏览器中输入一个url后回车，后台发生了什么？
比如输入url后，你看到了XX的首页，那么这一切是如何发生的呢？
回答：
简单来说有以下步骤：
1、查找域名对应的IP地址。
这一步会依次查找浏览器缓存，系统缓存，路由器缓存，ISPDNS缓存，根域名服务器。
2、向IP对应的服务器发送请求。
3、服务器响应请求，发回网页内容。
4、浏览器解析网页内容。
当然，由于网页可能有重定向，或者嵌入了图片，AJAX，其它子网页等等，这4个步骤可能反复进行多次才能将最终页面展示给用户。
8、判断两棵树是否相等，请实现两棵树是否相等的比较，相等返回1，否则返回其他值，并说明算法复杂度。
数据结构为：
[cpp]viewplaincopyprint?
1.typedef struct TreeNode
2.{
3. char c;
4. TreeNode *leftchild;
5. TreeNode *rightchild;
6.}TreeNode;
typedefstructTreeNode
{
charc;
TreeNode*leftchild;
TreeNode*rightchild;
}TreeNode;
函数接口为：
intCompTree（TreeNode*tree1,TreeNode*tree2）;
注：
A、B两棵树相等当且仅当RootA->c==RootB-->c,而且A和B的左右子树相等或者左右互换相等。
递归方法：
[cpp]viewplaincopyprint?
1.bool CompTree（TreeNode *tree1, TreeNode *tree2）
2.{
3. if（tree1 == NULL && tree2 == NULL）
4. return true;
5. if（tree1 == NULL || tree2 == NULL）
6. return false;
7. if（tree1->c !
= tree2->c）
8. return false;
9. if（ （CompTree（tree1->leftchild, tree2->leftchild） && CompTree（tree1->rightchild, tree2->rightchild）） || CompTree（tree1->leftchild, tree2->rightchild） && CompTree（tree1->rightchild, tree2->leftchild））
10. return true;
11.}
boolCompTree（TreeNode*tree1,TreeNode*tree2）
{
if（tree1==NULL&&tree2==NULL）
returntrue;
if（tree1==NULL||tree2==NULL）
returnfalse;
if（tree1->c!
=tree2->c）
returnfalse;
if（（CompTree（tree1->leftchild,tree2->leftchild）&&CompTree（tree1->rightchild,tree2->rightchild））||CompTree（tree1->leftchild,tree2->rightchild）&&CompTree（tree1->rightchild,tree2->leftchild））
returntrue;
}
时间复杂度：
在树的第0层，有1个节点，我们会进行1次函数调用；
在树的第1层，有2个节点，我们可能会进行4次函数调用；
在树的第2层，有4个节点，我们可能会进行16次函数调用；
....
在树的第x层，有2^x个节点，我们可能会进行（2^x）^2次函数调用；
所以假设总节点数为n，则算法的复杂度为O（n^2）。
腾讯面试题：
求一个论坛的在线人数，假设有一个论坛，其注册ID有两亿个，每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间，要求写一个算法统计一天中论坛的用户在线分布，取样粒度为秒。
回答：
一天总共有3600*24=86400秒。
定义一个长度为86400的整数数组intdelta[86400]，每个整数对应这一秒的人数变化值，可能为正也可能为负。
开始时将数组元素都初始化为0。
然后依次读入每个用户的登录时间和退出时间，将与登录时间对应的整数值加1，将与退出时间对应的整数值减1。
这样处理一遍后数组中存储了每秒中的人数变化情况。
定义另外一个长度为86400的整数数组intonline_num[86400]，每个整数对应这一秒的论坛在线人数。
假设一天开始时论坛在线人数为0，则第1秒的人数online_num[0]=delta[0]。
第n+1秒的人数online_num[n]=online_num[n-1]+delta[n]。
这样我们就获得了一天中任意时间的在线人数。
9、三个警察和三个囚徒的过河问题
三个警察和三个囚徒共同旅行。
一条河挡住了去路，河边有一条船，但是每次只能载2人。
存在如下的危险：
无论在河的哪边，当囚徒人数多于警察的人数时，将有警察被囚徒杀死。
问题：
请问如何确定渡河方案，才能保证6人安全无损的过河。
答案：
第一次：
两囚徒同过，回一囚徒
第二次：
两囚徒同过，回一囚徒
第三次：
两警察同过，回一囚徒一警察（此时对岸还剩下一囚徒一警察，是安全状态）
第四次：
两警察同过，回一囚徒（此时对岸有3个警察，是安全状态）
第五次：
两囚徒同过，回一囚徒
第六次：
两囚徒同过；over
10、从300万字符串中找到最热门的10条
搜索的输入信息是一个字符串，统计300万输入信息中的最热门的前10条，我们每次输入的一个字符串为不超过255byte，内存使用只有1G。
请描述思想，写出算法（c语言），空间和时间复杂度。
答案：
300万个字符串最多（假设没有重复，都是最大长度）占用内存3M*1K/4=0.75G。
所以可以将所有字符串都存放在内存中进行处理。
可以使用key为字符串（事实上是字符串的hash值），值为字符串出现次数的hash来统计每个每个字符串出现的次数。
并用一个长度为10的数组/链表来存储目前出现次数最多的10个字符串。
这样空间和时间的复杂度都是O（n）。
11、如何找出字典中的兄弟单词。
给定一个单词a，如果通过交换单词中字母的顺序可以得到另外的单词b，那么定义b是a的兄弟单词。
现在给定一个字典，用户输入一个单词，如何根据字典找出这个单词有多少个兄弟单词？
答案：
使用hash_map和链表。
首先定义一个key，使得兄弟单词有相同的key，不是兄弟的单词有不同的key。
例如，将单词按字母从小到大重新排序后作为其key，比如bad的key为abd，good的key为dgoo。
使用链表将所有兄弟单词串在一起，hash_map的key为单词的key，value为链表的起始地址。
开始时，先遍历字典，将每个单词都按照key加入到对应的链表当中。
当需要找兄弟单词时，只需求取这个单词的key，然后到hash_map中找到对应的链表即可。
这样创建hash_map时时间复杂度为O（n），查找兄弟单词时时间复杂度是O
（1）。
12、找出数组中出现次数超过一半的数，现在有一个数组，已知一个数出现的次数超过了一半，请用O（n）的复杂度的算法找出这个数。
答案1：
创建一个hash_map，key为数组中的数，value为此数出现的次数。
遍历一遍数组，用hash_map统计每个数出现的次数，并用两个值存储目前出现次数最多的数和对应出现的次数。
这样可以做到O（n）的时间复杂度和O（n）的空间复杂度，满足题目的要求。
但是没有利用“一个数出现的次数超过了一半”这个特点。
也许算法还有提高的空间。
答案2：
使用两个变量A和B，其中A存储某个数组中的数，B用来计数。
开始时将B初始化为0。
遍历数组，如果B=0，则令A等于当前数，令B等于1；如果当前数与A相同，则B=B+1；如果当前数与A不同，则令B=B-1。
遍历结束时，A中的数就是要找的数。
这个算法的时间复杂度是O（n），空间复杂度为O
（1）。
13、找出被修改过的数字
n个空间（其中n<1M），存放a到a+n-1的数，位置随机且数字不重复，a为正且未知。
现在第一个空间的数被误设置为-1。
已经知道被修改的数不是最小的。
请找出被修改的数字是多少。
例如：
n=6，a=2，原始的串为5,3,7,6,2,4。
现在被别人修改为-1,3,7,6,2,4。
现在希望找到5。
回答：
由于修改的数不是最小的，所以遍历第二个空间到最后一个空间可以得到a的值。
a到a+n-1这n个数的和是total=na+（n-1）n/2。
将第二个至最后一个空间的数累加获得sub_total。
那么被修改的数就是total-sub_total。
14、设计DNS服务器中cache的数据结构。
要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快。
（题目还给出了一系列的数据，比如：
站点数总共为5000万，IP地址有1000万，等等）
回答：
DNS服务器实现域名到IP地址的转换。
每个域名的平均长度为25个字节（估计值），每个IP为4个字节，所以Cache的每个条目需要大概30个字节。
总共50M个条目，所以需要1.5G个字节的空间。
可以放置在内存中。
（考虑到每秒5000次操作的限制，也只能放在内存中。
）
可以考虑的数据结构包括hash_map，字典树，红黑树等等。
15、找出给定字符串对应的序号。
序列Seq=[a,b,…z,aa,ab…az,ba,bb,…bz,…,za,zb,…zz,aaa,…]类似与excel的排列，任意给出一个字符串s=[a-z]+（由a-z字符组成的任意长度字符串），请问s是序列Seq的第几个。
回答：
注意到每满26个就会向前进一位，类似一个26进制的问题。
比如ab，则位置为26*1+2；
比如za，则位置为26*26+1；
比如abc，则位置为26*26*1+26*2+3；
16、找出第k大的数字所在的位置。
写一段程序，找出数组中第k大小的数，输出数所在的位置。
例如{2，4，3，4，7}中，第一大的数是7，位置在4。
第二大、第三大的数都是4，位置在1、3随便输出哪一个均可。
答案：
先找到第k大的数字，然后再遍历一遍数组找到它的位置。
所以题目的难点在于如何最高效的找到第k大的数。
我们可以通过快速排序，堆排序等高效的排序算法对数组进行排序，然后找到第k大的数字。
这样总体复杂度为O（NlogN）。
我们还可以通过二分的思想，找到第k大的数字，而不必对整个数组排序。
从数组中随机选一个数t，通过让这个数和其它数比较，我们可以将整个数组分成了两部分并且满足，{x,xx,...,t}<{y,yy,...}。
在将数组分成两个数组的过程中，我们还可以记录每个子数组的大小。
这样我们就可以确定第k大的数字在哪个子数组中。
然后我们继续对包含第k大数字的子数组进行同样的划分，直到找到第k大的数字为止。
平均来说，由于每次划分都会使子数组缩小到原来1/2，所以整个过程的复杂度为O（N）。
17、给40亿个不重复的unsignedint的整数，没排过序的，然后再给几个数
升级会员 