2012年欧姆定律中考题集

以下是整理自8月下旬至10月份内的各大公司的笔试面试三十题（注：所有题目基本上全部为软件开发方向，题目来源：网络收集），相信一定能给正在参加各种校招的诸多朋友多少帮助，学习参考或借鉴九月十月百度人搜，阿里巴巴，腾讯华为小米搜狗笔/面试五十题9月11日， 京东：谈谈你对面向对象编程的认识1 8月20日，金山面试，题目如下：数据库1中存放着a类数据，数据库2中存放着以天为单位划分的表30张（比如table_20110909,table_20110910,table_20110911）,总共是一个月的数据。表1中的a类数据中有一个字段userid来唯一判别用户身份，表2中的30张表（每张表结构相同）也有一个字段userid来唯一识别用户身份。如何判定a类数据库的多少用户在数据库2中出现过？百度实习笔试题（2012.5.6）简答题1一个单词单词字母交换，可得另一个单词，如army-mary，成为兄弟单词。提供一个单词，在字典中找到它的兄弟。描述数据结构和查询过程。评点：同去年9月份的一道题，见此文第3题：简答题2线程和进程区别和联系。什么是“线程安全”简答题3C和C+怎样分配和释放内存，区别是什么算法题1一个url指向的页面里面有另一个url,最终有一个url指向之前出现过的url或空，这两种情形都定义为null。这样构成一个单链表。给两条这样单链表，判断里面是否存在同样的url。url以亿级计，资源不足以hash。算法题2数组al0,mid-1 和 almid,num-1，都分别有序。将其merge成有序数组al0,num-1，要求空间复杂度O(1)系统设计题百度搜索框的suggestion,比如输入北京，搜索框下面会以北京为前缀，展示“北京爱情故事”、“北京公交”、“北京医院”等等搜索词。如何设计使得空间和时间复杂度尽量低。评点：老题，直接上Trie树+Hash，Trie树的介绍见：从Trie树（字典树）谈到后缀树。2 人搜笔试3 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 NodeNode* parent;Node* firstChild; / 孩子节点Node* sibling; / 兄弟节点要求非递归遍历该树。思路：采用队列存储，来遍历节点。5. 算法题：有N个节点，每两个节点相邻，每个节点只与2个节点相邻，因此，N个顶点有N-1条边。每一条边上都有权值wi，定义节点i到节点i+1的边为wi。求：不相邻的权值和最大的边的集合。4 人搜面试，所投职位：搜索研发工程师：面试题回忆1、删除字符串开始及末尾的空白符，并且把数组中间的多个空格（如果有）符转化为1个。2、求数组（元素可为正数、负数、0）的最大子序列和。3、链表相邻元素翻转，如a-b-c-d-e-f-g，翻转后变为：b-a-d-c-f-e-g4、链表克隆。链表的结构为：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）。5 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 网易有道二面：判断一个数字序列是BST后序遍历的结果，现场写代码。7 8月30日，网易有道面试题var tt = aa;function test()alert(tt);var tt = dd;alert(tt);test();8 8月31日，百度面试题：不使用随机数的洗牌算法，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的情形排除出去。9月8日，腾讯面试题：假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配， 比如：abcda和adabc,由于出现的字符个数都是相同，只是顺序不同， 所以这两个字符串是匹配的。要求高效！又是跟上述第3题中简单题一的兄弟节点类似的一道题，我想，你们能想到的，11 阿里云，搜索引擎中5亿个url怎么高效存储；11 一道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 11 11 / axis alignment assumed 11 / bottom left is (x0,y0), top right is (x1,y1) 11 double x 2; 11 double y 2; 11 ; 1111 template T const& min (T const& x, T const& y) return xy ? x : y; 11 template T const& max (T const& x, T const& y) return xy ? x : y; 1111 / return type changed to handle non-integer rects 11 double area (rect const& a, rect const& b) 11 11 / perfectly adjacent rects are considered having an intersection of 0 area 11 double const dx = min(a.x1,b.x1) - max(a.x0,b.x0); 11 double const dy = min(a.y1,b.y1) - max(a.y0,b.y0); 11 return dx=0&dy=0 ? dx*dy : -1; 11 12 下面是一个简短的证明。对于平行于坐标轴的矩形 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 的相交性。鉴于笛卡尔积各个维度上的不相关性，此方法可扩展到任意有限维线性空间，比如，三维空间中平行于坐标轴的长方体的交集体积可以用类似的方法计算。13 2012年创新工场校园招聘最后一道笔试题：工场很忙 创新工场每年会组织同学与项目的双选会，假设现在有M个项目，编号从1到M，另有N名同学，编号从1到N，每名同学能选择最多三个、最少一个感兴趣的项目。选定之后，HR会安排项目负责人和相应感兴趣的同学一对一面谈，每次面谈持续半小时。由于大家平时都很忙，所以咱们要尽量节约时间，请你按照以下的条件设计算法，帮助HR安排面试。1）同学很忙。项目负责人一次只能与一名同学面谈，而同学会在自己第一个面试开始时达到工场，最后一个面试结束后离开工场，如果参加一个项目组的面试后不能立即参加下一个项目组的面试，就必须在工场等待。所以请尽可能让同学的面试集中在某一时间段，减少同学在工场等待的时间。2）项目负责人很忙。众所周知，创业团队的负责人会有很多事情要做，所以他们希望能够将自己参与的面试集中在某一段时间内，请在保证1）的情况下，使得项目负责人等待的时间最少。3）HR很忙。从第一轮面试开始以后，所有HR都必须等到最后一轮面试结束，所以需要在保证1）和2）的同时，也能尽快解放掉所有的HR，即让第一轮面试到最后一轮面试之间持续的时间最短。输入(以文件方式输入，文件名为iw，例如iw.in)：第1行.第n行：同学的编号 项目的编号 样例（数据间用空格隔开,两个0表示输入结束）： 1 1 1 2 1 3 2 1 3 1 3 2 0 0 表示M=3，N=3，编号为1的同学选择了项目1,2和3，编号为2的同学选择了项目1，编号为3的同学选了项目1和2输出(以文件方式输出，文件名为iw，例如iw.out)：第1行：编号为1的项目依次面试新同学的编号序列 第2行：编号为2的项目依次面试新同学的编号序列 . 第n行：编号为n的项目依次面试新同学的编号序列 样例（数据间用空格隔开，0表示没有面试）： 1 3 2 3 1 0 0 0 1 表示编号为1的项目在第一轮面试编号为1的同学，第二轮面试编号为3的同学，第三轮面试编号为2的同学 编号为2的项目在第一轮面试编号为3的同学，第二轮面试编号为1的同学，第二轮不用面试 编号为3的项目在第一轮和第二轮都不用面试，第三轮面试编号为1的同学4*9 的笔试题，比较简单：1.求链表的倒数第二个节点2.有一个整数数组，求数组中第二大的数阿里巴巴二道题第一道：对于给定的整数集合S，求出最大的d，使得a+b+c=d。a,b,c,d互不相同，且都属于S。集合的元素个数小于等于2000个，元素的取值范围在-228，228 - 1，假定可用内存空间为100MB，硬盘使用空间无限大，试分析时间和空间复杂度，找出最快的解决方法。点评：绿色夹克衫：两两相加转为多项式乘法，比如(1 2 4 6) + (2 3 4 5) = (x + x2 + x4 + x6)*(x2 + x3 + x4 + x5) 。阿里巴巴第二道(研发类)笔试题1，原题大致描述有一大批数据，百万级别的。数据项内容是：用户ID、科目ABC各自的成绩。其中用户ID为01000万之间，且是连续的，可以唯一标识一条记录。科目ABC成绩均在0100之间。有两块磁盘，空间大小均为512M，内存空间64M。1) 为实现快速查询某用户ID对应的各科成绩，问磁盘文件及内存该如何组织；2) 改变题目条件，ID为010亿之间，且不连续。问磁盘文件及内存该如何组织；3) 在问题2的基础上，增加一个需求。在查询各科成绩的同时，获取该用户的排名，问磁盘文件及内存该如何组织。笔试题2：代码实现计算字符串的相似度。点评：和计算两字符串的最长公共子序列相似。设Ai为字符串A(a1a2a3 am)的前i个字符（即为a1,a2,a3 ai）设Bj为字符串B(b1b2b3 bn)的前j个字符（即为b1,b2,b3 bj）设 L(i , j)为使两个字符串和Ai和Bj相等的最小操作次数。当ai等于bj时 显然L(i, j)=L(i-1, j-1)当ai不等于bj时 若将它们修改为相等，则对两个字符串至少还要操作L(i-1, j-1)次 若删除ai或在Bj后添加ai，则对两个字符串至少还要操作L(i-1, j)次 若删除bj或在Ai后添加bj，则对两个字符串至少还要操作L(i, j-1)次 此时L(i, j)=min( L(i-1, j-1), L(i-1, j), L(i, j-1) ) + 1显然，L(i, 0)=i，L(0, j)=j, 再利用上述的递推公式，可以直接计算出L(i, j)值。具体代码请见这：13 9月14日，小米笔试，给一个浮点数序列，取最大乘积子序列的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积子序列为3，0.5，8。点评：解法一、或许，读者初看此题，自然会想到最大乘积子序列问题类似于最大子数组和问题：然实则具体处理起来诸多不同，为什么呢，因为乘积子序列中有正有负也还可能有0。既如此，我们可以把问题简化成这样：数组中找一个子序列，使得它的乘积最大；同时找一个子序列，使得它的乘积最小（负数的情况）。因为虽然我们只要一个最大积，但由于负数的存在，我们同时找这两个乘积做起来反而方便。也就是说，不但记录最大乘积，也要记录最小乘积。So，我们让maxCurrent表示当前最大乘积的candidate， minCurrent反之，表示当前最小乘积的candidate。 （用candidate这个词是因为只是可能成为新一轮的最大/最小乘积）， 而maxProduct则记录到目前为止所有最大乘积candidates的最大值。由于空集的乘积定义为1，在搜索数组前，maxCurrent,minCurrent,maxProduct都赋为1。假设在任何时刻你已经有了maxCurrent和minCurrent这两个最大/最小乘积的candidates，新读入数组的元素x(i)后，新的最大乘积candidate只可能是maxCurrent或者minCurrent与x(i)的乘积中的较大者，如果x(i)0导致maxCurrentminCurrent，需要交换这两个candidates的值。当任何时候maxCurrent1，由于1（空集）是比maxCurrent更好的candidate，所以更新maxCurrent为1，类似的可以更新minCurrent。任何时候maxCurrent如果比最好的maxProduct大，更新maxProduct。具体代码如下：template 13 Comparable maxprod( const vector&v) 13 13 int i; 13 Comparable maxProduct = 1; 13 Comparable minProduct = 1; 13 Comparable maxCurrent = 1; 13 Comparable minCurrent = 1; 13 /Comparable t; 1313 for( i=0; i maxProduct) 13 maxProduct = maxCurrent; 13 if(minCurrent maxProduct) 13 maxProduct = minCurrent; 13 if(maxCurrent minProduct) 13 minProduct = maxCurrent; 13 if(minCurrent maxCurrent) 13 swap(maxCurrent,minCurrent); 13 if(maxCurrent1) 13 / minCurrent =1; 13 13 return maxProduct; 13 13 解法二、本题除了上述类似最大子数组和的解法，也可以直接用动态规划求解（其实，上述的解法一本质上也是动态规划，只是解题所表现出来的具体形式与接下来的解法二不同罢了。这个不同就在于下面的解法二会写出动态规划问题中经典常见的状态转移方程，而解法一是直接求解）。具体解法如下：假设数组为a，直接利用动归来求解，考虑到可能存在负数的情况，我们用Maxi来表示以ai结尾的最大连续子序列的乘积值，用Mini表示以ai结尾的最小的连续子序列的乘积值，那么状态转移方程为： Maxi=maxai, Maxi-1*ai, Mini-1*ai; Mini=minai, Maxi-1*ai, Mini-1*ai; 初始状态为Max1=Min1=a1。代码如下：/* 13 给定一个整数数组，有正有负数，0，正数组成,数组下标从1算起 13 求最大连续子序列乘积，并输出这个序列，如果最大子序列乘积为负数，那么就输出-1 13 用Maxi表示以ai结尾乘积最大的连续子序列 13 用Mini表示以ai结尾乘积最小的连续子序列 因为有复数，所以保存这个是必须的 13 */ 13 void longest_multiple(int *a,int n) 13 int *Min=new intn+1(); 13 int *Max=new intn+1(); 13 int *p=new intn+1(); 13 /初始化 13 for(int i=0;i=n;i+) 13 pi=-1; 13 13 Min1=a1; 13 Max1=a1; 13 int max_val=Max1; 13 for(int i=2;i=n;i+) 13 Maxi=max(Maxi-1*ai,Mini-1*ai,ai); 13 Mini=min(Maxi-1*ai,Mini-1*ai,ai); 13 if(max_valMaxi) 13 max_val=Maxi; 13 13 if(max_val0) 13 printf(%d,-1); 13 else 13 printf(%d,max_val); 13 /内存释放 13 delete Max; 13 delete Min; 13 变种 此外，此题还有另外的一个变种形式，即给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意（N-1）个数的组合中乘积最大的一组，并写出算法的时间复杂度。 我们可以把所有可能的（N-1）个数的组合找出来，分别计算它们的乘积，并比较大小。由于总共有N个（N-1）个数的组合，总的时间复杂度为O（N2），显然这不是最好的解法。 OK，以下解答来自编程之美解法1解法2 此外，还可以通过分析，进一步减少解答问题的计算量。假设N个整数的乘积为P，针对P的正负性进行如下分析（其中，AN-1表示N-1个数的组合，PN-1表示N-1个数的组合的乘积）。 1.P为0 那么，数组中至少包含有一个0。假设除去一个0之外，其他N-1个数的乘积为Q，根据Q的正负性进行讨论：Q为0说明数组中至少有两个0，那么N-1个数的乘积只能为0，返回0；Q为正数返回Q，因为如果以0替换此时AN-1中的任一个数，所得到的PN-1为0，必然小于Q；Q为负数如果以0替换此时AN-1中的任一个数，所得到的PN-1为0，大于Q，乘积最大值为0。2. P为负数根据“负负得正”的乘法性质，自然想到从N个整数中去掉一个负数，使得PN-1为一个正数。而要使这个正数最大，这个被去掉的负数的绝对值必须是数组中最小的。我们只需要扫描一遍数组，把绝对值最小的负数给去掉就可以了。3. P为正数类似地，如果数组中存在正数值，那么应该去掉最小的正数值，否则去掉绝对值最大的负数值。14 上面的解法采用了直接求N个整数的乘积P，进而判断P的正负性的办法，但是直接求乘积在编译环境下往往会有溢出的危险（这也就是本题要求不使用除法的潜在用意），事实上可做一个小的转变，不需要直接求乘积，而是求出数组中正数（+）、负数（-）和0的个数，从而判断P的正负性，其余部分与以上面的解法相同。在时间复杂度方面，由于只需要遍历数组一次，在遍历数组的同时就可得到数组中正数（+）、负数（-）和0的个数，以及数组中绝对值最小的正数和负数，时间复杂度为O（N）。14 9月15日，中兴面试：小端系统union 14 int i; 14 unsigned char ch2; 14 Student; 141414 int main() 14 14 Student student; 14 student.i=0x1420; 14 printf(%d %d,student.ch0,student.ch1); 14 return 0; 14 15 输出结果为？（答案：32 20）16 一道有趣的Facebook面试题：给一个二叉树，每个节点都是正或负整数，如何找到一个子树，它所有节点的和最大？ 点评：某猛将兄:后序遍历，每一个节点保存左右子树的和加上自己的值。额外一个空间存放最大值。陈利人：同学们，如果你面试的是软件工程师的职位，一般面试官会要求你在短时间内写出一个比较整洁的，最好是高效的，没有什么bug的程序。所以，光有算法不够，还得多实践。写完后序遍历，面试官可能接着与你讨论，a). 如果要求找出只含正数的最大子树，程序该如何修改来实现？b). 假设我们将子树定义为它和它的部分后代，那该如何解决？c). 对于b，加上正数的限制，方案又该如何？总之，一道看似简单的面试题，可能能变换成各种花样。比如，面试管可能还会再提两个要求：第一，不能用全局变量；第一，有个参数控制是否要只含正数的子树。其它的，随意，当然，编程风格也很重要。17 谷歌面试题：有几百亿的整数，分布的存储到几百台通过网络连接的计算机上，你能否开发出一个算法和系统，找出这几百亿数据的中值？就是在一组排序好的数据中居于中间的数。显然，一台机器是装不下所有的数据。也尽量少用网络带宽。18 小米，南京站笔试（原第20题）：一个数组里，数都是两两出现的，但是有三个数是唯一出现的，找出这三个数。点评：3个数唯一出现，各不相同。由于x与a、b、c都各不相同，因此xa、xb、xc都不等于0。具体答案请参看这9月19日，IGT面试：你走到一个分叉路口，有两条路，每个路口有一个人，一个说假话，一个说真话，你只能问其中一个人仅一个问题，如何问才能得到正确答案？点评：答案是，问其中一个人：另一个人会说你的路口是通往正确的道路么？19 9月19日，创新工厂笔试题：给定一整型数组，若数组中某个下标值大的元素值小于某个下标值比它小的元素值，称这是一个反序。即：数组a; 对于i aj,则称这是一个反序。给定一个数组，要求写一个函数，计算出这个数组里所有反序的个数。点评：归并排序，至于有的人说是否有O（N）的时间复杂度，我认为答案是否定的，正如老梦所说，下限就是nlgn，n个元素的数组的排列共有的排列是nlgn，n！（算法导论里面也用递归树证明了：O(n*logn)是最优的解法，具体可以看下这个链接：）。然后，我再给一个链接，这里有那天笔试的两道题目：19 9月20日，创新工厂南京站笔试：已知字符串里的字符是互不相同的，现在任意组合，比如ab，则输出aa，ab，ba，bb，编程按照字典序输出所有的组合。点评：非简单的全排列问题（跟全排列的形式不同,abc 全排列的话，只有个不同的输出：19 本题可用递归的思想，设置一个变量表示已输出的个数，然后当个数达到字符串长度时，就输出。/假设str已经有序，from 一直很安静 19 void perm(char *str, int size, int resPos) 19 19 if(resPos = size) 19 print(result); 19 else 19 19 for(int i = 0; i 0) 19 19 a = a + b; 19 c+; 19 19 printf(%d, c); 19 20 问：最后程序输出是多少？点评：此题有陷阱，答题需谨慎！21 9月21日晚，海豚浏览器笔试题：有两个序列A和B,A=(a1,a2,.,ak),B=(b1,b2,.,bk),A和B都按升序排列，对于1=i,j=k，求k个最小的（ai+bj），要求算法尽量高效。22 9月22日上午，百度西安站全套笔试题如下：3.算法与程序设计第一题：某个公司举行一场羽毛球赛，有1001个人参加，现在为了评比出“最厉害的那个人”，进行淘汰赛，请问至少需要进行多少次比赛。第二题有100个灯泡，第一轮把所有灯泡都开启，第二轮把奇数位的灯泡灭掉，第三轮每隔两个灯泡，灭一个，开一个，依此类推。求100轮后还亮的灯泡。点评：完全平方数，本人去58面试时，也遇到过与此类似的题。第三题有20个数组，每个数组里面有500个数组，降序排列，每个数字是32位的unit,求出这10000个数字中最大的500个。4.系统设计题类似做一个手机键盘，上面有1到9个数字，每个数字都代表几个字母（比如1代表abc三个字母，z代表wxyz等等），现在要求设计当输入某几个数字的组合时，查找出通讯录中的人名及电话号码。其它的还有三道简答题，比如线程的死锁，内存的管理等等。最后，附一讨论帖子：23 9月22日，微软笔试：T(n)=1(n=1),T(n) = 25*T(n/5) + n2，求算法的时间复杂度。更多题目请参见：9月23日，腾讯校招部分笔试题(特24 点评：根号九说，不过最后两道大的附加题，全是秒杀99%海量数据处理面试题里的：25 9月23日，搜狗校招武汉站笔试题：一、已知计算机有以下原子操作1、 赋值操作：b = a;2、 +a和a+1;3、for( ) *有限循环；4、操作数只能为0或者正整数；5、定义函数实现加减乘操作二、对一个链表进行排序，效率越高越好，LinkedList.26 100个任务，100个工人每人可做一项任务，每个任务每个人做的的费用为t100100,求一个分配任务的方案使得总费用最少。点评：匈牙利算法，26 9月24日，Google南京等站全套笔试题如下：点评：谷歌的笔试从易到难，基础到复杂，涵盖操作系统 网络 数据结构 语言 数学思维 编程能力 算法能力，基本上能把一个人的能力全面考察出来。至于上述2.1寻找3个数的中位数,请看读者sos-phoenix给出的思路及代码：2.1 / 采用两两比较的思路（目前没想到更好的） 26 if (a = b) 26 if (b = c) 26 return b; 26 else 26 if (a =c) 26 return c; 26 else 26 return a; 26 26 26 else 26 if (a = c) 26 return a; 26 else 26 if (b = c) 26 return c; 26 else 26 return b; 26 26 27 最坏情况下的比较次数：3 （次）平均情况下的比较次数：(22 + 4*3)/6 = 8/3 （次）此外这题，微博上的左耳朵耗子后来也给出了一个链28 读者来信，提供的几个hulu面试题：9月19号,hulu电面：问题1 两个骰子，两个人轮流投，直到点数和大于6就停止，最终投的那个人获胜。问先投那个人获胜概率？问题2 平面上n个圆，任意两个都相交，是否有一条直线和所有的圆都有交点。9月22号,上午hulu面试问题1 100个人，每人头上戴一顶帽子，写有0.99的一个数，数可能重复，每个人都只能看到除自己以外其他人的帽子。每个人需要说出自己的帽子的数，一个人说对就算赢。问题2 n台机器，每台有负载，以和负载成正比的概率，随机选择一台机器。问题3 行列都递增的矩阵，求中位数。29 西安百度软件研发工程师：一面(2012.9.24)：问的比较广，涉及操作系统、网络、数据结构。比较难的就2道题。(1)10亿个int型整数，如何找出重复出现的数字；(2)有2G的一个文本文档，文件每行存储的是一个句子，每个单词是用空格隔开的。问：输入一个句子，如何找到和它最相似的前10个句子。（提示：可用倒排文档）。二面(2012.9.25)：(1)一个处理器最多能处理m个任务。现在有n个任务需要完成，每个任务都有自己完成所需的时间。此外每个任务之间有依赖性，比如任务开始执行的前提是任务必须完成。设计一个调度算法，使得这n这任务的完成时间最小；(2)有一个排序二叉树，数据类型是int型，如何找出中间大的元素；(3)一个N个元素的整形数组，如何找出前K个最大的元素。(4)给定一个凸四边形，如何判断一个点在这个平面上。运维部(2012.9.27)：(1)堆和栈的区别；(2)问如何数出自己头上的头发。30 9月25日，人人网笔试题：31 9月25日晚，创新工场校园招聘北邮站笔试：32 9月25日，小米大连站笔试题：1一共有100万，抽中的2万，每月增加4万，问20个月能抽中的概率为：？2 for(int i=0;istrlen(s);i+)n+=I;时间复杂度O（n）3 手机wifi（A）.wifi ap.局域网（B）.路由器ADSL（C）.互联网.服务器 断掉上述ABC哪些点TCP链接会立刻断掉？4 12345入栈，出栈结果 21543 31245 43215 12534 可能的为？(第一个和第三个)5 xn+a1xn-1+an-1x+an,最少要做乘法？题目中a1，a2，an为常数。33 9月26日，百度一二面：1、给定一数组，输出满足2a=b（a，b代表数组中的数）的数对，要求时间复杂度尽量低。2、搜索引擎多线程中每个线程占用多少内存？如果搜索引擎存储网页内存占用太大怎么解决？3、有很多url，例如*，* .现在给你一个 快速匹配出是*。点评：老题，此前blog内曾整理过。4、找出字符串的编辑距离，即把一个字符串s1最少经过多少步操作变成编程字符串s2，操作有三种，添加一个字符，删除一个字符，修改一个字符（只要听过编辑距离，知道往动态规划上想，很快就可以找到解法）。5、编程实现memcopy，注意考虑目标内存空间和源空间重叠的时候。6、实现简单的一个查找二叉树的深度的函数。34 9月26日晚，优酷土豆笔试题一道：优酷是一家视频网站，每天有上亿的视频被观看，现在公司要请研发人员找出最热门的视频。 该问题的输入可以简化为一个字符串文件，每一行都表示一个视频id，然后要找出出现次数最多的前100个视频id，将其输出，同时输出该视频的出现次数。 1.假设每天的视频播放次数为3亿次，被观看的视频数量为一百万个，每个视频ID的长度为20字节，限定使用的内存为1G。请简述做法，再写代码。 2.假设每个月的视频播放次数为100亿次，被观看的视频数量为1亿，每个视频ID的长度为20字节，一台机器被限定使用的内存为1G。 点评：有关海量数据处理的题目，请到此文中找方法(无论题目形式怎么变，基本方法不变，当然，最最常用的方法是：分而治之/Hash映射 + Hash统计 + 堆/快速/归并排序)：。注：上题第二问文件太大，则可如模1000，把整个大文件映射为1000个小文件再处理 .35 9月26日，baidu面试题：1.进程和线程的区别2.一个有序数组（从小到大排列），数组中的数据有正有负，求这个数组中的最小绝对值3.链表倒数第n个元素4.有一个函数fun能返回0和1两个值，返回0和1的概率都是1/2，问怎么利用这个函数得到另一个函数fun2，使fun2也只能返回0和1，且返回0的概率为1/4,返回1的概率为3/4。（如果返回0的概率为0.3而返回1的概率为0.7呢）5.有8个球，其中有7个球的质量相同，另一个与其他球的质量不同（且不知道是比其他球重还是轻），请问在最坏的情况下，最少需要多少次就能找出这个不同质量的球6.数据库索引7.有一个数组a，设有一个值n。在数组中找到两个元素ai和aj，使得ai+aj等于n，求出所有满足以上条件的i和j。8.1万个元素的数组，90%的元素都是1到100的数，10%的元素是101-10000的数，如何高效排序。36 小米的web开发笔试题：一场星际争霸比赛，共8个人，每个人的实力用分数表示，要分成两队，如何保证实力最平均？给定一个浮点数的序列，F1,F2,，Fn（1=n=1000）,定义P(s,e)为子序列Fi(s=i=e)的积，求P的最大值。37 9月27日，趋势科技面试题：马路口，30分钟内看到汽车的概率是95%，那么在10分钟内看不到汽车的概率是？38 9月27日晚，IGT笔试题：给定一个字符串里面只有R G B 三个字符，请排序，最终结果的顺序是R在前 G中 B在后。要求：空间复杂度是O(1)，且只能遍历一次字符串。点评：本质是荷兰国旗问题，类似快排中partition过程，38 9月27日，人人两面：一面 1 实现atoi 2 单链表变形 如 1 2 3 4 5 变为 1 3 5 4 2 如1 2 3 4 变为 1 3 4 2 (就是拆分链表 把偶数为反过来接在奇数位后面）二面 1 二叉树查找不严格小于一个值的最大值（返回节点）。 2 有序数组里二分查找一个数（如果有相同的找最后一次出现的）。 3 等价于n*n的矩阵，填写0，1，要求每行每列的都有偶数个1 （没有1也是偶数个），问有多少种方法。 评论：开始以为是算法题，想了狂搜，递推(dp，可以用xor表示一行的列状态，累加),分治，（拆两半，然后上半段下半段的列有相同的奇偶性）。后来，自己算了几个发现n = 1 n = 2 n = 3 的结果，他告诉了我n = 4是多少，然后发现f(n) = 2(n - 1) 2) 。最后我给出了一个巧妙的证明。然后发现如果是m*n的矩阵也是类似的答案，不局限于方阵。此外，题目具体描述可以看看这里：38 9月27日，小米两面：一面：除了聊研究，就一道题 1 数组里找到和最接近于0的两个值。二面： 1 行列有序的矩阵查找一个数 2 直方图最大矩形。点评：这里有此题的具体表述及一份答案： 3 next_permutation 4 字符串匹配 含有* ? （写代码） 5 实现strcpy memmove (必须写代码）/void * memmove ( void * destination, const void * source, size_t num );) 38 /是的标准函数，其作用是把从source开始的num个字符拷贝到destination。 38 /最简单的方法是直接复制，但是由于它们可能存在内存的重叠区，因此可能覆盖了原有数据。 38 /比如当source+count=dest&sourcedest时，dest可能覆盖了原有source的数据。 38 /解决办法是从后往前拷贝。 38 /对于其它情况，则从前往后拷贝。 38 void* memmove(void* dest, void* source, size_t count) 38 3838 void* ret = dest; 3838 if (dest = (source + count) 38 38 /正向拷贝 38 /copy from lower addresses to higher addresses 38 while (count -) 38 *dest+ = *source+; 38 38 else 38 38 /反向拷贝 38 /copy from higher addresses to lower addresses 38 dest += count - 1; 38 source += count - 1; 3838 while (count-) 38 *dest- = *source-; 38 38 return ret; 38 39 6 读数 （千万亿，百万亿）变为数字 （说思路即可，字符串查找，填写各个权值的字段，然后判断是否合法，读前面那些权值，累加）。40 9月27日，Hulu 2013北京地区校招笔试题填空题：1、中序遍历二叉树，结果为ABCDEFGH，后序遍历结果为ABEDCHGF，那么前序遍历结果为?2、对字符串HELL0_HULU中的字符进行二进制编码，使得字符串的编码长度尽可能短，最短长度为？3、对长度12的有序数组进行二分查找，目标等概率出现在数组的每个位置上，则平均比较次数为？4、一副扑克（去王），每个人随机的摸两张，则至少需要多少人摸牌，才能保证有两个人抽到同样的花色。5、x个小球中有唯一一个球较轻，用天平秤最少称量y次能找出这个较轻的球，写出y和x的函数表达式y=f(x)6、3的方幂及不相等的3的方幂的和排列成递增序列1,3,4,9,10,12,13，写出数列第300项7、无向图G有20条边，有4个度为4的顶点，6个度为3的顶点，其余顶点度小于3，则G有多少个顶点8、桶中有M个白球，小明每分钟从桶中随机取出一个球，涂成红色（无论白或红都涂红）再放回，问小明将桶中球全部涂红的期望时间是？9、煤矿有3000吨煤要拿到市场上卖，有一辆火车可以用来运煤，火车最多能装1000吨煤，且火车本身需要烧煤做动力，每走1公里消耗1吨煤，如何运煤才能使得运到市场的煤最多，最多是多少？10、1,2,3,4.n，n个数进栈，有多少种出栈顺序，写出递推公式（写出通项公式不得分）11、宇宙飞船有100,000位的存储空间，其中有一位有故障，现有一种Agent可以用来检测故障，每个Agent可以同时测试任意个位数，若都没有故障，则返回OK，若有一位有故障，则失去响应。如果有无限多个Agent可供使用，每个Agent进行一次检测需要耗费1小时，现在有2个小时时间去找出故障位，问最少使用多少个Agent就能找出故障。（总共12道填空题，还有一道太复杂，题目很长，还有示意图，这里没有记录下来）大题：1、n个数，找出其中最小的k个数，写出代码，要求最坏情况下的时间复杂度不能高于O(n logk)2、写程序输出8皇后问题的所有排列，要求使用非递归的深度优先遍历3、有n个作业，a1,a2.an，作业aj的处理时间为tj，产生的效益为pj，最后完成期限为dj，作业一旦被调度则不能中断，如果作业aj在dj前完成，则获得效益pj，否则无效益。给出最大化效益的作业调度算法。41 有道的一个笔试题，1-9，9个数组成三个三位数，且都是完全平方数（三个三位数 占据 9个数）求解法。42 点评林晚枫&归云见鸿：(a*10+b)(a*10+b)100a2+20ab+b2a 属于 1,2,3a=3,b=1 31 961,a=2,b=3 23 529 400+40b+b225 62527 72928 78429 841a=1,b=3 13 169 100+20b+b214 19616 25617 28918 32419 361=最终唯一解 529 784 361具体代码如下（3个for循环，然后hash）：43 9月28日，大众点评北京笔试题目：1.一个是跳台阶问题，可以1次一级，1次两级，1次三级，求N级的跳法一共多少种？ 点评：老题，44 2.一个文件有N个单词，每行一个，其中一个单词出现的次数大于N/2，怎么样才能快速找出这个单词？ 点评：还是老题，45 大众点评前面还有30道逻辑题，15道文字推理，15道数学推理，一共只给20min。46 9月28日，网易笔试题：1、英雄升级，从0级升到1级，概率100%。从1级升到2级，有1/3的可能成功；1/3的可能停留原级；1/3的可能下降到0级；从2级升到3级，有1/9的可能成功；4/9的可能停留原级；4/9的可能下降到1级。每次升级要花费一个宝石，不管成功还是停留还是降级。求英雄从0级升到3级平均花费的宝石数目。点评：题目的意思是，从第n级升级到第n+1级成功的概率是(1/3)n（指数），停留原级和降级的概率一样，都为1-(1/3)n/2）。2、将一个很长的字符串，分割成一段一段的子字符串，子字符串都是回文字符串。有回文字符串就输出最长的，没有回文就输出一个一个的字符。例如：habbafgh输出h,abba,f,g,h。点评：一般的人会想到用后缀数组来解决这个问题，47 10月9日，腾讯一面试题：有一个log文件，里面记录的格式为： QQ号： 时间： flag：如123456 14：00：00 0 123457 14：00：01 1其中flag=0表示登录 flag=1表示退出问：统计一天平均在线的QQ数。 点评：第8题后的腾讯面试题，读者可以参看之。 48 10月9日，腾讯面试题：1.有一亿个数，输入一个数，找出与它编辑距离在3以内的书，比如输入6（0110），找出0010等数，数是32位的。2.每个城市的IP段是固定的，新来一个IP，找出它是哪个城市的，设计一个后台系统。49 10月9日，YY笔试题：1 输出一个字符串中没有重复的字符。如“baaca”输出“bac”。2 对于一个多叉树，设计TreeNode节点和函数，返回先序遍历情况下的下一个节点。函数定义为TreeNode* NextNode（TreeNode* node）3 分割字符串。对于一个字符串，根据分隔符seperator，把字符串分割，如果存在多个分隔符连在一起，则当做一个分隔符。如果分隔符出现在 符号之间，则不需要分割 之间的字符。比如a+abc ，分隔符为+，输出a abca+hu+ 输出a hu+a+HU+JI 输出a HU JI。请根据上述需求完成函数：void spiltString(string aString，char aSeperator)。50 10月9日，赶集网笔试51 10月9日，阿里巴巴2013校园招聘全套笔试题（注：下