腾讯C++后台招聘问题汇总与分享

1.前言

2016.4.11日广州天河区东圃喜来登酒店参加了Tencent CC++后台技术一面，面试官人很温和，经历了大概70分钟的问答，特将遇到的面试问题汇总如下，自己总结学习，亦供网友参考。

2.问题汇总

问题一：
不好意思，我有事，先处理一下，你先写个非递归二分查找。
答：
这个和上次CVTE面试的第一个问题相同，之前复习过。感觉很多面试的第一个问题都是先写段代码。因此，手写代码感觉很重要，因为这是给面试官的第一印象。除了二分查找，快排，链表反转，实现atoi()函数等等，在面试中也常被用来作为手写代码的考题。

//数组递增有序 int binarySearch(int* array,int len,int value){ int mid=0; int low=0; int high=len-1; while(low<=high){ mid=(low+high)/2; if(array[mid]==value) //找到 return mid; if(value>array[mid]) //在右半区 low=mid+1; else //在左半区 high=mid-1; } return -1; //查找失败 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

问题二：
（面试官一直在打电话）如果你写完了，你再写一个从数组中找出第二大的数。
答：
找第几大的数突然间想到了堆排序，因为自己之前练习过堆排序，所以就花了十分钟左右的时间写下了堆排序。写堆排序需要知道节点下标index的左子节点的下标为2*index+1，2*index+2。以数组构造堆的话是一个完全二叉树，数组长度为len，那么最后一个非叶子节点的下标是len/2-1。以堆排序来寻找第二大数参考代码如下：

//手写大顶堆排序求大二大数 void adjust(int A[],int index,int len){ if(index>len/2-1)//叶子节点，不同调整 return; int biggestIndex=0; if(2*index+2A[2*index+2]?2*index+1:2*index+2; else biggestIndex=2*index+1; if(A[index]index]=A[index]+A[biggestIndex]; A[biggestIndex]=A[index]-A[biggestIndex]; A[index]=A[index]-A[biggestIndex]; adjust(A,biggestIndex,len); }} void createMaxHeap(int A[],int len){ for(int i=len/2-1;i>=0;--i){ adjust(A,i,len); } } int getSecondMax(int A[],int len){ createMaxHeap(A,len); //建堆 for(int i=0;i<2;++i){ A[0]=A[0]+A[len-1-i]; A[len-1-i]=A[0]-A[len-1-i]; A[0]=A[0]-A[len-1-i]; adjust(A,0,len-1-i); } return A[len-2];}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

很显然，这个求解方法的时间复杂度是nlogn，不是较优解法，不是面试官想要的答案。面试官追问有没有更好的方法，时间复杂度是O(n)。

稍微想了一下，回答冒泡排序和简单选择排序可以在O(2n)的时间复杂度找到第二大的数。他试官说还有没有更快的方法呢？不要O(2n)，只要O(n)。

正确答案是：
保存最大值和第二大值，扫描一遍数组即可找到，也就是以空间换时间。冒泡排序和简单选择排序都需要扫描两遍。参考如下代码：

int getSecondMax(int array[],int len){ if(len<=1) return -1; int max=0,secondMax=0; if(array[0]>array[1]){ max=array[0]; secondMax=array[1]; }else{ max=array[1]; secondMax=array[0]; } for(int i=2;isecondMax) //新的第二大数 secondMax=array[i]; else max=array[i]; //最大数 } return secondMax;}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

问题三：
C++中struct和class的区别？
答：
（1）关于继承和访问权限，struct默认的继承访问权限为public，class为private；
（2）关于大括号初始化，C++中的struct是对C中的struct的扩充，同时兼容C中struct应有的大括号初始化特性。
class和struct如果定义了构造函数的话，都不能用大括号进行初始化；
如果没有定义构造函数，struct可以用大括号初始化；
如果没有定义构造函数，且所有成员变量全是public的话，可以用大括号初始化。

事实上，这个区别是由上面的区别造成的，所以这个可以不算一个区别。
（3）关于模版，在模版中，类型参数前面可以使用class或typename，不能使用struct。

问题四：
说说C++多态的实现机制。
答：
简单来说，就是通过虚函数表来实现的，具体请参考:CVTE面试问题汇总.

问题五：
C中static关键字的作用。
答：
（1）修饰变量，一是表名变量存储空间在全局静态存储区，二是变量生命周期是真个程序的生命周期，三是变量作用域限定在当前文件。

（2）修饰函数，限制函数的作用域为当前文件。

问题五：
C中extern关键字的作用。
答：
extern修饰变量和函数起到声明的作用，以表示变量或者函数的定义在别的文件中，提示编译器遇到此变量和函数时在其他文件中寻找其定义。

问题六：
C++中extern "C"的作用。
答：
C++中extern "C"修饰函数时，指明该函数以C的方式进行编译和链接。具体来说就是C++函数支持函数重载，C不支持函数重载，原因二者的函数签名不同。

如函数void foo(int,int)被C编译器编译后在符号库中的名字为_foo，而C++编译器则会产生像_foo_int_int之类的名字（不同的编译器可能生成的名字不同，但是都采用了相同的机制，生成的新名字称为”mangledname”）。

问题七：
说一下CC++程序的内存布局。
答：
目前我还没有找到很权威的著作对此问题有详细的论述，肯定有，只是我还不知道。看了《C++高级进阶教程》中描述如下。

如果内存地址由下到上的是从低地址到高地址，那么程序的内存布局大致如下：

问题七：
僵尸进程是如何产生的。
答：
在UNIX 系统中，一个进程结束了，但是他的父进程没有等待(调用wait / waitpid)他， 那么他将变成一个僵尸进程。

问题八：
僵尸进程如何避免。
答：
（1）父进程通过wait和waitpid等函数等待子进程结束，但这会导致父进程挂起。
（2）如果父进程很忙，那么可以用signal函数为SIGCHLD安装handler，因为子进程结束后， 父进程会收到该信号，可以在handler中调用wait回收。
（3）如果父进程不关心子进程什么时候结束，那么可以用signal（SIGCHLD,SIG_IGN）通知内核，自己对子进程的结束不感兴趣，那么子进程结束后，内核会回收， 并不再给父进程发送信号。
（4）还有一些技巧，就是fork两次，父进程fork一个子进程，然后继续工作，子进程fork一 个孙进程后退出，那么孙进程被init接管，孙进程结束后，init会回收。不过子进程的回收 还要自己做。

问题九：
写一个宏，给定数组名求数组长度，数组类型未知。
答：
想到sizeof就可以很容易求出来了。思路是先用sizeof(array)求出数组占用的内存空间大小（单位字节），再通过sizeof求出数组单个元素的类型大小（单位字节），前者除以后者即可。

#define func(array) sizeof(array)/sizeof(array[0])
1

问题十：
Linux下awk和sed了解过吧，给定一个文本文件，编写shell脚本将文件中重复的行删除。
答：
使用sort+uniq/awk/sed可以来完成。
方法一：利用sort以不重复的方式打印出文件所有的行并排序-u，表示unique。

sort -u file
1

方法二：利用sort先对文件按行排好序之后再交由uniq处理。sort -k 指定列，-t指定列分隔符。

sort -k 1 -t ':' file|uniq
1

方法三：利用sort+awk来完成。

sort file | awk '{if ($0!=line) print;line=$0}'
1

if ($0!=line) print;表示当前行是否等于上一行，不等于的话则打印，line开始是空的。line=$0表示当前行赋给line。

方法四：利用sort+sed来完成。

sort file | sed '$!N; /^\(.*\)\n\1$/!P;D'
1

稍后解释。

问题十一：
有用过Linux中的epoll吗？它的作用是什么？
答：
epoll是Linux内核为处理大批量文件描述符而作了改进的poll，是Linux下多路复用IO接口select/poll的增强版本，它能显著提高程序在大量并发连接中只有少量活跃的情况下的系统CPU利用率。

问题十二：
epoll和select的区别在哪，或者说优势在哪？
答：
（1）epoll除了提供select/poll那种IO事件的水平触发（Level Triggered）外，还提供了边缘触发（Edge Triggered）；
（2）select的句柄数目受限，在linux/posix_types.h头文件有这样的声明：#define __FD_SETSIZE 1024，表示select最多同时监听1024个fd。而epoll没有，epoll的最大并发的连接数的理论值无上限，但由于实际内存资源有限，实际并发的连接数受到资源的限制和最大的打开文件句柄数目的限制；
（3）epoll的最大好处是不会随着FD的数目增长而降低效率，在selec中采用轮询处理，其中的数据结构类似一个数组的数据结构，而epoll 是维护一个队列，直接看队列是不是空就可以了。
（4）使用mmap加速内核与用户空间的消息传递。无论是select,poll还是epoll都需要内核把FD消息通知给用户空间，如何避免不必要的内存拷贝就很重要，在这点上，epoll是通过内核于用户空间mmap同一块内存实现的。

此外，epoll创建时传入的参数是什么？
创建一个epoll的实例，size用来告诉内核这个监听的数目一共有多大。这个参数不同于select()中的第一个参数，给出最大监听的fd+1的值。需要注意的是，当创建好epoll句柄后，它就是会占用一个fd值，在linux下如果查看/proc/进程id/fd/，是能够看到这个fd的，所以在使用完epoll后，必须调用close()关闭，否则可能导致fd被耗尽。

问题十三：
给定数据表table1如下，编写SQL语句找出出现次数前三的年龄。

答：
在MS Access中测试跑通，参考语句如下：

select top 3 table2.Age,table2.num from (select Age,count(Age) as num from table1 group by Age) as table2 Order By table2.num DESC
1

问题十四：
网络的五层协议模型。
答：
很简单，如下图所示：