百度校园招聘笔试题目.docx
《百度校园招聘笔试题目.docx》由会员分享，可在线阅读，更多相关《百度校园招聘笔试题目.docx（6页珍藏版）》请在冰点文库上搜索。
XX校园招聘笔试题目
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为第二种情况下-1和+1最终需要的步数相同。
所以在?
?
?
01的情况下，应该选择-1操作。
**如果最后几位是?
?
?
011，则有可能为?
?
?
0011，?
?
?
11111011。
在第一种情况下，+1和-1最终需要的步数相同；在第二种情况下+1步数更少些。
所以在?
?
?
011的情况下，应该选择+1操作。
**如果最后有更多的连续1，也应该选择+1操作。
如果最后剩下的各位都是1，则有11时应该选择-1；111时+1和-1相同；1111时应选择+1；大于四个1时也应该选择+1；
由以上的分析可知，奇数的时候加1或减1，完全取决于二进制的后两位，如果后两位是10、00那么肯定是偶数，选择除以2，如果后两位是01、11，那么选择结果会不一样的，如果是*****01，那么选择减1，如果是*****11，那么选择加1，特殊情况是就是n是3的时候，选择减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、海量日志数据，提取出某日访问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
升级会员 