2014年网易阿里腾讯 面试问题相关

http://blog.csdn.net/wendy260310/article/details/41039625

刚刚结束了找工作之旅，总结一下自己遇到的一些问题，可以给大家做一个参考。

1.回文数的判断，这个问题给的是一个long int而不是char *,这个是非常关键的，我写的代码如下

[cpp] view plaincopy

1. bool isreverse(long int inputNumber)  
2. {  
3. int reverse=0,temp=inputNumber;  
4. while(temp)  
5.     {  
6.         reverse=reverse*10+(temp%10);  
7.         temp/=10;  
8.     }  
9. return reverse==inputNumber;  
10. }  

这个被面试官批评了半天，原因是reverse可能会越界，他说你们写代码不能当成儿戏。最好的方法还是要把这个long int 转成char*。

2.关于二分查找的问题，二分查找虽然说简单，但是要想写对还是需要认真的。写完二分查找之后，又说如果数组中的元素有重复的，求第一个。

[cpp] view plaincopy

1. int binarySearch(int *inputArray,int key,int start,int end)  
2. {  
3. int mid;  
4. while(start<=end)  
5.     {  
6.         mid=start+((end-start)>>1);  
7. if(inputArray[mid]==key)  
8. return mid;  
9. else
10. if(inputArray[mid]>key)  
11.                 end=mid-1;  
12. else
13.                 start=mid+1;  
14.     }  
15. return NOT_FOUND;  
16. }  

第二个问题的代码:

[cpp] view plaincopy

1. int binarySearch(int *inputArray,int key,int start,int end)  
2. {  
3. int mid,first=start;  
4. while(start<=end)  
5.     {  
6.         mid=start+((end-start)>>1);  
7. if(inputArray[mid]==key&&(mid==first||inputArray[mid-1]<inputArray[mid]))  
8. return mid;  
9. else
10. if(inputArray[mid]>=key)  
11.                 end=mid-1;  
12. else
13.                 start=mid+1;  
14.     }  
15. return NOT_FOUND;  
16. }  

这两段代码仅仅作为参考，没有进行严格的边界检查，start和end都是闭区间，这个面试官也问了！

3.关于QQ聊天的时候是采用TCP还是UDP的问题，我这个不会，但是我自己的观点是采用UDP，如果采用TCP，那两个人聊天是采用长连接还是短连接呢，长连接的话，A和B说一句话就不说了，那连接就一直浪费了。短连接的问题也非常严重，每次发一个消息就要建立一次连接。UDP可以实现可靠的传输，我们可以在高层实现一个确认机制，我们注意到QQ有的时候会提示你消息发送失败应该就是确认的问题，可能是消息真的发送失败也可能是没有收到确认，还有就是我们可以看到QQ的消息有的时候不是顺序到达的，这也说明它不是TCP。个人观点，欢迎指正。

4.关于应用层协议解析，我们知道TCP是没有边界的，应用层协议就要对消息进行解析，问有没有设计过应用层的协议。这个是完全不会。

5.一个二叉树的问题，问题的描述如下：一个树有n个节点，每个节点的有一个数据表示该节点有几个石头，这棵树刚好有n个石头。现在的问题是，我希望进行调整(调整只发生在父亲和孩子之间），使得每个节点刚好有1个石头，求调整所需要的步长。步长的定义如下：父亲(孩子)向孩子(父亲）移动k个石头，那么就算是k步。参考代码：

[cpp] view plaincopy

1. int stepCount(Tree *root,int &contribution)  
2. {  
3. if(root==NULL)  
4.     {  
5.         contribution=0;  
6. return 0;  
7.     }  
8. int leftContribution,rightContribution,leftStepCount,rightStepCount;  
9.     leftStepCount=stepCount(root->left,leftContribution);  
10.     rightStepCount=stepCount(root->right,rightContribution);  
11.     contribution=leftContribution+rightContribution+root->stone-1;  
12. return abs(leftContribution)+abs(rightContribution)+leftStepCount+rightStepCount;  
13. }  

6.这个问题是要去掉字符数组中的指定的字符，这个问题是比较常见的问题了.

[cpp] view plaincopy

1. void removeChar(char *inputCharArray,char c)  
2. {  
3. int i=0,count=0;  
4. while(inputCharArray[i])  
5.     {  
6. if(inputCharArray[i]==c)  
7.             count++;  
8. else
9.             inputCharArray[i-count]=inputCharArray[i];  
10.         ++i;  
11.     }  
12. }  

7.关于malloc分配内存的问题，涉及到了指针越界的问题。linux内存的分布，brk系统调用等，这个话题建议看看相关的资料。

8.关于C++的一些基础问题：explicit和volatile的用法，dynamic_cast对指针和引用的使用问题。

9.一个长为L的木头，分为n段，这n段的长度已经指定，也就是说L1+L2+....+Ln=L的。下面用一个例子来示意分段的时候的费用计算方法：假设我现在有一个长为10的木头，想分为2，3，5这三段。第一次将10分为5和5，费用是10，第二次将5分为2，3费用是5，整个过程的费用是15。如果我第一次将10分为8和2，费用10，第二次将8分为5和3，那么费用是8，一共是18，这个题目的问题就是求最小的费用。这个问题实际是一个哈夫曼编码的问题，有些块的费用会重复的计算，重复计算的次数相当于根到叶子节点的路径长(注意到L1，L2，..Ln一定出现在叶子节点）。这个问题只要答出哈夫曼树就让过了。

2014年腾讯广研创新班笔试题(回忆的）

1.编程题。

数制转换的问题,A=1,B=2,C=3....Z=26,AA=27,输入一个字符串(ACDEDS)输出结果。

2.A,B两个人玩游戏,A写下一个【1，100】的数，让B来猜，如果B猜小了，那么A会告诉他猜小了，但是一旦某一次B猜大了，A就不再提示了，只是告诉B猜对了没有，请问B应该采用什么策略来猜，最少猜多少次，第一次应该猜几。

3.Ackerman函数问题,网上有递推。要求ACK(3,3)。

4.求数组子数组最大和(填空题，见编程之美).

5.二分查找(填空题)

6.catalan数，问的是进栈的顺序是1,2,3,4,5问合法的出栈序列有多少个。