百度面试题集锦

        1.实现一个函数，对一个正整数n，算得到1需要的最少操作次数。操作规则为：如果n为偶数，将其除以2；如果n为奇数，可以加1或减1；一直处理下去。

礼仪

求职信息

        例子：

面试网

func(7) = 4，可以证明最少需要4次运算
n = 7
n-1 6
n/2 3
n-1 2
n/2 1 求职面试

        要求：实现函数(实现尽可能高效) int func(unsign int n)；n为输入，返回最小的运算次数。给出思路(文字描述)，完成代码，并分析你算法的时间复杂度。

礼仪

        答： 面试问题

qzm4

[cpp] view plaincopy
int func(unsigned int n) 
{ 
    if(n == 1) 
        return 0; 
    if(n % 2 == 0) 
        return 1 func(n/2); 
    int x = func(n 1); 
    int y = func(n - 1); 
    if(x > y) 
        return y 1; 
    else 
        return x 1; 
}  求职面试

        假设n表示成二进制有x bit，可以看出计算复杂度为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操作。

qzm4

面试问题

        **如果最后有更多的连续1，也应该选择 1操作。

面试问题

        如果最后剩下的各位都是1，则有11时应该选择-1；111时 1和-1相同；1111时应选择 1；大于四个1时也应该选择 1；

求职信息

求职信息

[cpp] view plaincopy
int func(unsigned int n) 
{ 
    if(n == 1) 
        return 0; 
    if(n % 2 == 0) 
        return 1 func(n/2); 
    if(n == 3) 
        return 2; 
    if(n&2) 
        return 1 func(n 1); 
    else 
        return 1 func(n-1); 
} 

 
        由以上的分析可知，奇数的时候加1或减1，完全取决于二进制的后两位，如果后两位是10、00那么肯定是偶数，选择除以2，如果后两位是01、11，那么选择结果会不一样的，如果是*****01，那么选择减1，如果是*****11，那么选择加1，特殊情况是就是n是3的时候，选择减1操作。 求职信息

        非递归代码如下：

求职信息

面试网

[cpp] view plaincopy
// 非递归写法 
int func(int n) 
{ 
    int count = 0; 
    while(n > 1) 
    { 
        if(n % 2 == 0) 
            n >>= 1; 
        else if(n == 3) 
            n--; 
        else 
        { 
            if(n&2)      // 二进制是******11时 
                n ; 
            else         // 二进制是******01时  面试问题
                n--; 
        } 
        count ; 
    } 
    return count; 
} 
另外一种写法如下：
[cpp] view plaincopy
// 非递归写法 
int func(int n) 
{ 
    int count = 0; 
    while(n > 1) 
    { 
        if(n % 2 == 0)            // n % 4等于0或2 
            n >>= 1; 
        else if(n == 3) 
            n--; 
        else  qzm4
            n = (n % 4 - 2);     // n % 4等于1或3 
        count ; 
    } 
    return count; 
} 

求职信息

        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.判断两棵树是否相等，请实现两棵树是否相等的比较，相等返回1，否则返回其他值，并说明算法复杂度。 礼仪

面试问题

        数据结构为： qzm4

[cpp] view plaincopy
typedef struct TreeNode 
{ 
    char c; 
    TreeNode *leftchild; 
    TreeNode *rightchild; 
}TreeNode; 

        函数接口为：int CompTree(TreeNode* tree1,TreeNode* tree2);

求职信息

        注：A、B两棵树相等当且仅当RootA->c==RootB-->c,而且A和B的左右子树相等或者左右互换相等。

礼仪

        递归方法：

求职信息

[cpp] view plaincopy
bool CompTree(TreeNode *tree1, TreeNode *tree2) 
{ 
    if(tree1 == NULL && tree2 == NULL) 
        return true; 
    if(tree1 == NULL || tree2 == NULL) 
        return false; 
    if(tree1->c != tree2->c) 
        return false; 
    if( (CompTree(tree1->leftchild, tree2->leftchild) && CompTree(tree1->rightchild, tree2->rightchild)) || CompTree(tree1->leftchild, tree2->rightchild) && CompTree(tree1->rightchild, tree2->leftchild)) 
        return true; 
} 

        时间复杂度：

         在树的第0层，有1个节点，我们会进行1次函数调用；
         在树的第1层，有2个节点，我们可能会进行4次函数调用；
         在树的第2层，有4个节点，我们可能会进行16次函数调用；
         ....
         在树的第x层，有2^x个节点，我们可能会进行(2^x)^2次函数调用； 面试网

        所以假设总节点数为n，则算法的复杂度为O(n^2)。

        4.一个大的含有50M个URL的记录，一个小的含有500个URL的记录，找出两个记录里相同的URL。 面试网

        回答： 面试网

        首先使用包含500个url的文件创建一个hash_set。

qzm4

面试网

        然后遍历50M的url记录，如果url在hash_set中，则输出此url并从hash_set中删除这个url。
求职信息

礼仪

        所有输出的url就是两个记录里相同的url。 求职信息

求职面试

        5.蚂蚁爬杆问题

面试问题

    　有一根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 求职信息

        6.海量日志数据，提取出某日访问百度次数最多的那个IP。

礼仪

        回答： 面试问题

        如果日志文件足够的大，大到不能完全加载到内存中的话。

面试网

     求职信息

        那么可以考虑分而治之的策略，按照IP地址的hash(IP)%1024值，将海量日志存储到1024个小文件中。每个小文件最多包含4M个IP地址。

面试问题

        对于每个小文件，可以构建一个IP作为key，出现次数作为value的hash_map，并记录当前出现次数最多的1个IP地址。

面试问题

        有了1024个小文件中的出现次数最多的IP，我们就可以轻松得到总体上出现次数最多的IP。 求职信息

        7.有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。 qzm4

    　3）对2）中获得的10个文件进行归并排序，并将最终结果输出到文件中。

面试网

        8.当在浏览器中输入一个url后回车，后台发生了什么？比如输入url后，你看到了百度的首页，那么这一切是如何发生的呢？ 求职面试

        回答：

　　简单来说有以下步骤： 面试问题

　　1)查找域名对应的IP地址。这一步会依次查找浏览器缓存，系统缓存，路由器缓存，ISPDNS缓存，根域名服务器。
　　2)向IP对应的服务器发送请求。
　　3)服务器响应请求，发回网页内容。
　　4)浏览器解析网页内容。 qzm4

        当然，由于网页可能有重定向，或者嵌入了图片，AJAX，其它子网页等等，这4个步骤可能反复进行多次才能将最终页面展示给用户。

qzm4

声明：百度面试题集锦来源于互联网，其版权均归原作者及其网站所有，本站虽力求保存原有的版权信息，但由于诸多原因，可能导致无法确定其真实来源，如果您对本站文章、图片资源的归属存有异议，请立即通知我们，情况属实，我们会第一时间予以删除，并同时向您表示歉意！