百度软件工程师面试题大全

第第页百度软件工程师面试题大全

百度软件工程师面试题大全

发表于：2023-03-15来源：未知：seanhe点击数：标签：

百度软件工程师面试题大全

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]viewplaincopyintfunc(unsignedintn)

{

if(n==1)

return0;

if(n%2==0)

return1+func(n/2);

intx=func(n+1);

inty=func(n-1);

if(xy)

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]viewplaincopyintfunc(unsignedintn)

{

if(n==1)

return0;

if(n%2==0)

return1+func(n/2);

if(n==3)

return2;

if(n2)

return1+func(n+1);

else

return1+func(n-1);

}

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、海量日志数据，提取出某日访问百度次数最多的那个IP。

回答：

IP地址最多有2^32=4G种取值可能，所以不能完全加载到内存中。

可以考虑分而治之的策略，按照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

所有蚂蚁都离开木杆的最大