2011-2012年腾讯，创新工场，淘宝，百度，阿里，迅雷。网易游戏校园招聘面试题集锦(1-25题含答案)又是一年招聘季，小鸟我也在本季参加招聘，所以特在网上和群里面这里去年和今年的面试题，以备战招聘，有些题可能答案有问题，希望大家分享自己的答案和意见，也可以留言提供一些面试题，谢谢大家了。1.五只猴子分桃。半夜，第一只猴子先起来，它把桃分成了相等的五堆，多出一只。于是，它吃掉了一个，拿走了一堆； 第二只猴子起来一看，只有四堆桃。于是把四堆合在一起，分成相等的五堆，又多出一个。于是，它也吃掉了一个，拿走了一堆；.....其他几只猴子也都是 这样分的。问：这堆桃至少有多少个？参考答案：先给这堆桃子加上4个,设此时共有X个桃子,最后剩下a个桃子.这样: 第一只猴子分完后还剩:(1-1/5)X=(4/5)X; 第二只猴子分完后还剩:(1-1/5)2X;第三只猴子分完后还剩:(1-1/5)3X;第四只猴子分完后还剩:(1-1/5)4X;第五只猴子分完后还剩:(1-1/5)5X=(1024/3125)X;得:a=(1024/3125)X;要使a为整数,X最小取3125.减去加上的4个,所以,这堆桃子最少有3121个。2.已知有个rand7()的函数，返回1到7随机自然数，让利用这个rand7()构造rand10() 随机1~10。（参考答案：这题主要考的是对概率的理解。程序关键是要算出rand10，1到10，十个数字出现的考虑都为10%.根据排列组合，连续算两次rand7出现的组合数是7*7=49，这49种组合每一种出现考虑是相同的。怎么从49平均概率的转换为1到10呢？方法是：1.rand7执行两次，出来的数为a1.a2.2.如果a1*7+a2<40,b=(a1*7+a2)/10+1,如果a1*7*a2>=40,重复第一步）。参考代码如下所示： 01.int rand7() 02.{ 03. return rand()%7+1; 04.} 05. 06.int rand10() 07.{ 08. int a71,a72,a10; 09. do 10. { 11. a71= rand7()-1; 12. a72 = rand7()-1; 13. a10 = a71 *7 + a72; 14. } while (a10>= 40); 15. return (a71*7+a72)/4+1; 16.} 3.如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串，问如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）。01./* 02.如果两个字符串的字符一样，但是顺序不一样，被认为是兄弟字符串， 03.问如何在迅速匹配兄弟字符串（如，bad和adb就是兄弟字符串）。 04.*/ 05.#include <iostream> 06.using namespace std; 07. 08.int isBroStr(char *str1, char *str2) 09.{ 10. int a[26 * 2] = {0}; 11. int i, strLen; 12. 13. if (!str1 && !str2) 14. return 1; 15. else if (!str1 || !str2) 16. return 0; 17. else 18. { 19. if(strlen(str1) != strlen(str2)) 20. return 0; 21. strLen = strlen(str1); 22. for(i = 0; i < strLen; i++) 23. { 24. ++a[str1[i] - 'A']; 25. --a[str2[i] - 'A']; 26. } 27. for(i = 0; i < 26 * 2; i++) 28. if (a[i]) 29. return 0; 30. return 1; 31. } 32.} 33. 34.int main() 35.{ 36. char *str1 = "asdfaabAAB"; 37. char *str2 = "asdfAABaab"; 38. if (isBroStr(str1, str2)) 39. cout << " String 1 and String 2 are brothers!" << endl; 40. else 41. cout << " String 1 and String 2 are not brothers!" << endl; 42. system("PAUSE"); 43. return 0; 44.} 4.要求设计一个DNS的Cache结构，要求能够满足每秒5000以上的查询，满足IP数据的快速插入，查询的速度要快每秒5000的查询不算高啊，最土的方法使用MySQL+Memcached架构应该都能满足吧？
数据结构建议以域名的md5值为主键来存储，值可以只存储目标IP就行。Memcached用户支撑前端查询，MySQL用户存储数据，还要看总书量会有多大，如果不是特别大，直接使用MyISAM引擎来存储就行，更新插入都非常快，如果超千万，可以使用InnoDB来存储，每次有新数据插入时直接使用replace into table就行，Memcached数据的更新直接使用set。
Memcached随便用得好些，每秒上万次的get是容易达到的，MySQL你别小看，在有的测试里，以主键查询的测试，一台普通的服务器上，MySQL/InnoDB 5.1服务器上获得了750000+QPS的成绩。5.淘宝面试题：有一个一亿节点的树，现在已知两个点，找这两个点的共同的祖先。node *LCA(node* root,node *p ,node *q){node* temp;while(p!=NULL){ p=p->parent; temp = q; while(temp!=NULL) { if(p==temp->parent) return p; temp = temp->parent;}}}6.某服务器流量统计器，每天有1000亿的访问记录数据，包括时间、url、ip。设计系统实现记录数据的保存、管理、查询。要求能实现一下功能：（1）计算在某一时间段（精确到分）时间内的，某url的所有访问量。（2）计算在某一时间段（精确到分）时间内的，某ip的所有访问量。答案参见下题。7.假设某个网站每天有超过10亿次的页面访问量，出于安全考虑，网站会记录访问客户端访问的ip地址和对应的时间，如果现在已经记录了1000亿条数据，想统计一个指定时间段内的区域ip地址访问量，那么这些数据应该按照何种方式来组织，才能尽快满足上面的统计需求呢，设计完方案后，并指出该方案的优缺点，比如在什么情况下，可能会非常慢？（参考答案：用B+树来组织，非叶子节点存储（某个时间点，页面访问量），叶子节点是访问的IP地址。这个方案的优点是查询某个时间段内的IP访问量很快，但是要统计某个IP的访问次数或是上次访问时间就不得不遍历整个树的叶子节点。或者可以建立二级索引，分别是时间和地点来建立索引。）8.腾讯最新面试题：服务器内存1G，有一个2G的文件，里面每行存着一个QQ号（5-10位数），怎么最快找出出现过最多次的QQ号。首先你要注意到，数据存在服务器，存储不了（内存存不了），要想办法统计每一个qq出现的次数。比如，因为内存是1g，首先 你用hash 的方法，把qq分配到10个（这个数字可以变动，比较）文件（在硬盘中）。相同的qq肯定在同一个文件中，然后对每一个文件，只要保证每一个文件少于1g的内存，统计每个qq的次数，可以使用hash_map(qq, qq_count)实现。然后，记录每个文件的最大访问次数的qq，最后，从10个文件中找出一个最大，即为所有的最大。9.腾讯2.如何求根号2的值，并且按照我的需要列出指定小数位，比如根号2是1.141 我要列出1位小数就是1.1 2位就是1.41， 1000位就是1.414...... 等。。#include <stdio.h>
double sqrtn(int n, int m){ long double ln = n*1.0; long double left = 0; long double right = ln; long double err = 1, mid; for(int i=0;i<m;i++) { err *= 0.1; } while(true) { mid = (left + right) / 2; if(mid*mid > ln) { right = mid; } else if(mid*mid < ln) { left = mid; } else {int res = (int)(mid/err); return res*err; } if(right - left < err) {int res = (int)(mid/err); return res*err; } }}
void main(){long double res = sqrtn(2,8);printf("%.10f\n",res);}10.给定一个字符串的集合，格式如：{aaa bbb ccc}， {bbb ddd}，{eee fff}，{ggg}，{ddd hhh}要求将其中交集不为空的集合合并，要求合并完成后的集合之间无交集，例如上例应输出{aaa bbb ccc ddd hhh}，{eee fff}， {ggg}。查了查网上的解法，只看到一个（参见http://blog.csdn.net/lillllllll/article/details/4162605），有网上一位仁兄做了以下改进，说明如下：1. 首先得到所有元素的集合（aaa, bbb, ccc, ddd, eee, fff, ggg, hhh），复杂度O(N)，N是所有元素的个数；2. 为所有集合标记一个二进制数，来表示包含哪些集合，得到数组int bina[5]复杂度O(N^2)；如题，{aaa, bbb, ccc} = 1 1 1 0 0 0 0 0，{bbb, ddd} = 0 1 0 1 0 0 0 0，{eee, fff} = 0 0 0 0 1 1 0 0，{ggg} = 0 0 0 0 0 0 1 0，{ddd, hhh} = 0 0 0 1 0 0 0 1，3. 然后写一个函数，判断int数组中的第一个元素是否与其他元素&操作为空，复杂度为O（M），M是原集合的个数a. 为空则输出该元素对应的集合，并删除第一个元素，递归调用本方法；b. 不为空则与那个元素做或操作合并，删除那个元素，递归调用本方法；c. 如果只剩下一个元素则输出其对应的字符串；4. 所有的结合已经得到了。
11.创新工场面试题：abcde五人打渔，打完睡觉，a先醒来，扔掉1条鱼，把剩下的分成5分，拿一份走了；b再醒来，也扔掉1条，把剩下的分成5份，拿一份走了；然后cde都按上面的方法取鱼。问他们一共打了多少条鱼，写程序和算法实现。提示：共打了多少条鱼的结果有很多。但求最少打的鱼的结果是3121条鱼（应该找这5个人问问，用什么工具打了这么多条鱼）。本题和第一题一样；#include <iostream> using namespace std; int main() { int e, d, c, b, a; for(int i = 0, f = 0; i < 1/* 改?为a1就¨ª是º?最Á?小?答äe案ã? */; ++i, ++f){ for(; true; ++f){ if(f % 4){ continue; } e = f / 4 * 5 + 1; //从最后一个人开始 如果刚好合适 至少要有 if(e % 4){ continue; } d = e / 4 * 5 + 1; if(d % 4){ continue; } c = d / 4 * 5 + 1; if(c % 4){ continue; } b = c / 4 * 5 + 1; if(b % 4){ continue; } a = b / 4 * 5 + 1; break; } } cout << "a = " << a << '\n'; return 0; } 12.我们有很多瓶无色的液体，其中有一瓶是毒药，其它都是蒸馏水，实验的小白鼠喝了以后会在5分钟后死亡，而喝到蒸馏水的小白鼠则一切正常。现在有5只小白鼠，请问一下，我们用这五只小白鼠，5分钟的时间，能够检测多少瓶液体的成分？解答；把五个老鼠看成5位二进制位： 5 4 3 2 1第一瓶 0 0 0 0 1第二瓶 0 0 0 1 0第三瓶 0 0 0 1 1….第31瓶 1 1 1 1 1相应位的老鼠死了就可以判断是第几瓶有毒；13.在一维坐标轴上有n个区间段，求重合区间最长的两个区间段http://blog.csdn.net/julianxiong/article/details/733832314.请使用代码计算1234567891011121314151617181920*2019181716151413121110987654321大数相乘问题：#include <iostream> #include <string.h> using namespace std; void multiply(const char *a,const char *b); int main() { //cout<<"hicjiajia"<<endl; string num1,num2; // 初始状态用string来存储大数 cout<<"现在，来两个大数吧！ "<<endl; cin>>num1>>num2; const char *p1=num1.c_str(); // 将string转为 const char * const char *p2=num2.c_str(); // 将string转为 const char * multiply(p1,p2); system("pause"); return 0; } void multiply(const char *a,const char *b) { int i,j,ca,cb,*s; ca=strlen(a); cb=strlen(b); s=(int *)malloc(sizeof(int)*(ca+cb)); //分配存储空间 for (i=0;i<ca+cb;i++) s[i]=0; // 每个元素赋初值0 for (i=0;i<ca;i++) for (j=0;j<cb;j++) s[i+j+1]+=(a[i]-'0')*(b[j]-'0'); for (i=ca+cb-1;i>=0;i--) // 这里实现进位操作 if (s[i]>=10) { s[i-1]+=s[i]/10; s[i]%=10; } char *c=(char *)malloc((ca+cb)*sizeof(char)); //分配字符数组空间，因为它比int数组省！ i=0;while(s[i]==0) i++; // 跳过头部0元素 for (j=0;i<ca+cb;i++,j++) c[j]=s[i]+'0'; c[j]='\0'; for (i=0;i<ca+cb;i++) cout<<c[i]; cout<<endl; free(s); }15.1分2分5分的硬币，组成1角，共有多少种组合设1分个数为x，2分个数为y，5分的硬币个数为z，则1*x+2*y+5*z=10；5*z=10-x-2*y；即：z x对应可能的取值0 10 8 6 4 2 0（6个）1 5 3 1（3个）2 0（1个）总共个数为6+3+1=10.因此，按照规律，本题目组合总数为10以内的偶数+5以内的奇数+0以内的偶数某个偶数m以内的偶数个数（包括0）可以表示为m/2+1=(m+2)/2某个奇数m以内的奇数个数也可以表示为(m+2)/2
所以，求总的组合次数可以编程为：number=0;for (int m=0;m<=10;m+=5){number+=(m+2)/2;}cout<<number<<endl;这样程序是不是简单多了（只需要累加3次，而上面的3层循环呢？大家自己想想）。别人考你肯定不是考你会不会编这个程序，是考你如何去使程序的复杂度降低。6分、4分、2分组成100分怎么处理？2分为x，4分为y，6分为z。则6*z=100-2*x-4*y，可化简为：3*z=50-x-2*yz可能的取值为0、1、2•••16，当z=0时，x可以为50 48 46•••2 0（26个）当z=1时，x可以为47 45 43•••3 1（24个）当z=2时，x可以为44 42 40•••2 0（23个）当z=3时，x可以为41 39 37•••3 1（21个）…当z=15时，x可以为5 3 1（3个）当z=16时，x可以为2 0（2个）
因此，按照规律，本题目组合总数为50以内的偶数+47以内的奇数+44以内的偶数+•••+5以内的奇数+2以内的偶数某个偶数m以内的偶数个数（包括0）可以表示为m/2+1=(m+2)/2某个奇数m以内的奇数个数也可以表示为(m+2)/2
所以，求总的组合次数可以编程为：number=0;for (int m=0;m<=50;m+=3){number+=(m+2)/2;}cout<<number<<endl;是不是可以看出规律了呢？实际上就是看表达式（这里是3*z=50-x-2*y），就是把最大乘数（这里是3）放在一边，这也是m增加的步长。而m的最大取值也就是表达式中的这个常数。16.解释下面ptr含义和不同double* ptr = &value;//ptr是一个指向double类型的指针，ptr的值可以改变，ptr所指向的value的值也可以改变 const double* ptr = &value//ptr是一个指向const double类型的指针，ptr的值可以改变，ptr所指向的value的值不可以改变double* const ptr=&value//ptr是一个指向double类型的指针，ptr的值不可以改变，ptr所指向的value的值可以改变const double* const ptr=&value//ptr是一个指向const double类型的指针，ptr的值不可以改变，ptr所指向的value的值也不可以改变2、去掉const属性，例： const double value = 0.0f; double* ptr = NULL;怎么才能让ptr指向value？强制类型转换，去掉const属性，如ptr = <const_cast double *>(&value);
17.如果用一个循环数组q[0..m-1]表示队列时,该队列只有一个队列头指针front,不设队列尾指针rear，求这个队列中从队列投到队列尾的元素个数（包含队列头、队列尾）（华赛面试题、腾讯笔试题）。貌似没有找到很好的解法，只能设置一个count计数；
18题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词以空格符隔开。为简单起见，标点符号和普通字母一样处理。例如输入“I am a student.”，则输出“student. a am I”。这种题是很无聊的，而且用istream什么就没有可以做的了，思路：倒着遍历字符串，查找到一个空格后，输出本空格与上次空格之间的内容。可以用\0临时替代printf#include <stdio.h>#include <stdlib.h>#include <string.h>
#define MAX 1024
void reverse_print(char* str){// Get lenint len = strlen(str);int i = len-1;int last = len;char tmp;// Find from last to firstwhile(i>=0){if( str[i]==' ' || i==0){tmp = str[last];str[last] = '\0';if(i==0 && str[i]!=' '){printf("%s ", str+i);}else{printf("%s ", str+i+1);}str[last] = tmp;last = i;}i--;}}
int main(){char* buf = NULL;int len = 0;len = getline(&buf, &len, stdin);if(len==-1){printf("getline error.\n");return -1;}else{buf[len] = '\0';buf[len-1] = '\0'; // \nreverse_print(buf);if(buf){free(buf);}}return 0;}
19.十月百度：一个数组保存了N个结构，每个结构保存了一个坐标，结构间的坐标都不相同，请问如何找到指定坐标的结构（除了遍历整个数组，是否有更好的办法）？（要么预先排序，二分查找。要么哈希。hash的话，坐标(x,y)你可以当做一个2位数，写一个哈希函数，把（x,y）直接转成“(x,y)”作为key，默认用string比较。或如Edward Lee所说，将坐标(x, y)作为 Hash 中的 key。例如(m, n)，通过 (m,n) 和 (n, m) 两次查找看是否在 HashMap 中。也可以在保存时就规定 (x, y) , x < y ，在插入之前做个判断。）
20.（1的数目）给定义个十进制正整数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有1的个数。例如N=12，我们会有1,10,11,12, 1的个数为5解答：假设N=abcde,这里a,b,c,d,e分别是十进制数N的各个数位上的数字。如果要计算百位上出现的1的次数，它将会受到三个因素的影响：百位上1的数字，百位以下（低位）的数字，百位（更高位）以上的数字。如果百位数为0，如12013，则百位出现1的情况有12*当前位数（100）如果百位数为1，如12113，则百位出现1的情况有12*100+114如果百位数不为1，如12213，则百位出现1的情况有（12+1）*100实现代码：#include<iostream>using namespace std;int sum1s(int n){int lowerNum = 0;int currNum = 0;int highNum = 0;int i = 1;int count = 0;while(n/i != 0){lowerNum = n-(n/i)*i;currNum = (n/i)%10;highNum =n/(i*10);switch(currNum){case 0:count +=highNum*i;break;case 1:count +=highNum*i + (lowerNum+1);break;default:count +=(highNum+1)*i;break;}i*=10;}return count;}void main(){int num;while(cin>>num)cout<<sum1s(num)<<endl;}21相信大家都使用过百度搜索框的suggestion功能(如下图所示)。百度搜索框中的suggestion提示功能如何实现的？请给出实现思路和主要的数据结构、算法。有什么优化思路可以使得时间和空间效率最高？首先通过根据搜索日志，统计出热词出现的次数。同时还需加入一些常用词语。将热词和常用词语赋予一定的权重，做一棵trie数。根据用户输入的单词，去trie书中进行匹配，然后取其权重最高的前K个，取前k个，可以采用top k算法。22腾讯实习生笔试题：两个数组a[N]，b[N]，其中A[N]的各个元素值已知，现给b[i]赋值，b[i] = a[0]*a[1]*a[2]...*a[N-1]/a[i]；要求：1.不准用除法运算2.除了循环计数值，a[N],b[N]外，不准再用其他任何变量（包括局部变量，全局变量等）3.满足时间复杂度O（n），空间复杂度O（1）。解答：先从右往左推出b[i]右边的乘积和存到b[i]中，再从左往右推出b[i]左边的乘积和存到b[0]中，用b[i]*b[0]就是最后的结构，最后在计算b[0]就得出最后结果：#include <stdio.h>#define MAX 100int main (){ int n =0 ; int a[MAX]; int b[MAX]; int i; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",a+i); b[n-1]=1; b[0]=1; //计算右边成绩和 for(i=n-2;i>0;i--) b[i]=a[i+1]*b[i+1]; for(i=1;i<n;i++) { //保存左边乘积和 b[0]=b[0]*a[i-1]; //将本行两部分的值乘倒一起，得到最后结果 b[i]=b[i]*b[0]; } b[0]=1; for(i=1;i<n;i++) b[0]=b[0]*a[i]; for(i=0;i<n;i++) printf("%-9d",b[i]); printf("\n"); return 0 ;}23十月百度：一个数组保存了N个结构，每个结构保存了一个坐标，结构间的坐标都不相同，请问如何找到指定坐标的结构（除了遍历整个数组，是否有更好的办法）？解答：用hash_map实现，因为hash_map是用hash_table实现的，所有查询复杂度为O（1）24百度最新面试题：现在有1千万个随机数，随机数的范围在1到1亿之间。现在要求写出一种算法，将1到1亿之间没有在随机数中的数求出来。（编程珠玑上有此类似的一题，如果有足够的内存的话可以用位图法，即开一个1亿位的bitset，内存为100m/8== 12.5m, 然后如果一个数有出现，对应的bitset上标记为1，最后统计bitset上为0的即可。）25.设计包含min函数的栈。定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。#include <iostream>
using namespace std;
struct node{int data;int min;};
struct MinStack{node *data;int top;int size;};
MinStack initStack(int size){MinStack stack;stack.data = new node[size];stack.size = size;stack.top = 0;return stack;}
void freeStack(MinStack stack){delete[] stack.data;}int minStack(MinStack stack){if(0 == stack.top)return INT_MAX;return stack.data[stack.top-1].min;}void push(MinStack &stack, int data){if(stack.size == stack.top)return ;stack.data[stack.top].data = data;int tem = minStack(stack);stack.data[stack.top].min = min(data,tem);stack.top++;}
int pop(MinStack &stack){if(0 == stack.top)return 0;return stack.data[--stack.top].data;}
void main(){MinStack stack = initStack(5);push(stack,5);push(stack,4);push(stack,2);push(stack,3);int res = minStack(stack);cout<<res<<endl;freeStack(stack);}