最新九月百度人搜，阿里巴巴，腾讯华为京东360笔试面试二十题

引言

    自发表上一篇文章至今（事实上，上篇文章更新了近3个月之久），blog已经停了3个多月，而在那之前，每月都不曾断过。正如上一篇文章支持向量机通俗导论（理解SVM的三层境界）末尾所述：”额，blog许久未有更新了，因为最近实在忙，无暇顾及blog。“与此同时，工作之余，也在一直闲心研究学习数据挖掘："神经网络将可能作为Top 10 Algorithms in Data Mining之番外篇第1篇，同时，k-最近邻法(k-nearest neighbor，kNN)算法谈到kd树将可能作为本系列第三篇。这是此系列接下来要写的两个算法，刚好项目中也要用到KD树“。

    但很显然，若要等到下一篇数据挖掘系列的文章时，说不定要到年底去了，而最近的这段时间，9月，正是各种校招/笔试/面试火热的时节，自己则希望能帮助到这些找工作的朋友，故此，怎能无动于衷，所以，3个多月后，blog今天更新了。

    再者，虽然如我的这条微博：http://weibo.com/1580904460/yzs72mmFZ所述，blog自10年10月开通至11年10月，一年的时间内整理了300多道面试题(这300道题全部集锦在此文中第一部分：http://blog.csdn.net/v_july_v/article/details/6543438)。但毕竟那些题已经是前年或去年的了，笔试面试题虽然每年类型变化不大，但毕竟它年年推陈出新，存着就有其合理性。

    OK，以下是整理自8月下旬至9月中旬各大公司的笔试面试二十题，相信一定能给正在参加各种校招的诸多朋友多少帮助，学习参考或借鉴（当然，你手头上若有好的笔试/面试题，欢迎通过微博私信：http://weibo.com/julyweibo，或邮箱：[e-mail]发给我，或者干脆直接评论在本文下，再者，如果你对以下任何一题有任何看法.想法.思路或建议，欢迎留言评论，大家一起讨论，享受思考的乐趣）。

九月百度人搜，阿里巴巴，腾讯华为京东笔/面试二十题

1. 9月11日， 京东：

   谈谈你对面向对象编程的认识

2. 8月20日，金山面试，题目如下：
       数据库1中存放着a类数据，数据库2中存放着以天为单位划分的表30张（比如table_20110909,table_20110910,table_20110911）,总共是一个月的数据。表1中的a类数据中有一个字段userid来唯一判别用户身份，表2中的30张表（每张表结构相同）也有一个字段userid来唯一识别用户身份。如何判定a类数据库的多少用户在数据库2中出现过？
   来源：http://topic.csdn.net/u/20120820/23/C6B16CCF-EE15-47C0-9B15-77497291F2B9.html。
   
3. 百度实习笔试题（2012.5.6）
     简答题1
   一个单词单词字母交换，可得另一个单词，如army->mary，成为兄弟单词。提供一个单词，在字典中找到它的兄弟。描述数据结构和查询过程。
     简答题2
   线程和进程区别和联系。什么是“线程安全”
   简答题3
   C和C++怎样分配和释放内存，区别是什么
     算法题1
   一个url指向的页面里面有另一个url,最终有一个url指向之前出现过的url或空，这两种情形都定义为null。这样构成一个单链表。给两条这样单链表，判断里面是否存在同样的url。url以亿级计，资源不足以hash。
     算法题2
   数组al[0,mid-1] 和 al[mid,num-1]，都分别有序。将其merge成有序数组al[0,num-1]，要求空间复杂度O(1)
     系统设计题
   百度搜索框的suggestion,比如输入北京，搜索框下面会以北京为前缀，展示“北京爱情故事”、“北京公交”、“北”等等搜索词。
   如何设计使得空间和时间复杂度尽量低。
   
4. 人搜笔试
1. 快排每次以第一个作为主元，问时间复杂度是多少？（O(N*logN)）
  2. T(N) = N + T(N/2)+T(2N), 问T(N)的时间复杂度是多少？（O(N)）
  3. 从（0,1）中平均随机出几次才能使得和超过1？（e）
  4.编程题：
 一棵树的节点定义格式如下：
 struct Node{
    Node* parent;
    Node* firstChild; // 孩子节点
    Node* sibling; // 兄弟节点 
}
要求非递归遍历该树。
思路：采用队列存储，来遍历节点。
  5. 算法题：
有N个节点，每两个节点相邻，每个节点只与2个节点相邻，因此，N个顶点有N-1条边。每一条边上都有权值wi，定义节点i到节点i+1的边为wi。
求：不相邻的权值和最大的边的集合。
5. 2011，人搜面试，所投职位：搜索研发工程师：面试题回忆 
        1、删除字符串开始及末尾的空白符，并且把数组中间的多个空格（如果有）符转化为1个。
        2、求数组（元素可为正数、负数、0）的最大子序列和。 
        3、链表相邻元素翻转，如a->b->c->d->e->f-g，翻转后变为：b->a->d->c->f->e->g 
        4、链表克隆。链表的结构为： 
        typedef struct list { 
            int data; //数据字段 
        list *middle; //指向链表中某任意位置元素(可指向自己)的指针 
        list *next;//指向链表下一元素 
        } list; 
        5、100万条数据的数据库查询速度优化问题，解决关键点是：根据主表元素特点，把主表拆分并新建副表，并且利用存储过程保证主副表的数据一致性。（不用写代码） 
        6、求正整数n所有可能的和式的组合（如；4=1+1+1+1、1+1+2、1+3、2+1+1、2+2） 
        7、求旋转数组的最小元素（把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。） 
        8、找出两个单链表里交叉的第一个元素 
        9、字符串移动（字符串为*号和26个字母的任意组合，把*号都移动到最左侧，把字母移到最右侧并保持相对顺序不变），要求时间和空间复杂度最小 
        10、时间复杂度为O(1)，怎么找出一个栈里的最大元素   
        11、线程、进程区别 
        12、static在C和C++里各代表什么含义 
        13、const在C/C++里什么意思 
        14、常用linux命令 
        15、解释Select/Poll模型 
6. 百度，网易，阿里巴巴等面试题：http://blog.csdn.net/hopeztm/article/category/1201028；
   
7. 8月30日，网易有道面试题
   var tt = 'aa';
   function test()
   {
     alert(tt);
     var tt = 'dd';
     alert(tt);
   }
   test();  
   
8. 8月31日，百度面试题：不使用随机数的洗牌算法，详情：http://topic.csdn.net/u/20120831/10/C837A419-DFD4-4326-897C-669909BD2086.html；
   
9. 9月6日，阿里巴巴面试：
   1、介绍一下你自己。
   2、介绍一下你认为做的最好的一个项目。
   3、请用五分钟的时间把你做的项目的流程图画一下。
   4、项目中你遇到的难点是什么？怎么解决的？
   5、项目中你认为哪个技术是你最拿手的？
   6、介绍一下HTTP协议
   7、如何把一个大的日志文件哈希到不同的哈希表中，这些哈希表的存储格式是什么？
   8、linux网络编程，画一个c/s通信的流程
   9、多线程了解多少，做过的项目中有没有用到过？
   10、描述一下动态规划的思想
   11、快排。
   12、内存分配方式有哪几种？代码段放在哪个内存区？static int a[1024][1024][1024]放在哪个区？会不会有异常？
   13、如何表示图？
   14、如何验证图的连通性？
   15、对互联网的业务和技术是否关注？
   
10. 9月7日，一道华为上机题：
    题目描述: 选秀节目打分，分为专家评委和大众评委，score[] 数组里面存储每个评委打的分数，judge_type[] 里存储与 score[] 数组对应的评委类别，judge_type == 1，表示专家评委，judge_type == 2，表示大众评委，n表示评委总数。打分规则如下：专家评委和大众评委的分数先分别取一个平均分（平均分取整），然后，总分 = 专家评委平均分 * 0.6 + 大众评委 * 0.4，总分取整。如果没有大众评委，则 总分 = 专家评委平均分，总分取整。函数最终返回选手得分。
    函数接口 int cal_score(int score[], int judge_type[], int n)  
     上机题目需要将函数验证，但是题目中默认专家评委的个数不能为零，但是如何将这种专家数目为0的情形排除出去。
    来源：http://topic.csdn.net/u/20120907/15/c30eead8-9e49-41c2-bd11-c277030ad17a.html；
    
11. 9月8日，腾讯面试题：
    假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配，
     比如：abcda和adabc,由于出现的字符个数都是相同，只是顺序不同，
     所以这两个字符串是匹配的。要求高效！
    我想，你们能想到的，这篇blog里：http://blog.csdn.net/v_JULY_v/article/details/6347454都已经有了。
12. 阿里云，搜索引擎中5亿个url怎么高效存储；
    
13. 创新工场微博，前几天才发布的难道不少人的的牛题：http://t.qq.com/iwrecruiting?pgv_ref=im.WBlog.guest&ptlang=2052；

14. 4**9 的笔试题，比较简单：
    1.求链表的倒数第二个节点
    2.有一个整数数组，求数组中第二大的数

15.  阿里巴巴二道题
    第一道：
    对于给定的整数集合S，求出最大的d，使得a+b+c=d。a,b,c,d互不相同，且都属于S。集合的元素个数小于等于2000个，元素的取值范围在[]，假定可用内存空间为100MB，硬盘使用空间无限大，试分析时间和空间复杂度，找出最快的解决方法。
    阿里巴巴第二道(研发类)
    笔试题1，原题大致描述有一大批数据，百万级别的。数据项内容是：用户ID、科目ABC各自的成绩。其中用户ID为0~1000万之间，且是连续的，可以唯一标识一条记录。科目ABC成绩均在0~100之间。有两块磁盘，空间大小均为512M，内存空间64M。
    1) 为实现快速查询某用户ID对应的各科成绩，问磁盘文件及内存该如何组织；
    2) 改变题目条件，ID为0~10亿之间，且不连续。问磁盘文件及内存该如何组织；
    3) 在问题2的基础上，增加一个需求。在查询各科成绩的同时，获取该用户的排名，问磁盘文件及内存该如何组织。
    笔试题2：代码实现计算字符串的相似度。 
16. 9月11日，京东全套笔试题：
17. 群友壮壮在我的算法群里贴了如下一个图（而它就是我写的编程艺术系列第一章左旋转字符串：http://blog.csdn.net/v_JULY_v/article/details/6322882的题）：
    上面文章来源：http://www.cnblogs.com/bakari/archive/2012/09/09/2677155.html。当然，有些书上也收录过此题，并给出了与我思路类似的解答，如下图所示：
    

18. 360PHP笔试全套试题：

    1、手工写代码一个HTML提交表单，注意（表单对齐方式）

    JavaScript代码
    1. <script type="text/javascript">
    2. function check_form()
    3. {
    4.   var username = document.getElementById('username').value;
    5.   if (username == '') {
    6.     alert('非法用户名');
    7.     return false;
    8.   } else {
    9.     return true;
    10.  }
    11. /*
    12. 更牛B的创意呢，你可以写成jQuery的
    13.
    14.  if ($.trim($('#username').val()) == '') {
    15.   alert('非法用户名');
    16.   $('#username').focus();
    17.   return false;
    18.  } esle {
    19.   return true;
    20.  }
    21. */
    22. }
    23. </script>

    XML/HTML代码

    1. <form name="from1" method="POST" action="login.php" onsubmit="return check_form()">
    2. <table border="1" width="100%">
    3. <tr>
    4.   <td align="right">用户名： </td>
    5.   <td><input type="text" id="username" name="username"></td>
    6. </tr>
    7. <tr>
    8.   <td align="right">密码：</td>
    9.   <td><input type="password" id="password" name="password"></td>
    10 </tr>
    11. <tr>
    12.   <td colspan="2" align="right"><input type="submit" value="提交"></td>
    13. </tr>
    14. </table>
    15. </form>

    2、写一段上面表单的PHP验证程序

    PHP代码

    1. <?php
    2. /**
    3. * 如果想好好表现也可以不按这个流程来写，设计个OO风格的也许会+分，可以耐心的多写会但不要写乱这可不是在键盘上那么容易
    4. */
    5. $db = mysql_connect('localhost', 'root', '');
    6. mysql_select_db('db_name');
    7.
    8. /* 不要吝啬多写代码这个过滤函数要加的，此题也考察安全意识 */
    9. $username = mysql_real_escape_string($_POST['username']);
    10. $password = mysql_real_escape_string($_POST['password']);
    11.
    12. $sql = "SELECT PASS FROM UserInfo WHERE USER='{$username}'";
    13. $query = mysql_query($sql);
    14. $row = mysql_fetch_assoc($query);
    15.
    16. if ( ! $row) {
    17.   echo "用户名不存在";
    18. } else {
    19.   echo $row['PASS'] == $password ? "密码正确" : "密码错误";
    20. }

    3、继上一题写出HTTP请求与接收的报文（摘录）

    （1）请求行
        请求行由请求方法字段、URL字段和HTTP协议版本字段3个字段组成，它们用空格分隔。例如，GET /index.html HTTP/1.1。
        HTTP协议的请求方法有GET、POST、HEAD、PUT、DELETE、OPTIONS、TRACE、CONNECT。这里介绍最常用的GET方法和POST方法。
      GET：当客户端要从服务器中读取文档时，使用GET方法。GET方法要求服务器将URL定位的资源放在响应报文的数据部分，回送给客户端。使用GET方法时，请求参数和对应的值附加在URL后面，利用一个问号（“?”）代表URL的结尾与请求参数的开始，传递参数长度受限制。例如，/index.jsp?id=100&op=bind。
      POST：当客户端给服务器提供信息较多时可以使用POST方法。POST方法将请求参数封装在HTTP请求数据中，以名称/值的形式出现，可以传输大量数据。
    （2）请求头部
        请求头部由关键字/值对组成，每行一对，关键字和值用英文冒号“:”分隔。请求头部通知服务器有关于客户端请求的信息，典型的请求头有：
      User-Agent：产生请求的浏览器类型。
      Accept：客户端可识别的内容类型列表。
      Host：请求的主机名，允许多个域名同处一个IP地址，即虚拟主机。
    （3）空行
        最后一个请求头之后是一个空行，发送回车符和换行符，通知服务器以下不再有请求头。
    （4）请求数据
        请求数据不在GET方法中使用，而是在POST方法中使用。POST方法适用于需要客户填写表单的场合。与请求数据相关的最常使用的请求头是Content-Type和Content-Length。
    

    4、正则匹配邮箱地址

    PHP代码

    1. <?php
    2. $html = "9812ed [e-mail] s9dfasdf$@$ [e-mail] [e-mail] [e-mail] [e-mail]";
    3. preg_match_all('/\w+(\.\w+)*@\w+(\.\w+){1,}/', $html, $mails);
    4. print_r($mails);
    4、SHELL下搜索*.xml文件中含有hello的文件（我在Ubuntu下尝试命令通过，以前在CentOS也这样的使用过此命令但是没有预期效果）

    Shell代码

    1. grep -r hello *.xml

    5、autoload机制

    在$object = new UFO;时，试图调用一个未引入的类文件在系统报错之前，会尝试使用__autoload进行加载类，如果定义了__autoload方法将按照此规则进行加载类文件

    6、实现strrev()函数“360奇虎”，不使用mb_substr情况下。

    PHP代码

    1. <?php
    2. /* 不使用mb_string */
    3. $string = "虎奇063";
    4. $length = strlen($string);
    5. $rev_string = '';
    6. /* 限UTF-8字符编码字节占3，不然还有写个is_utf8来判断所占用的字节数 */
    7. $byte_len = 3;
    8. for ($i = 0; $i < $length;) {
    9.   if (ord(substr($string, $i, 1)) > 0xa0) {
    10.     $rev_string = substr($string, $i, $byte_len) . $rev_string;
    11.     $i+= $byte_len;
    12.   } else {
    13.   $rev_string = substr($string, $i, 1) . $rev_string;
    14.   $i++;
    15.   }
    16. }
    17. echo $rev_string;

    7、使用了索引查询的语句，EXPLAIN

    SQL代码

    1. SELECT * FROM user where name='a';
    2.
    3. SELECT * FROM user where name='a' OR name='b';
    4.
    5. SELECT * FROM user where name like 'a%';

19. 多玩YY 2012校园招聘笔试题  C++  A卷

    时间：120分钟          提示：请注意代码风格

    1、请给出以下程序的输出：（12分）

    class A
    {
    public:
        A()
        {
            puts("In A");
        }
        ~A()
        {
            puts("Out A");
        }
    };
    
    class B
    {
    public:
        B()
        {
            puts("In B");
        }
        ~B()
        {
            puts("Out B");
        }
    };
    
    class X
    {
    public:
        X()
        {
            puts("In X");
        }
        ~X()
        {
            puts("Out X");
        }
        virtual void test()
        {
            puts("test in X");
        }
    };
    
    class C:public X
    {
    public:
        C(): b(), a()
        {
            puts("In C");
    
        }
        ~C()
        {
            puts("Out C");
        }
        virtual void test()
        {
            puts("test in C");
        }
    private:
        A a;
        B b;
    };
    
    int main()
    {
        X* p = new C;
        p->test();
        delete p;
    
        return 0;
    }

    2、请简述以下const的作用（8分）

    1）const int a = 10;
    2)const  int*
    3)int * const a
    4)void T::test() const

    3、请问以下过程调用的时拷贝构造函数还是赋值运算符：（6分）

    class Test{…}
    Test a,b;
    a = b;             1)
    Test a;
    Test b = a;         2)
    Test a;
    Test b(a);          3)

    4、请完成以下函数的填空：（9分）

    int binarySearch(int from, int to, int target, int *array)
    {
      /*
        功能：从array中查找target，返回target在array中的下标
      */
      if(from <= to)
      {
        int middle = (from + to) /2;
        if(array[middle] == target)
    
        else if(array[middle]<target)
    
      else
    
      }
      return -1;
    }

    5、请给出以下程序的输出：（5分）

    class T
    {
    public:
        T()
        {
            puts("T()");
        }
        ~T()
        {
            puts("~()");
        }
    private:
    };
    
    void test(T t)
    {
    }
    
    int main()
    {
        T t;
        test(t);
    
        return 0;
    }

    6、下面的代码段有几处错误，请根据程序的意图，写出正确的server类（10分）

    提示：这段代码实现的功能是定期向各个server 发ping包，各个server对象是在不同时间创建的

    class Server
    {
        Server()
        {
        }
        ~Server()
        {
        }
        void checkSendPing()
        {
            /*
            每隔5秒给该服务器发ping
            */
            static int lastSendPing = (int)time(NULL);
            int now = (int)time(NULL);
            if(now < lastSendPing + 5)
                return;
            //send ping to peer
        }
    private:
    };
    
    void monitorServer(std::vector<Server>& x)
    {
        /*
        监控所有服务器的状态，这个函数每秒运行一次
        */
        for(std::vector<Server>::iterator it = x.begin();
            it != x.end();++it)
            it->checkSendPing();
    }

    7、（编程题）100万个数据，数据值在0~65535之间，请用尽可能少的内存和最快的速度从小到大排序（10分）

    void sort(int* array, int n)
    {
        //n的值在100万左右
        //你的实现
    }

    8、（编程题）请完成如下函数，从长度为n的数组array中删除值等于v的元素，返回删除后的数组array和元素个数（10分）

    int remove(int* array, int n, int v)
    {
        //你的实现
    }

    9、（编程题）请看以下的Maixu结构：（15分）

    struct Maixu
    {
        int sid;                       //id
        std::list<int> userlist:      //队列
        int validTime;                //预定时间，每个结构不一样，平均5分钟左右，以秒为单位
        int leftTime;                 //剩余时间，以秒为单位
    };

    其中队列userlist中每一项都在预定的时间validTime后出队，比如当前队列是{1,2,3}，validTime是5秒，则5秒后1出列，队列变为{2,3}，再过5秒2出队，队列变为{3}，相应的实现代码如下：

    std::vector<Maixu> m_maixus;      /*这个vector长度最多可以达到100000*/
    
    void Timer()              //Timer函数每秒运行一次
    {
        for(std::vector<Maixu>::iterator it = m_maixus.begin();
          it !=m_maixus.end();++it)
          {
              if(it->userlist.empty())
                  continue;
              if(--it->leftTime == 0)
              {
                  //时间到
                  it->userlist.pop_front();
                  it->leftTime = it->validTime;
                  //其他操作
              }
          }
    }

    请问上面的实现方式有没有什么问题？如何改进？请提出你的改进方案并重写上面的代码段。

    10、（思考题）有服务器S1、S2…Sn（100>n>50），每个服务器上维护着连接到该服务器的用户的信息，服务器之间互相连接，当用户信息有更新，必须通知到与它相连的其它服务器。比如S1上的用户a改了昵称，必须通知到S2 、S3…但由于网络的不可靠，更新通知不一定每次都能到达其它服务器，假设S2丢了通知，则S2必须同步上的用户信息，最差情况下，S2~Sn都可能同时丢了S1的通知而导致同步。

    每个服务器大概维护10000个用户，用户的信息结构如下，大小平均约100B：（15分）

    struct UserInfo
    {
        int userId;        //用户id
        string nickname;   //昵称
        string sign;       //签名
        //其它用户信息
    };

    问题：

    1） S2如何发现它丢了S1的通知？
    2） 每个服务器的带宽限制10M/s，请给出一个可用的同步方案，保证服务器带宽不超过限制的情况下完成同步工作；
    3） 显然如果通知越可靠，同步将会大大减少，请提出一些能提高通知可靠性的方案并简单说明它的实现。
    

20. 持续更新，待续...2012.09.13；
21. 
    

    由于整理匆忙，有部分题目未注明详细来源，若以上任何一题目出自你的空间或者发的帖子而未有注明，请于本文评论中告知我，一定即刻补上，谢谢。

后记

    经过上面这么多笔试面试题目的了解，你自会看到，除了少数几个特别难的算法题，大部分都是考察的基础，故面试的关键是你的80%的基础和编程能力 + 20%的算法能力。

    重复开头那句话：如果你有好的笔试面试题，欢迎提供给我统一整理出来（对于好的题目提供者，在私信：http://weibo.com/julyweibo，或邮件：[e-mail]，里你尽可以提出你的要求，或贴出你的微博昵称，或个人主页，或免费回赠编程艺术+算法研究的两个PDF文档：http://weibo.com/1580904460/yzpYDAuYz），以供他人借阅；如果你对以上任何一题有好的思路或解法，更欢迎不吝分享，show me your answer or code！thank you。

    OK，以上的一切都是我喜欢且我乐意做的，我愿同各位朋友享受这一切。如果你身边有正在参加校招/笔试/面试的朋友，欢迎把此文转给他/她，举手之劳，助人无限，谢谢。完。July，二零一二年九月。