Q：介绍一下自己吧；

A：blabla

Q：介绍项目

A：blabla

Q：来说一下C++的内存管理

A：C++内存分为堆区、栈区、代码区、全局区。其中代码区是存放代码的部分，全局区存放全局变量和静态变量的部分。而栈区是运行时局变量的内存，堆区是用new和malloc的函数申请出来的内存。一般来说内存管理就是管理的这部分内存，堆区的内存一开始很少，但是随着程序的运行会慢慢变大，而且容易碎片化。

Q：来说一下c++的多态

A：多态既是一个类的多种形态，C++通过虚函数的方式实现多态，即如果一个基类被子类集成，如果相关函数使用虚函数的话在如果基类指针指向子类对象，那么调用方法时候就会调用子类的，实现多态性。

Q：来讲一下三次握手、四次挥手

A：三次握手：服务器处于listen状态的时候可以接受客户端的链接。既客户端发送一个SYN，服务器回复一个SYN+ACK，客户端在回复一个ACK完成连接。

四次挥手：一般来说都是客户端主动要求关闭连接，客户端发送一个FIN，服务器回复一个ACK，但是此时服务器有个能还有没发送完的数据，等到这些数据处理完之后服务器才会回复一个FIN，然后客户端会回复一个ACK。服务器收到这个ACK后会直接关闭连接，而客户端则会等2MSL之后关闭。

Q：为什么是三次握手？

A：这个问题在《自顶向下》里面提到过，大概是防止网络中滞留已久的SYN发送给服务器后让服务器误以为是一个新的连接。如果两次握手的话会出现这个问题，三次握手不会。而我个人认为除了这个原因外，三次握手可以相互确认双方的一些信息，比如初始序列号，MTU等参数。

Q：你对网络通信的安全了解有哪些？

A：TCP方面有一个泛洪攻击，即黑客不断向服务器发送第一次握手不回复第三次握手，这样会导致服务器不断开辟新的内存而崩溃。解决办法是SYN_cookie，服务器在收到syn之后先不为其开辟内存，而是通过一系列信息设置一个参数作为初始序列号给客户机，等客户机回应第三次握手之后再为其开辟内存。

HTTPS加密方式了解一点，HTTPS即HTTP和TCP之间加一个SSL协议。过程是双方通信的时候服务器先给客户机发送一个安全证书，客户机用一个秘钥对这个证书进行加密，之后将密码返回给服务器，服务器利用这个证书和加密后的数据进行解密获得随机数。之后双方通过这个随机数进行加密通信。

Q：数据库事务了解吗？

A：我数据库没有深入了解，只会增删改查（暗示不要问了）。

Q：来讲一个你熟悉的排序吧，分析一下复杂度。

A：我将一般排序分为三种，第一种快的O(nlogn)的，分别是快排、堆排、归并排序。第二种只有一个就是希尔排序，第三种就是O(n^2)那些了：选择排序、插入排序、冒泡排序……。

对于快排，虽然现在大部分库函数主流都是快排，但是快排相对来说不稳定。而归并排序相对稳定，但是我认为不选择归并排序的原因主要是因为归并排序需要开二倍空间，浪费内存。

（其实还有两种，第四种是桶排序、计数排序……，第五种是闹着玩排序：比如睡眠排序、猴子排序）

而我其实最喜欢堆排序，堆排序包括两个步骤：建堆和根据已建堆进行排序。其建堆复杂度是O(n)，第一次知道建堆复杂度是O(n)的时候我其实很惊讶，但这其实很容易证明，利用高中所学数列中的裂项相消法既可证明。然后第二部是排序，其复杂度是O(nlogn)。其实我个人认为第二步的复杂度严格来说是O(log(n!))，但是其实O(log(n!))与O(nlogn)等价。所以不做讨论。（然后介绍怎么建堆和通过堆排序blabla）。

堆排序相对于快排来说很稳定，相对于归并来说不耗费内存。但是为什么不选择堆排序呢？这是因为操作系统机制导致的。我们都知道操作系统给你的并不是真是的空间而是分页的虚拟内存。你认为的数组是连续的实际是不连续的，你每次查询页时候操作系统都会先查询TLB（快表），如果TLB里面不存在这个页则会去内存中寻找。堆排序的缺点就在于此，因为堆排序是树形结构导致每次访问空间不连续需要不断查询页表。而归并与快排相对连续，每次TLB命中率较高所以常数较小表现良好。

但是理论上来说堆排序是世界上最好的排序，好于快排与归并，由于现实原因没有选择快排。

（这里我blabla了一堆，不知道面试官烦不烦……）

然后就是写题环节了。

给你一个数组：问你是否能分为平均数相同的两组。

问了下有没有数据范围

我就dfs写的。