[原]九月百度人搜，阿里巴巴，腾讯华为小米搜狗笔/面试三十题(更新至09.25)

    最新九月百度人搜，阿里巴巴，腾讯华为小米搜狗笔试面试三十题

引言

    自发表上一篇文章至今（事实上，上篇文章更新了近3个月之久），blog已经停了3个多月，而在那之前，自开博以来的21个月每月都不曾断过。正如上一篇文章 支持向量机通俗导论（理解 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，或邮箱：[email protected]发给我，或者干脆直接评论在本文下；同时，若你对以下任何一题有任何看法.想法.思路或建议，欢迎留言评论，大家一起讨论，共同享受思考的乐趣，谢谢）。

九月百度人搜，阿里巴巴，腾讯华为小米搜狗笔/面试三十题

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，成为兄弟单词。提供一个单词，在字典中找到它的兄弟。描述数据结构和查询过程。评点：同去年9月份的一道题，见此文第3题： http://blog.csdn.net/v_july_v/article/details/6803368。
     简答题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,比如输入北京，搜索框下面会以北京为前缀，展示“北京爱情故事”、“北京公交”、“北京医院”等等搜索词。
   如何设计使得空间和时间复杂度尽量低。评点：老题，直接上Trie树+Hash，Trie树的介绍见： 从Trie树（字典树）谈到后缀树。
   
4. 人搜笔试
1. 快排每次以第一个作为主元，问时间复杂度是多少？（O(N*logN)）
  2. T(N) = N + T(N/2)+T(2N), 问T(N)的时间复杂度是多少？ 点评：O(N*logN) or 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. 人搜面试，所投职位：搜索研发工程师：面试题回忆 
        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日，阿里笔试题：平面上有很多点，点与点之间有可能有连线，求这个图里环的数目。
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,由于出现的字符个数都是相同，只是顺序不同，
     所以这两个字符串是匹配的。要求高效！
    又是跟上述第3题中简单题一的兄弟节点类似的一道题，我想，你们能想到的，这篇blog里： http://blog.csdn.net/v_JULY_v/article/details/6347454都已经有了。
12. 阿里云，搜索引擎中5亿个url怎么高效存储；
    
13. 一道C++笔试题，求矩形交集的面积：
    在一个平面坐标系上，有两个矩形，它们的边分别平行于X和Y轴。
    其中，矩形A已知， ax1(左边), ax2（右边）, ay1（top的纵坐标）, ay2（bottom纵坐标）. 矩形B，类似，就是 bx1, bx2, by1, by2。这些值都是整数就OK了。
    要求是，如果矩形没有交集，返回-1， 有交集，返回交集的面积。
    int area(rect const& a, rect const& b)
    {
      ...
    }
    点评：
    healer_kx：
    补齐代码，最好是简洁的，别用库。你可以写你的辅助函数，宏定义，代码风格也很重要。
    ri_aje：
    

    struct rect
    {
     // axis alignment assumed
     // bottom left is (x[0],y[0]), top right is (x[1],y[1])
     double x [2];
     double y [2];
    };
    
    template <typename T> T const& min (T const& x, T const& y) { return x<y ? x : y; }
    template <typename T> T const& max (T const& x, T const& y) { return x>y ? x : y; }
    
    // return type changed to handle non-integer rects
    double area (rect const& a, rect const& b)
    {
     // perfectly adjacent rects are considered having an intersection of 0 area
     double const dx = min(a.x[1],b.x[1]) - max(a.x[0],b.x[0]);
     double const dy = min(a.y[1],b.y[1]) - max(a.y[0],b.y[0]);
     return dx>=0&&dy>=0 ? dx*dy : -1;
    }

    下面是一个简短的证明。
    对于平行于坐标轴的矩形 r，假设其左下角点坐标为 (rx0,ry0)，右上角点坐标为 (rx1,ry1)，那么由 r 定义的无限有界点集为：{(x,y)|x in [rx0,rx1] && y in [ry0,ry1]}。
    根据交集的定义，则任意二维点 (x,y) 在矩形 a,b 的交集内等价于
    {(x,y)|(x,y) in a 并且 (x,y) in b} <==>
    {(x,y)|x in [ax0,ax1] && x in [bx0,bx1] 并且 y in [ay0,ay1] && y in [by0,by1]} <==>
    {(x,y)|x in [max(ax0,bx0),min(ax1,bx1)] 并且 y in [max(ay0,by0),min(ay1,by1)]}
    因此，交集矩形的边长分别为 min(ax1,bx1)-max(ax0,bx0) 和 min(ay1,by1)-max(ay0,by0)。注意当交集为空时(a,b 不相交)，则经此法计算出来的交集边长为负值，此事实可用于验证 a,b 的相交性。
    鉴于笛卡尔积各个维度上的不相关性，此方法可扩展到任意有限维线性空间，比如，三维空间中平行于坐标轴的长方体的交集体积可以用类似的方法计算。
    来源： http://topic.csdn.net/u/20120913/18/bc669d60-b70a-4008-be65-7c342789b925.html。
    
14. 创新工场微博，发布的一些题： http://t.qq.com/iwrecruiting?pgv_ref=im.WBlog.guest&ptlang=2052；

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

16. 阿里巴巴二道题
    第一道：
    对于给定的整数集合S，求出最大的d，使得a+b+c=d。a,b,c,d互不相同，且都属于S。集合的元素个数小于等于2000个，元素的取值范围在[ -2^28，2^28 - 1]，假定可用内存空间为100MB，硬盘使用空间无限大，试分析时间和空间复杂度，找出最快的解决方法。
    阿里巴巴第二道(研发类)
    笔试题1，原题大致描述有一大批数据，百万级别的。数据项内容是：用户ID、科目ABC各自的成绩。其中用户ID为0~1000万之间，且是连续的，可以唯一标识一条记录。科目ABC成绩均在0~100之间。有两块磁盘，空间大小均为512M，内存空间64M。
    1) 为实现快速查询某用户ID对应的各科成绩，问磁盘文件及内存该如何组织；
    2) 改变题目条件，ID为0~10亿之间，且不连续。问磁盘文件及内存该如何组织；
    3) 在问题2的基础上，增加一个需求。在查询各科成绩的同时，获取该用户的排名，问磁盘文件及内存该如何组织。
    笔试题2：代码实现计算字符串的相似度。 
17. 9月14日，小米笔试，给一个浮点数序列，取最大乘积子序列的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积子序列为3，0.5，8。
18. 9月15日，中兴面试：
    小端系统
    

    union{
            int i;
            unsigned char ch[2];
    }Student;
    
    
    int main()
    {
            Student  student;
            student.i=0x1420;
            printf("%d  %d",student.ch[0],student.ch[1]);
    	return 0;
    }

    输出结果为？（答案：32 20）
    
19. 一道有趣的Facebook面试题：
    给一个二叉树，每个节点都是正或负整数，如何找到一个子树，它所有节点的和最大？ 
    点评：
    @某猛将兄:后序遍历，每一个节点保存左右子树的和加上自己的值。额外一个空间存放最大值。
    @陈利人：同学们，如果你面试的是软件工程师的职位，一般面试官会要求你在短时间内写出一个比较整洁的，最好是高效的，没有什么bug的程序。所以，光有算法不够，还得多实践。
    写完后序遍历，面试官可能接着与你讨论，a). 如果要求找出只含正数的最大子树，程序该如何修改来实现？b). 假设我们将子树定义为它和它的部分后代，那该如何解决？c). 对于b，加上正数的限制，方案又该如何？总之，一道看似简单的面试题，可能能变换成各种花样。
    比如，面试管可能还会再提两个要求：第一，不能用全局变量；第一，有个参数控制是否要只含正数的子树。其它的，随意，当然，编程风格也很重要。
    
20. 谷歌面试题：
    有几百亿的整数，分布的存储到几百台通过网络连接的计算机上，你能否开发出一个算法和系统，找出这几百亿数据的中值？就是在一组排序好的数据中居于中间的数。显然，一台机器是装不下所有的数据。也尽量少用网络带宽。
    
21. 小米，南京站笔试（原第20题）：
    一个数组里，数都是两两出现的，但是有三个数是唯一出现的，找出这三个数。
    点评：
    3个数唯一出现，各不相同。
    
22. 9月19日，IGT面试：你走到一个分叉路口，有两条路，每个路口有一个人，一个说假话，一个说真话，你只能问其中一个人仅一个问题，如何问才能得到正确答案？点评：答案是，问其中一个人：另一个人会说你的路口是通往正确的道路么？
    
23. 9月19日，创新工厂笔试题：
    给定一整型数组，若数组中某个下标值大的元素值小于某个下标值比它小的元素值，称这是一个反序。
    即：数组a[]; 对于i < j 且 a[i] > a[j],则称这是一个反序。
    给定一个数组，要求写一个函数，计算出这个数组里所有反序的个数。
    点评：
    归并排序，至于有的人说是否有O（N）的时间复杂度，我认为答案是否定的，正如老梦所说，下限就是nlgn，n个元素的数组的排列共有的排列是nlgn，n！（算法导论里面也用递归树证明了：O(n*logn)是最优的解法，具体可以看下这个链接：）。然后，我再给一个链接，这里有那天笔试的两道题目： http://blog.csdn.net/luno1/article/details/8001892。
24. 9月20日，创新工厂南京站笔试：
    已知字符串里的字符是互不相同的，现在任意组合，比如ab，则输出aa，ab，ba，bb，编程按照字典序输出所有的组合。
    点评：非简单的全排列问题（跟全排列的形式不同,abc 全排列的话，只有６个不同的输出： http://blog.csdn.net/v_july_v/article/details/6879101）。本题可用递归的思想，设置一个变量表示已输出的个数，然后当个数达到字符串长度时，就输出。

    //假设str已经有序，from 一直很安静
    void perm(char *str, int size, int resPos)
    {
        if(resPos == size)
    	print(result);
        else
        {
    	for(int i = 0; i < size; ++i)
            {
    	  result[resPos] = str[i];
    	  perm(str, size, resPos + 1);
    	}
        }
    }

25. 9月21日，小米，电子科大笔试3道题：

    void fun()
    {
    	unsigned int a = 2013;
    	int b = -2;
    	int c = 0;
    	while (a + b > 0)
    	{
    		a = a + b;
    		c++;
    	}
    	printf("%d", c);
    }

    问：最后程序输出是多少？点评：此题有陷阱，答题需谨慎！
    
26. 9月21日晚，海豚浏览器笔试题：
    有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升序排列，对于1<=i,j<=k，求k个最小的（ai+bj），要求算法尽量高效。
    
27. 9月22日上午，百度西安站全套笔试题如下：
    3.算法与程序设计
    第一题：
    某个公司举行一场羽毛球赛，有1001个人参加，现在为了评比出“最厉害的那个人”，进行淘汰赛，请问至少需要进行多少次比赛。
    第二题
    有100个灯泡，第一轮把所有灯泡都开启，第二轮把奇数位的灯泡灭掉，第三轮每隔两个灯泡，灭一个，开一个，依此类推。求100轮后还亮的灯泡。
    第三题
    有20个数组，每个数组里面有500个数组，降序排列，每个数字是32位的unit,求出这10000个数字中最大的500个。
    4.系统设计题
    类似做一个手机键盘，上面有1到9个数字，每个数字都代表几个字母（比如1代表abc三个字母，z代表wxyz等等），现在要求设计当输入某几个数字的组合时，查找出通讯录中的人名及电话号码。
    其它的还有三道简答题，比如线程的死锁，内存的管理等等。
    
28. 9月22日，微软笔试：
    T(n)=1(n<=1),T(n) = 25*T(n/5) + n^2，求算法的时间复杂度。更多题目请参见： http://blog.csdn.net/wonderwander6642/article/details/8008209。
    
29. 9月23日，腾讯校招部分笔试题(特别提醒:下述试卷上的答案只是一考生的解答,非代表正确答案.如下面第11题答案选D,第12题答案选C,至于解释请看这里: http://coolshell.cn/articles/7965.html)：
    
    点评：根号九说，不过最后两道大的附加题，全是90%海量数据题秒杀里的，太感谢July了。
30. 9月23日，搜狗校招武汉站笔试题：
    一、已知计算机有以下原子操作
    1、 赋值操作：b = a;
    2、 ++a和a+1;
    3、for( ){ ***}有限循环；
    4、操作数只能为0或者正整数；
    5、定义函数
    实现加减乘操作
    二、对一个链表进行排序，效率越高越好，LinkedList<Integer>.
    
    附：9月15日，搜弧校招笔试题： http://blog.csdn.net/hackbuteer1/article/details/8015964。
    
31. 
    100个任务，100个工人每人可做一项任务，每个任务每个人做的的费用为t[100][100],求一个分配任务的方案使得总费用最少。
    点评：匈牙利算法，可以看看这篇文章： http://www.byvoid.com/blog/hungary/。
32. 9月24日，Google南京等站全套笔试题如下：
    
    点评：
    谷歌的笔试从易到难，基础到复杂，涵盖操作系统 网络 数据结构 语言 数学思维 编程能力 算法能力，基本上能把一个人的能力全面考察出来。赞一下!
    
33. 读者来信，提供的几个hulu面试题（为保护个人隐私，略去相关信息）：
    9月19号,hulu电面：
    问题1 两个骰子，两个人轮流投，直到点数和大于6就停止，最终投的那个人获胜。问先投那个人获胜概率？
    问题2  平面上n个圆，任意两个都相交，是否有一条直线和所有的圆都有交点。
    9月22号,上午hulu面试
    问题1 100个人，每人头上戴一顶帽子，写有0..99的一个数，数可能重复，每个人都只能看到除自己以外其他人的帽子。每个人需要说出自己的帽子的数，一个人说对就算赢。
    问题2 n台机器，每台有负载，以和负载成正比的概率，随机选择一台机器。
    问题3  行列都递增的矩阵，求中位数。
    
34. 9月25日晚，创新工场校园招聘北邮站笔试：
    
35. 
    

后记