CVTE2017秋季校招一面回忆（C++后台岗）

2016.9.9日下午再一次参加了CVTE的C++后台开发岗的面试，面试经历了1个小时20分钟左右的时间，被问及了很多问题，很多问题也没有回答出来，自己还是存在很多知识盲点，需要潜心复习修炼，查漏补缺。手写代码也是没做好，下次一定要坚持写出来。总体来说，这场面试的难度对我来说不简单，现将回忆起的面试题与大家分享共勉。

1.找出数组中第k大的数（手写代码）

这是一道很经典的问题，《算法导论》中也有详细的介绍。回答时我与面试官说了一下自己的思路，有三种思路： （1）方法一 申请一个长度为k的中间数组，然后遍历数组，将前k大的数放入在中间数组即可，时间复杂度为O（kN），假定数组长度为N；这个解法是不合理的，因为可以不需要中间数组，且看下面的解决办法。

（2）方法二：简单选择排序 使用简单选择排序找出第k大的数，时间复杂度为O（kN），空间复杂度为0。

方法一读者自行实现，因第二种方法较为简单，面试时手写代码需要在几分钟的时间写出来，当然是越简单越好，下面就给出具体的实现。

//array:数组；len：数组长度；k:第k大
int getKthMax(int array[],int len,int k){
    int maxIndex=0;
    for(int i=0;i<n;++i){
        maxIndex=i;
        for(int j=i+1;j<len;++j)
            if(array[j]>array[maxIndex])
                maxIndex=j;
        if(maxIndex!=i){
            int tmp=array[maxIndex];
            array[maxIndex]=array[i];
            array[i]=tmp;
        }
    }
    return array[k-1];
}

下面说一下当时的具体场景。面对这道题，我和面试官说完思路后，他好像并不在意我的想法，而是补充了应用场景，场景是“数组很长，项目经理要求我实现这个功能，问我该怎么实现，需不需要给数组排序”。我的回答是并不需要排序，因为排序消耗的时间较长。面试官补充到说：“应该排序，因为会多次用到。”对于这个问题我应该主动询问面试官是否需要多次查询，因为如果只需要查询一次，得不偿失，如果需要经常查询第n大的数，则需要排序，做到一劳永逸。这样回答的话就应该较为全面了，在面试的过程中，如果对面试官提出的问题有疑问，应该主动与之沟通。

下面面试官说那写一下代码吧，看能不能写出来。于是我就思考决定用哪一方法，以及如何实现，当我还未思考达到1分钟时，自己也没有主动放弃，面试官就说：“写不出来，咱们下一题吧。”感觉他并不希望我能够写出来，也不想给我时间去写。我应该坚持，但在那种场景我不能坚持，只能跟着面试官的意思走，因为他是面试官。还有一个教训就是，在手写代码题我犯了大忌：talk is cheap，show me the code（少逼逼，亮代码）。说了太多，却没有代码。对于手写代码题，建议不要与面试官讨论自己的实现思路，而是按照自己的实现思路去写代码，再拿着自己的代码与面试官讨论自己的实现方式和不同的解法，如此做，自己的talk将不会那么低贱，显得更有分量，即使自己的方法不是最优解或者不是面试官想要的解，但至少你向面试官证明了自己的代码书写能力。

（3）第三种方法：冒泡排序 既然能用简单选择排序的方法找出第n大的数，当然可以使用冒泡排序的方法。第一趟冒泡第一大，第二次冒泡第二大，第n次冒泡第大，时间复杂度为O(nM)，M为数组长度。因为比较简单，这里也不具体实现了，具体可以参考冒泡排序的实现。

（4）正确的解法：使用快速排序寻找数组中第k大的数 面试官提示我用快速排序思想去解决这个问题，但是自己还是没能够在面试官的提示下说出面试官心中想要的答案。

我们都知道快速排序是对冒泡的改进，使排序时间复杂度降低到O(nlgn)，为什么不用快排来解决这个问题呢？那么快排的时间复杂度又是多少呢？

这里以递减排序为例，因为快排每次将数组划分为两组和一个分区元素，每一趟划分你只需要将k与分元素的下标进行比较，如果比分区元素下标+1大就从右边的子数组中找，如果比分区元素下标+1小从左边的子数组中找，如果一样则就是分区元素。如果需要从左边或者右边的子数组中再查找的话，只需要递归一遍查找即可，无需像快排一样两边都需要递归，所以复杂度必然降低。

平均时间复杂度如下：假设快排每次都平均划分，但都不在分区元素上找到第k大，直至最后一趟找到。

第一趟快排没找到，时间复杂度为O(n)，第二趟也没找到，时间复杂度为O(n/2)，…，最后一趟log2nlog_2n趟找到，时间复杂度为O(n/2log2n)=O(1)O(n/2^{log_2n})=O(1)，所以总的时间复杂度为O(n(1+1/2+1/4+....+1/n))=O(2(n−1))=O(n)O(n(1+1/2+1/4+....+1/n))=O(2(n-1))=O(n)，很明显比上面提出的方法快，相比于快速排序，虽然递归深度是一样的，但每一趟时间复杂度降低了一半，整体是收敛的。

示例代码：

/****************************************************
*@brief:利用快速排序以递减排序的方式找出无序数组中第k大的数
*@param：array：无序数组；low：左起始下标；high：右结束下标
*@ret：成功返回第k大的数，失败返回-1
****************************************************/
int getNthMaxByQuickSort(int array[],int low,int high,int k){
    if(low>high)
        return -1;

    int left=low;
    int right=high;
    int key=array[left];    /*用数组的第一个记录作为分区元素*/
    while(left<right){
        while(right>left&&array[right]<=key)
            --right;
        array[left]=array[right];
        while(left<right&&array[left]>=key)
            ++left;
        array[right]=array[left];
    }
    array[left]=key;
    if(left+1==k)
        return array[left];
    if(left+1>k)    //在左边寻找
        getNthMaxByQuickSort(array,low,left-1,k);
    else            //在右边寻找
        getNthMaxByQuickSort(array,left+1,high,k);
}

//测试
int main(){
    int array[]={1,1,5,9,2,3,6,8,7,4,0};
    cout<<getNthMaxByQuickSort(array,0,10,1)<<endl;    //9
    cout<<getNthMaxByQuickSort(array,0,10,2)<<endl;    //8
    cout<<getNthMaxByQuickSort(array,0,10,11)<<endl;   //0
}

2.从n个数中找出最小的k个数（n>>k）,最优平均时间复杂度是多少

根据上面的分析，可见最优平均时间复杂度是O(n)。

3.假设你有100MB的内存，需要对1GB的数据进行排序，最合适的算法是什么

给定四个选项，时间复杂度如下：

所以应该选择归并排序。本题的考点主要有两个。一个是外部排序，一个是排序算法的特点和时间复杂度。

外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。

外部排序一般用归并排序，空间复杂度是O（n）。一般来说外部排序分为两个步骤：预处理和归并。首先，根据可用内存的大小，将外存上含有n个纪录的文件分成若干长度为t的子文件（或段）；其次，利用内部排序的方法，对每个子文件的t个纪录进行内部排序。这些经过排序的子文件（段）通常称为顺串，顺串生成后将其写入外存。这样在外存上就得到了m个顺串（m=⌈n/t⌉m=\lceil n/t\rceil）。最后，对这些顺串进行归并，使顺串的长度逐渐增大，直到所有的待排序的记录成为一个顺串为止。

注意，归并时，需要使用额外文件来存储最终的顺串。归并过程如下，遍历每一个子文件指针当前所指元素，取出最大或最小的元素，写入最终文件中。循环上面的步骤，直至所有子文件元素均被有序地写入最终文件。

4.C如何模拟实现C++的类

C++定义类最大的特点是使程序面向对象而不是面向过程，这在C中是没有体现的。 类的标志性特征是封装，继承，多态，对象化提供了模型化和信息隐藏的好处，类化提供了可重用性的好处。使用C模拟实现C++的类，必须也要拥有上面三个基本特征。

（1）封装 C中可以使用struct来模拟C++的类，将成员变量作为struct的成员变量， 成员函数由struct的函数指针变量来表示。 （2）继承 继承的替代实现方案可以使用组合的方式。将父struct的对象作为子struct的数据成员并放置在第一个位置。 （3）多态 同名的函数指针变量赋予不同的实现函数的地址，实现多态。或者模拟真实的C++多态实现的机制，可以将所有virtual函数的入口地址使用函数指针存放在一个结构体中，然后在C的结构体类中的增加一个成员变量指向该函数指针结构体对象。

C如何模拟实现C++的类，可以参考简单的实例：C实现C++类

你可能会发现一个问题，因为C中struct的成员访问权限只能是public，上面的模拟实现，没有模拟出类成员的private和protected访问权限，该如何实现呢？

网上查找了很多资料，还是没有找到如何实现，于是在CSDN论坛上发帖咨询，有两位热心的网友提供了如下设计方案，感觉可行。

公有变量作为struct中的字段，公有方法可以在struct中设置一个函数指针。私有变量和私有方法移到提供类的实现的源码文件中，并且用static修饰，这样就无法在源文件之外被访问。

//头文件CCLssA.h
struct classA {
  int public_a, public_b, public_c;  
  func_t public_f1, public_f2, public_f3;
};

//源文件CCLssA.c
typedef void (*func_t)(void);
static int private_a, private_b, private_c;
static void private_f1(void) {}
static void private_f2(void) {}
static void private_f3(void) {}

//主文件main.c
struct classA obj;
obj.public_a;
obj.public_b;
obj.f1();

如此做结构体对象本质上还是不存在private成员，只是逻辑上将static全局变量作为自己的私有成员变量。要真正实现面向对象机制中的封装，继承和多态是需要编译器支持的，不可能简单凭C语言的特性来实现。具体可参考原贴C如何实现C++类的私有和公共？

5.TCP与UDP的区别

TCP（Transmission Control Protocol，传输控制协议）。

当应用层向TCP层发送用于网间传输的、用8位字节表示的字节流，TCP则把数据流分割成适当长度的报文段，最大传输段大小（MSS）通常受该计算机连接的网络的数据链路层的最大传送单元（MTU）限制。之后TCP把数据包传给IP层，由它来通过网络将包传送给接收端实体的TCP层。

TCP通过连接管理、序列号、检验和、确认应答、重发控制以及窗口控制等机制实现可靠性传输。 （1）连接管理。是面向连接的协议，也就是说，在收发数据前，必须和对方建立可靠的连接。一个TCP连接必须要经过三次“对话”才能建立连接。 （2）序列号与重发控制。TCP为了保证报文传输的可靠，就给每个包一个序号，同时序号也保证了传送到接收端实体的包的按序接收。然后接收端实体对已成功收到的字节发回一个相应的确认(ACK)；如果发送端实体在合理的往返时延(RTT)内未收到确认，那么对应的数据（假设丢失了）将会被重传。 （3）在数据正确性与合法性上，TCP用一个校验和函数来检验数据是否有错误，在发送和接收时都要计算校验和。 （4）在流量控制上，采用滑动窗口协议，协议中规定，对于窗口内未经确认的分组需要重传。 （5）在拥塞控制上，采用广受好评的TCP拥塞控制算法（也称AIMD算法）。该算法主要包括三个主要部分：1）加性增、乘性减；2）慢启动；3）对超时事件做出反应。

UDP（User Datagram Protocol，用户数据报协议） （1） UDP是一个非连接的协议，传输数据之前源端和终端不建立连接，当它想传送时就简单地去抓取来自应用程序的数据，并尽可能快地把它扔到网络上。在发送端，UDP传送数据的速度仅仅是受应用程序生成数据的速度、计算机的能力和传输带宽的限制；在接收端，UDP把每个消息段放在队列中，应用程序每次从队列中读一个消息段。 （2） 由于传输数据不建立连接，因此也就不需要维护连接状态，包括收发状态等，因此一台服务机可同时向多个客户机传输相同的消息。 （3） UDP信息包的标题很短，只有8个字节，相对于TCP的20个字节信息包的额外开销很小。 （4） 吞吐量不受拥挤控制算法的调节，只受应用软件生成数据的速率、传输带宽、源端和终端主机性能的限制。 （5）UDP是面向报文的。发送方的UDP对应用程序交下来的报文，在添加首部后就向下交付给IP层。既不拆分，也不合并，而是保留这些报文的边界，因此，应用程序需要选择合适的报文大小。

我们经常使用“ping”命令来测试两台主机之间TCP/IP通信是否正常，其实“ping”命令的原理就是向对方主机发送UDP数据包，然后对方主机确认收到数据包，如果数据包是否到达的消息及时反馈回来，那么网络就是通的。

小结TCP与UDP的区别： （1）TCP基于连接，UDP无连接； （2）TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达。UDP尽最大努力交付，即不保证可靠交付； （3）每一条TCP连接只能是点到点的，UDP支持一对一，一对多，多对一和多对多的交互通信； （4）TCP首部开销20字节，UDP的首部开销小，只有8个字节； （5）TCP面向字节流模式，因此可能出现黏包问题；UDP面向数据报模式，数据报保留边界，不会出现黏包问题； （6）UDP没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如IP电话，实时视频会议等）；

基于TCP的应用层协议： FTP:21, Telnet:23, SMTP:25，POP3：110，HTTP：80，Https：443。

基于UDP的应用层协议： DNS:53, TFTP:69, SNMP:161, RIP:520。

6.http是基于TCP还是UDP实现的

很显然是TCP，结果没答出来，应该二选一猜一个的。

7.使用UDP传输数据时如何知道数据成功发送到接收方

接收方返回确认包。

8.如何解决TCP黏包问题

什么是TCP黏包问题？ 首先了解两个概念： 两个简单概念长连接与短连接： （1）长连接 Client方与Server方先建立通讯连接，连接建立后不断开， 然后再进行报文发送和接收。

（2）短连接 Client方与Server每进行一次报文收发交易时才进行通讯连接，交易完毕后立即断开连接。此种方式常用于一点对多点的通讯，比如多个Client连接一个Server。

如果利用TCP每次发送数据，就与对方建立连接，然后双方发送完一段数据后，就关闭连接，在这种短连接的情况下就不会出现粘包问题，因为只有一种包结构，比如http协议包。但是在长连接的情况下，如果如果双方建立连接，需要在连接后一段时间内发送不同结构数据，如连接后，有好几种结构： （1）”hello give me sth abour yourself” （2）”Don’t give me sth abour yourself” 那这样的话，如果发送方连续发送这个两个包出去，接收方一次接收可能会是”hello give me sth abour yourselfDon’t give me sth abour yourself” 这样接收方就傻了，不知道接收的数据是什么，因为协议没有规定这么诡异的字符串，所以要处理把它分包，怎么分也需要双方组织一个比较好的包结构，所以一般可能会在头加一个数据长度之类的包，以确保成功接收，正确理解。

所以，TCP黏包问题指的是发送端以字节流的形式发送不同结构的数据包无明显边界导致接收方无法正确解析数据包。

TCP黏包出现的原因？ TCP以字节流传输数据，字节流之间无明显边界，UDP以数据包传输数据，数据报保留消息边界，不会出现粘包。这是根本原因，直接原因是： （1）发送端需要等缓冲区满才发送出去，发送方造成粘包； （2）接收方不及时接收缓冲区的包，多个包接收，接收方造成黏包。

解决办法。 为了避免粘包现象，可采取以下几种措施。一是对于发送方引起的粘包现象，用户可通过编程设置来避免，TCP提供了强制数据立即传送的操作指令push，TCP软件收到该操作指令后，就立即将本段数据发送出去，而不必等待发送缓冲区满；二是对于接收方引起的粘包，则可通过优化程序设计、精简接收进程工作量、提高接收进程优先级等措施，使其及时接收数据，从而尽量避免出现粘包现象；三是由接收方控制，将一包数据按结构字段，人为控制分多次接收，然后合并，通过这种手段来避免粘包。

以上提到的三种措施，都有其不足之处。第一种编程设置方法虽然可以避免发送方引起的粘包，但它关闭了优化算法，降低了网络发送效率，影响应用程序的性能，一般不建议使用。第二种方法只能减少出现粘包的可能性，但并不能完全避免粘包，当发送频率较高时，或由于网络突发可能使某个时间段数据包到达接收方较快，接收方还是有可能来不及接收，从而导致粘包。第三种方法虽然避免了粘包，但应用程序的效率较低，对实时应用的场合不适合。

唯一解决办法：制定应用层协议。 处理粘包的唯一方法就是制定应用层的数据通讯协议，通过协议来规范现有接收的数据是否满足消息数据的需要。在应用中处理粘包的基础方法主要有两种，分别是以4节字描述消息大小或以结束符，实际上也有两者相结合的如HTTP，Redis的通讯协议等。于是这里就涉及到封包和拆包的操作。

封包就是给一段数据加上包头，这样一来数据包就分为包头和包体两部分内容了(过滤非法包时封包会加入”包尾”内容)。包头其实上是个大小固定的结构体,其中有个结构体成员变量表示包体的长度,这是个很重要的变量,其他的结构体成员可根据需要自己定义.根据包头长度固定以及包头中含有包体长度的变量就能正确的拆分出一个完整的数据包。

拆包就是根据包头信息正确解析数据包。

9.单播、多播和广播的区别

单播（Unicast）、多播（Multicast）和广播（Broadcast）这三个术语都是用来描述网络节点之间通讯方式。

（1）单播 主机之间一对一的通讯模式，网络中的交换机和路由器对数据只进行转发不进行复制。如果10个客户机需要相同的数据，则服务器需要逐一传送，重复10次相同的工作。但由于其能够针对每个客户的及时响应，所以现在的网页浏览全部都是采用单播模式，具体的说就是IP单播协议。网络中的路由器和交换机根据其目标地址选择传输路径，将IP单播数据传送到其指定的目的地。

单播的优点： 1）服务器及时响应客户机的请求 2）服务器针对每个客户不通的请求发送不通的数据，容易实现个性化服务。

单播的缺点： 1）服务器针对每个客户机发送数据流，服务器流量＝客户机数量×客户机流量；在客户数量大、每个客户机流量大的流媒体应用中服务器不堪重负。 2）现有的网络带宽是金字塔结构，城际省际主干带宽仅仅相当于其所有用户带宽之和的5％。如果全部使用单播协议，将造成网络主干不堪重负。现在的P2P应用就已经使主干经常阻塞。而将主干扩展20倍几乎是不可能。

（2）多播（组播） 主机之间一对一组的通讯模式，也就是加入了同一个组的主机可以接受到此组内的所有数据，网络中的交换机和路由器只向有需求者复制并转发其所需数据。主机可以向路由器请求加入或退出某个组，网络中的路由器和交换机有选择的复制并传输数据，即只将组内数据传输给那些加入组的主机。这样既能一次将数据传输给多个有需要（加入组）的主机，又能保证不影响其他不需要（未加入组）的主机的其他通讯。

组播的优点： 1）需要相同数据流的客户端加入相同的组共享一条数据流，节省了服务器的负载。具备广播所具备的优点。 2）由于组播协议是根据接受者的需要对数据流进行复制转发，所以服务端的服务总带宽不受客户接入端带宽的限制。IP协议允许有2亿6千多万个组播，所以其提供的服务可以非常丰富。 3）此协议和单播协议一样允许在Internet宽带网上传输。

组播的缺点： 1）与单播协议相比没有纠错机制，发生丢包错包后难以弥补，但可以通过一定的容错机制和QOS加以弥补。 2）现行网络虽然都支持组播的传输，但在客户认证、QOS等方面还需要完善，这些缺点在理论上都有成熟的解决方案，只是需要逐步推广应用到现存网络当中。

（3）广播 主机之间一对所有的通讯模式，网络对其中每一台主机发出的信号都进行无条件复制并转发，所有主机都可以接收到所有信息（不管你是否需要），由于其不用路径选择，所以其网络成本可以很低廉。有线电视网就是典型的广播型网络，我们的电视机实际上是接受到所有频道的信号，但只将一个频道的信号还原成画面。在数据网络中也允许广播的存在，但其被限制在二层交换机的局域网范围内，禁止广播数据穿过路由器，防止广播数据影响大面积的主机。

广播的优点： 1）网络设备简单，维护简单，布网成本低廉 2）由于服务器不用向每个客户机单独发送数据，所以服务器流量负载极低。

广播的缺点： 1）无法针对每个客户的要求和时间及时提供个性化服务。 2）网络允许服务器提供数据的带宽有限，客户端的最大带宽＝服务总带宽。例如有线电视的客户端的线路支持100个频道（如果采用数字压缩技术，理论上可以提供500个频道），即使服务商有更大的财力配置更多的发送设备、改成光纤主干，也无法超过此极限。也就是说无法向众多客户提供更多样化、更加个性化的服务。 3）广播禁止允许在Internet宽带网上传输。

10.如何判断主机字节序

主机字节序又叫做CPU字节序，不是由操作系统决定的，而是由cpu指令集架构决定的。主机字节序分为两种，大端字节序（Big Endian）和小端字节序（Little Endian）。

考虑一个16位整数，它由2个字节组成。内存中存储这两个字节有两种方法：一种是将低序字节存储在低地址中，高字节存储在高地址中，这称为小端字节序。另一种是将高序字节存储在低地址中，低序字节存储在高地址中，这称为大端字节序。

判断方法： 假设我们的32位整数0x12345678是从起始位置为0x00的地址开始存放，则：

0x00  0x01    0x02    0x03    
78    56      34      12  （小端）  
12    34      56      78  （大端） 

因此，我们可以这样判断：

int main(){  
    int i = 0x12345678;  
    if(*((char*)&i) == 0x12)  
        printf("大端");  
    else  
        printf("小端");
    return 0;
}

11.网络字节序是大端还是小端

网络字节顺序是TCP/IP中规定好的一种数据表示格式，它与具体的CPU类型、操作系统等无关，从而可以保证数据在不同主机之间传输时能够被正确解释。网络字节顺序采用Big Endian排序方式。

12.arm架构的字节序是什么

ARM公司的ARM架构处理器大端和小端都支持，默认是小端模式。 Intel、AMD的CPU是X86系列架构的，采用小端模式。 IBM公司的CPU是PowerPC架构，采用Big Endian，Motorola处理器也是采用Big Endian。

13.Linux内核的同步方式

首先问了我线程的同步方式有哪些，我回答的是Linux下线程的同步方式。linux下提供了多种方式来处理线程同步，最常用的是互斥量、条件变量和信号量，还有不常用的读写锁，自旋锁和屏障。

然后面试官又问我Linux内核的同步方式，没有研究过内核，懵逼。首先解释一下几个与同步有关的术语。

临界区（Critical Region）： 指的是访问临界资源的程序片段，而这个程序片段不能并发执行，必须被原子地的执行。

竞争状态： 多个任务（进程或线程）同时访问同一临界区。

同步（synchronization）： 避免竞争状态，使多个任务有序互斥的访问临界区。

查询网络资源，了解到Linux内核大概有如下几种同步方式：中断屏蔽、原子操作、自旋锁和信号量。

（1）中断屏蔽。 在单CPU范围内避免竞态的一种简单方法是在进入临界区之前屏蔽系统的中断。由于linux内核的进程调度等操作都依赖中断来实现，发生内核抢占时进程之间的并发也就得以避免了。内核抢占（kernel preemption）指的是若内核具有抢占性，一个在内核态运行的进程，当且仅当在执行内核函数期间被另外一个进程取代。Linux 2.6引入了内核抢占机制。

中断屏蔽的使用方法：

local_irq_disable()//屏蔽中断
//临界区
local_irq_enable()//开中断

特点： 由于linux系统的异步IO，进程调度等很多重要操作都依赖于中断，在屏蔽中断期间所有的中断都无法得到处理，因此长时间的屏蔽是很危险的，有可能造成数据丢失甚至系统崩溃，这就要求在屏蔽中断之后，当前的内核执行路径应当尽快地执行完临界区的代码。

中断屏蔽只能禁止本CPU内的中断，因此，并不能解决多CPU引发的竞态，所以单独使用中断屏蔽并不是一个值得推荐的避免竞态的方法，它一般和自旋锁配合使用。

（2）原子操作。 原子操作指的是在执行过程中不会被中断的操作。原子原本指的是不可分割的微粒，所以原子操作也就是不能够被分割的指令。

原子操作是不可分割的，在执行完毕不会被任何其它任务或事件中断。在单处理器系统(UniProcessor)中，能够在单条指令中完成的操作都可以认为是” 原子操作”，因为中断只能发生于指令之间。这也是某些CPU指令系统中引入了test_and_set、test_and_clear等指令用于临界资源互斥的原因。但是，在对称多处理器(Symmetric Multi-Processor)结构中就不同了，由于系统中有多个处理器在独立地运行，即使能在单条指令中完成的操作也有可能受到干扰。

下面看一个本应该是原子操作，结果出现了错误。 我们的程序逻辑经常遇到这样的操作序列： 1、读一个位于memory中的变量的值到寄存器中 2、修改该变量的值（也就是修改寄存器中的值） 3、将寄存器中的数值写回memory中的变量值

如果这个操作序列是串行化的操作（在一个thread中串行执行），那么一切OK，然而，世界总是不能如你所愿。在多CPU体系结构中，运行在两个CPU上的两个内核控制路径同时并行执行上面操作序列，有可能发生下面的场景：

多个CPUs和Memory Chip是通过总线互联的，在任意时刻，只能有一个总线master设备（例如CPU、DMA Controller）访问该Slave设备（在这个场景中，slave设备是RAM chip）。因此，来自两个CPU上的读memory操作被串行化执行，分别获得了同样的旧值。完成修改后，两个CPU都想进行写操作，把修改的值写回到memory。但是，硬件arbiter的限制使得CPU的写回必须是串行化的，因此CPU1首先获得了访问权，进行写回动作，随后，CPU2完成写回动作。在这种情况下，CPU1的对memory的修改被CPU2的操作覆盖了，因此执行结果是错误的。

不仅是多CPU，在单CPU上也会由于有多个内核控制路径的交错而导致上面描述的错误。一个具体的例子如下：

系统调用的控制路径上，完成读操作后，硬件触发中断，开始执行中断handler。这种场景下，中断handler控制路径的写回的操作被系统调用控制路径上的写回覆盖了，结果也是错误的。

如何解决上面的问题呢？在Linux内核提出了原子操作，原子操作又分为原子整数操作和原子位操作，下面我们来看看这两个操作用法。

原子整数操作。 内核提供了一个特殊的类型atomic_t，具体定义如下：

typedef struct { 
    int counter; 
}atomic_t;

相应的对该类型变量的操作提供了一系列API，因在一系列API使用利用了指令集的特性和锁来保证对atomic_t类型变量的操作是原子操作。

原子位操作。 除了原子整数操作外，内核还提供了一组针对位这一级数据进行操作的函数，位操作函数是对普通的内在地址进行操作的，它的参数是一个指针和一个位号。由于是对普通的指针进程操作，所以没有像atomic_t这样的类型约束。

unsigned long word = 0;
set_bit(0,&word);
clear_bit(0,&word);
change_bit(0,&word);//翻转第0位的值

原子整数操作和原子位操作的相应的API介绍可以参考Linux内核的原子操作。

（3）自旋锁（spin lock）。 Linux内核中最常见的锁是自旋锁，自旋锁最多只能被一个可执行线程持有，如果一个执行线程试图获得一个被争用（已经被持有）的自旋锁，那么该线程就会一直进行忙循环—旋转—等待锁重新可用，要是锁未被争用，请求锁的执行线程便能立刻得到它，继续执行，在任意时间，自旋锁都可以防止多于一个的执行线程同时进入理解区，注意同一个锁可以用在多个位置—例如，对于给定数据的所有访问都可以得到保护和同步。

自旋锁在Linux内核同步和线程同步的区别。 这里自旋锁与Linux用户态线程同步使用的自旋锁实现原理是相同的，但在使用上有一点区别。Linux线程同步使用的自旋锁供应用程序使用，在用户态使用且使用次数比较少，接口也不相同。内核同步使用的自旋锁在内核使用的比较多，且只能工作在内核态。

（4）信号量（semaphore）。 Linux内核的信号量在概念和原理上与用户态的System V的IPC机制信号量是一样的，但是它绝不可能在内核之外使用，它是一种睡眠锁。如果有一个任务想要获得已经被占用的信号量时，信号量会将其放入一个等待队列，然后让其睡眠。当持有信号量的进程将信号释放后，处于等待队列中的一个任务将被唤醒（因为队列中可能不止一个任务），并让其获得信号量。

信号量与自旋锁的区别： （1）自旋锁让一个任务（进程或线程）旋转，使CPU处于忙等状态，此时不能去执行其它的代码，但信号量使任务睡眠，此时CPU处于闲等状态，可以去执行其它的代码。 （2）由于争用信号量的进程在等待锁重新变为可用时会睡眠，所以信号量适用于锁会被长时间持有的情况；相反，自旋锁一般短时间被持有，如果使用信号量就不太适宜了，因为睡眠、维护等待队列以及唤醒所花费的开销可能比锁占用的全部时间表还要长； （3）信号量允许有多个持有者，而自旋锁在任何时候只能允许一个持有者。

14.fork和pthread在创建子进程和线程时最终会调用哪个系统API

fork，vfork，clone，都是系统调用，三者不存在谁调用谁的关系。但三者最终都会调用do_fork。 pthread_create是对clone的封装，最终会调用clone。

clone系统调用就是一个创建轻量级进程的系统调用：

int clone(int (*fn)(void * arg), void *stack, int flags, void * arg);

所以fork和pthread在创建子进程和线程时最终会调用do_fork。但面试官给我的回答是clone。可能问题问的有点问题，或者问题里面没有问fork最终调用的哪一个API。

15.C++构造函数为什么不能有返回值

C++构造函数在C++设计时规定构造函数和析构函数均不能有返回值，连void也不行，函数体内也不能使用return。那为什么要这样设计呢？

构造函数不需要用户调用，在创建一个对象时会自动执行构造函数。当然也可以直接调用构造函数。构造函数返回的就是这个类的对象this指针，这是不能改变的，默认的。所以构造函数不能指定返回值。参考如下代码：

    int i;
public:
    Test(int i);

};

Test::Test(int a){
    i=a;
}

在VS2012对应的汇编代码是：

class Test{
    int i;
public:
    Test(int i);

};

Test::Test(int a){
003DA9C1  mov         ebp,esp  
003DA9C3  sub         esp,0CCh  
003DA9C9  push        ebx  
003DA9CA  push        esi  
003DA9CB  push        edi  
003DA9CC  push        ecx  
003DA9CD  lea         edi,[ebp-0CCh]  
003DA9D3  mov         ecx,33h  
003DA9D8  mov         eax,0CCCCCCCCh  
003DA9DD  rep stos    dword ptr es:[edi]  
003DA9DF  pop         ecx  
003DA9E0  mov         dword ptr [this],ecx  
    i=a;
003DA9E3  mov         eax,dword ptr [this]  
003DA9E6  mov         ecx,dword ptr [a]  
003DA9E9  mov         dword ptr [eax],ecx  
}
003DA9EB  mov         eax,dword ptr [this]   //看这里，将this赋给eax作为构造函数的返回值
003DA9EE  pop         edi  
003DA9EF  pop         esi  
003DA9F0  pop         ebx  
003DA9F1  mov         esp,ebp  
003DA9F3  pop         ebp  
003DA9F4  ret         4  

下面直接调用构造函数，来验证构造函数返回的是类对象的this指针。直接调用构造函数的方法是调用placement new()，关于什么事placement new和operator new可以参考我的另一篇博文：C++中的定位放置new(placement new)。

#include <stdint.h>

#include <iostream>
using namespace std;

class Test{
public:
    int i;
    Test(int a){
        i=a;
    }
};

int main(){
    void* mem=new uint8_t[sizeof(Test)];
    Test* pT=NULL;
    pT=new (mem) Test(8);   //直接调用构造函数，返回对象this指针
    cout<<mem<<endl;        //输出：005092D0
    cout<<pT<<endl;         //输出：005092D0
    cout<<pT->i<<endl;      //输出：8

析构函数为什么也不能有返回值呢？ 析构函数不带任何参数，也不能有返回值，为什么要这样设计析构函数呢？

析构函数不带任何参数是因为析构函数仅仅只是负责对类指针成员指向的空间进行释放，不需要有任何参数。

析构函数同构造函数一样，不需要用户调用，而是在销毁对象时自动执行。但我们也可以直接调用析构函数，但这样做容易导致对内存空间释放两次，使程序出错。鉴于析构函数总是由编译器来生成调用析构函数的代码，以确保它们被执行，如果析构函数有返回值，要么编译器必须知道如何处理返回值，要么就只能由客户程序员自己来显式的调用构造函数与析构函数，这样一来，安全性就被破坏了。所以析构函数同构造函数一样，不能为之指定返回值。

16.C++构造函数无返回值，如何判断对象是否“构造”成功

两个办法。 （1）在C++构造函数中抛出异常，但要注意资源泄漏问题，因为C++拒绝为没有完成构造函数的对象调用析构函数； （2）向C++构造函数多传递一个标志参数，通过该参数来判断对象是否构造成功。

17.不用循环打印1到N

方法一：递归

void print1ton(int n){   
    if(n>1) {  
        print2n(n-1);  
    }
    printf("%d\n", n);  
}

该方法简洁明了，适合在面试的适合手写出来。

方法二：类对象的引用计数

#include <iostream>  
using namespace std;  

class A {
static int counter;  
public:   
    A() {     
        cout <<counter++ <<endl;  
    }
};  

int A::counter = 1;  

int main(){  
    #define N 100
    A array[N];
    return 0;  
}  

18.C++中list容器实现的是单链表还是双链表

双向链表容器。

19.QT中信号与槽的简介

因为简历中写到了关于QT的项目，所以被问到了这个问题。

QT是一个跨平台的C++ GUI应用构架，它提供了丰富的窗口部件集，具有面向对象、易于扩展、真正的组件编程等特点。

信号与槽是QT自行定义的一种对象通信机制，也是QT的核心机制，它独立于标准的C/C++语言。

信号： 当对象改变其状态时，信号就由该对象发射 (emit) 出去，而且对象只负责发送信号，它不知道另一端是谁在接收这个信号。这样就做到了真正的信息封装，能确保对象被当作一个真正的软件组件来使用。

当一个信号被发射时，与其相关联的槽将被立刻执行，就象一个正常的函数调用一样。信号-槽机制完全独立于任何GUI事件循环。只有当所有的槽返回以后发射函数（emit）才返回。 如果存在多个槽与某个信号相关联，那么，当这个信号被发射时，这些槽将会一个接一个地 执行，但是它们执行的顺序将会是随机的、不确定的，我们不能人为地指定哪个先执行、哪 个后执行。

信号的声明是在头文件中进行的，QT的signals关键字指出进入了信号声明区，随后即可 声明自己的信号。例如，下面定义了三个信号：

signals: 
    void mySignal();
    void mySignal(int x);
    void mySignalParam(int x,int y);

在上面的定义中，signals是QT的关键字，而非C/C++的。接下来的一行void mySignal() 定义了信号mySignal，这个信号没有携带参数；接下来的一行void mySignal(int x)定义 了重名信号mySignal，但是它携带一个整形参数，这有点类似于C++中的虚函数。从形式上 讲信号的声明与普通的C++函数是一样的，但是信号却没有函数体定义，另外，信号的返回 类型都是void，不要指望能从信号返回什么有用信息。

信号由moc自动产生，它们不应该在.cpp文件中实现。moc（Meta Object Compiler）是QT的工具，该工具是一个C++预处理程序，它为高层次的事件处理自动生成所需要的附加代码。

槽： 槽是普通的C++成员函数，可以被正常调用，它们唯一的特殊性就是很多信号可以与其相关联。当与其关联的信号被发射时，这个槽就会被调用。

既然槽是普通的成员函数，因此与其它的函数一样，它们也有存取权限。槽的存取权限决定了谁能够与其相关联。同普通的C++成员函数一样，槽函数也分为三种类型，即public slots、private slots和protected slots。

public slots：在这个区内声明的槽意味着任何对象都可将信号与之相连接。这对于组件编程非常有用，你可以创建彼此互不了解的对象，将它们的信号与槽进行连接以便信息能够正确的传递。 protected slots：在这个区内声明的槽意味着当前类及其子类可以将信号与之相连接。这适用于那些槽，它们是类实现的一部分，但是其界面接口却面向外部。 private slots：在这个区内声明的槽意味着只有类自己可以将信号与之相连接。这适用于联系非常紧密的类。 槽也能够声明为虚函数，这也是非常有用的。 槽的声明也是在头文件中进行的。例如，下面声明了三个槽：

public slots:
    void mySlot();
    void mySlot(int x);
    void mySignalParam(int x,int y);

信号与槽的关联: 只有将信号与槽关联在一起，当某个对象发送信号时，信号对应的槽才会被触发执行。通过调用QObject对象的connect函数来将某个对象的信号与另外一个对象的槽函数相关联，这样当发射者发射信号时，接收者的槽函数将被调用。该函数的申明如下：

bool QObject::connect ( const QObject * sender, const char * signal, 
        const QObject * receiver, const char * member ) [static]

这个函数的作用就是将发射者sender对象中的信号signal与接收者receiver中的member槽函数联系起来。当指定信号signal时必须使用QT的宏SIGNAL()，当指定槽函数时必须使用宏SLOT()。如果发射者与接收者属于同一个对象的话，那么在connect调用中接收者参数可以省略。 例如，下面定义了两个对象：标签对象label和滚动条对象scroll，并将valueChanged()信号与标签对象的setNum()相关联，另外信号还携带了一个整形参数，这样标签总是显示滚动条所处位置的值。

QLabel *label  = new QLabel;
QScrollBar *scroll = new QScrollBar;
QObject::connect( scroll, SIGNAL(valueChanged(int)), label,  SLOT(setNum(int)) );

信号与槽之间的关系 [12]^{[12]}： （1）一个信号可以连接多个槽 当信号发射时，会以不确定的顺序一个接一个的调用各个槽。

（2）多个信号可以连接同一个槽 即无论是哪一个信号被发射，都会调用这个槽。

（3）信号直接可以相互连接 发射第一个信号时，也会发射第二个信号。

（4）连接可以被移除 这种情况用得比较少，因为在对象被删除时，Qt会自动移除与这个对象相关的所有连接。语法如下：

disconnect(sender, SIGNAL(signal), receiver, SLOT(slot));

（5）信号的参数与槽的参数的关系 信号的参数个数必须大于等于槽的参数个数，并且与槽的参数类型要一一对应，超过槽的参数后面的参数会被忽略。需要注意的是，槽的参数不能有缺省值。

小结

整个面试过程被面试官牵着鼻子走，回答的也有点吃力，问题涉及到的知识点纷杂多样，涉及到编程语言，Linux操作系统，计算机网络，算法与数据结构，计算机组成原理等知识。很遗憾，还是折戟沉沙，铩羽而归。尽管如此，还是要感谢CVTE给我这次面试的机会，让我认识到了自己的不足。分析了一下失败的原因，主要有两方面，一是，从上一次参加了CVTE2016春季实习校招的面试，再到这一次校招面试，两次求职面试，CVTE的校招宣讲，笔试和面试都比其他很多公司要早，给我个人的感觉就是太重宣传，招人甚少，难逃未有招人诚心之嫌，僧多粥少，这也就导致了竞争压力较大。二是，这也是最根本的原因就是个人能力不足，面试没有做到充足的准备。面试是个技巧活，即使工作经验有多么丰富，也不能等同于自己的面试求职能力有多强。面试的问题涉及到的知识点，工作中往往只能用到其中的一部分，长时间不温习，很容易会忘记。所以面试一定要好好准备。

个人的面试的心得吧，面试过程中，求职者应做到：礼貌，谦逊，少说。说的越多，错的就可能越多，很多问题答到点上就行了，要做到应适可而止。

从9号面试，到今天14号，历时5天，终于坚持整理出了面试过程遇到的问题。明天就是猴年中秋了，祝愿在IT道路上渐行渐远的网友们节日快乐。仅以此篇博客纪念我第二次CVTE被虐之旅，对CVTE已累觉不爱。

参考文献

[1]求一个数组中第k大的数方法 [2]TCP与UDP的区别 [3]TCP.百度百科 [4]（经典）tcp粘包分析 [5]TCP通讯处理粘包详解 [6]单播、多播（组播）和广播的区别 [7]如何判断字节序 [8]内核抢占 [9]Linux内核的同步机制之四－－信号量 [10] fork, vfork, clone,pthread_create,kernel_thread [11]c++构造函数有返回值吗？

[12]Qt入门之信号与槽机制 [13]QT的信号与槽机制介绍