百度研发类面试题（C++方向）
1、在函数内定义一个字符数组，用gets函数输入字符串的时候，如果输入越界，为什么程序会崩溃？
答：因为gets无法截断数组越界部分，会将所有输入都写入内存，这样越界部分就可能覆盖其他内容，造成程序崩溃。
2、C++中引用与指针的区别
答：联系：引用是变量的别名，可以将引用看做操作受限的指针；
区别：
1） 指针是一个实体，而引用仅是个别名；
2）引用只能在定义时必须初始化，指针可以不初始化为空；
3）引用初始化之后其地址就不可改变（即始终作该变量的别名直至销毁，即从一而终。注意：并不表示引用的值不可变，因为只要所指向的变量值改变。引用的值也就改变了），但指针所指地址是不可变的；如下：
int m=23,n=13;
int& a=m;
a=12; //合法，相当于修改m=12
a=n;//合法，相当于修改m=13
3、C/C++程序的内存分区
答：其实C和C++的内存分区还是有一定区别的，但此处不作区分：
1）、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其
操作方式类似于数据结构中的栈。
2）、堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回
收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
3）、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的
全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另
一块区域。 - 程序结束后由系统释放。
4）、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放
5）、程序代码区—存放函数体的二进制代码。
栈区与堆区的区别：
1）堆和栈中的存储内容：栈存局部变量、函数参数等。堆存储使用new、malloc申请的变量等；
2）申请方式：栈内存由系统分配，堆内存由自己申请；
3）申请后系统的响应：栈——只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
堆——首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表 中删除，并将该结点的空间分配给程序；
4）申请大小的限制：Windows下栈的大小一般是2M，堆的容量较大；
5）申请效率的比较：栈由系统自动分配，速度较快。堆使用new、malloc等分配，较慢；
总结：栈区优势在处理效率，堆区优势在于灵活；
内存模型：自由区、静态区、动态区；
根据c/c++对象生命周期不同，c/c++的内存模型有三种不同的内存区域，即：自由存储区，动态区、静态区。
自由存储区：局部非静态变量的存储区域，即平常所说的栈；
动态区： 用new ，malloc分配的内存，即平常所说的堆；
静态区：全局变量，静态变量，字符串常量存在的位置；
注：代码虽然占内存，但不属于c/c++内存模型的一部分；
4、快速排序的思想、时间复杂度、实现以及优化方法
答：快速排序的三个步骤：
(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 "基准"（pivot）；
(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大；
(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
基准的选择：
对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。
即：同一数组，时间复杂度最小的是每次选取的基准都可以将序列分为两个等长的；时间复杂度最大的是每次选择的基准都是当前序列的最大或最小元素；
快排代码实现：
我们一般选择序列的第一个作为基数，那么快排代码如下：
void quicksort(vector<int> &v,int left, int right)
{
if(left < right)//false则递归结束
{
int key=v[left];//基数赋值
int low = left;
int high = right;
while(low < high) //当low=high时，表示一轮分割结束
{
while(low < high && v[high] >= key)//v[low]为基数，从后向前与基数比较
{
high--;
}
swap(v[low],v[high]);
while(low < high && v[low] <= key)//v[high]为基数，从前向后与基数比较
{
low++;
}
swap(v[low],v[high]);
}
//分割后，对每一分段重复上述操作
quicksort(v,left,low-1);
quicksort(v,low+1,right);
}
}
注：上述数组或序列v必须是引用类型的形参，因为后续快排结果需要直接反映在原序列中；
优化：
上述快排的基数是序列的第一个元素，这样的对于有序序列，快排时间复杂度会达到最差的o(n^2)。所以，优化方向就是合理的选择基数。
常见的做法“三数取中”法（序列太短还要结合其他排序法，如插入排序、选择排序等），如下：
①当序列区间长度小于 7 时，采用插入排序；
②当序列区间长度小于 40 时，将区间分成2段，得到左端点、右端点和中点，我们对这三个点取中数作为基数；
③当序列区间大于等于 40 时，将区间分成 8 段，得到左三点、中三点和右三点，分别再得到左三点中的中数、中三点中的中数和右三点中的中数，再将得到的三个中数取中数，然后将该值作为基数。
具体代码只是在上一份的代码中将“基数赋值”改为①②③对应的代码即可：
int key=v[left];//基数赋值
if(right-left+1<=7){
insertion_sort(v,left,right);//插入排序
return;
}else if(right-left+1<=8){
key=SelectPivotOfThree(v,left,right);//三个取中
}else{
//三组三个取中，再三个取中（使用4次SelectPivotOfThree，此处不具体展示）
}
需要调用的函数：
void insertion_sort(vector<int> &unsorted,int left, int right) //插入排序算法
{
for (int i = left+1; i <= right; i++)
{
if (unsorted[i - 1] > unsorted[i])
{
int temp = unsorted[i];
int j = i;
while (j > left && unsorted[j - 1] > temp)
{
unsorted[j] = unsorted[j - 1];
j--;
}
unsorted[j] = temp;
}
}
}
int SelectPivotOfThree(vector<int> &arr,int low,int high) //三数取中，同时将中值移到序列第一位
{
int mid = low + (high - low)/2;//计算数组中间的元素的下标
//使用三数取中法选择枢轴
if (arr[mid] > arr[high])//目标: arr[mid] <= arr[high]
{
swap(arr[mid],arr[high]);
}
if (arr[low] > arr[high])//目标: arr[low] <= arr[high]
{
swap(arr[low],arr[high]);
}
if (arr[mid] > arr[low]) //目标: arr[low] >= arr[mid]
{
swap(arr[mid],arr[low]);
}
//此时，arr[mid] <= arr[low] <= arr[high]
return arr[low];
//low的位置上保存这三个位置中间的值
//分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了
}
这里需要注意的有两点：
①插入排序算法实现代码；
②三数取中函数不仅仅要实现取中，还要将中值移到最低位，从而保证原分割函数依然可用。
5、 IO模型——IO多路复用机制
答：预备知识介绍：
IO模型有4中：同步阻塞IO、同步非阻塞IO、异步阻塞IO、异步非阻塞IO；IO多路复用属于IO模型中的异步阻塞IO模型，在服务器高性能IO构建中常常用到。
同步异步是表示服务端的，阻塞非阻塞是表示用户端，所以可解释为什么IO多路复用（异步阻塞）常用于服务器端的原因；
文件描述符（FD，又叫文件句柄）：描述符就是一个数字，它指向内核中的一个结构体(文件路径，数据区等属性)。具体来源：Linux内核将所有外部设备都看作一个文件来操作，对文件的操作都会调用内核提供的系统命令，返回一个fd(文件描述符)。
下面开始介绍IO多路复用：
（1）I/O多路复用技术通过把多个I/O的阻塞复用到同一个select、poll或epoll的阻塞上，从而使得系统在单线程的情况下可以同时处理多个客户端请求。与传统的多线程/多进程模型比，I/O多路复用的最大优势是系统开销小，系统不需要创建新的额外进程或者线程。
（2）select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。
（3）I/O多路复用的主要应用场景如下：
服务器需要同时处理多个处于监听状态或者多个连接状态的套接字；
服务器需要同时处理多种网络协议的套接字；
（4）目前支持I/O多路复用的系统调用有 select，poll，epoll，epoll与select的原理比较类似，但epoll作了很多重大改进，现总结如下：
①支持一个进程打开的文件句柄FD个数不受限制（为什么select的句柄数量受限制：select使用位域的方式来传递关心的文件描述符，因为位域就有最大长度，在Linux下是1024，所以有数量限制）；
②I/O效率不会随着FD数目的增加而线性下降；
③epoll的API更加简单；
（5）三种接口调用介绍：
①select函数调用格式：
#include <sys/select.h>
#include <sys/time.h>
int select(int maxfdp1,fd_set *readset,fd_set *writeset,fd_set *exceptset,const struct timeval *timeout)
//返回值：就绪描述符的数目，超时返回0，出错返回-1
②poll函数调用格式：
# include <poll.h>
int poll ( struct pollfd * fds, unsigned int nfds, int timeout);
③epoll函数格式（操作过程包括三个函数）：
#include <sys/epoll.h>
int epoll_create(int size);
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);
（6）作用：一定程度上替代多线程/多进程，减少资源占用，保证系统运行的高效率；
更多细节待续……
6、常用的Linux命令
答：（1）查看CPU利用率：top
（2）查看当前目录：pwd和ls（ls -a可以查看隐藏目录）
（3）切换目录：cd
（4）查看文件占用磁盘大小：du和df
（5）创建文件夹：mkdir
（6）新建文件：touch
（7）查看文件：cat
（8）拷贝：cp 移动：mv 删除：rm
（9）查看进程：ps，如ps aux
（10）删除进程：kill -9 PID，注-9是参数
（11）程序运行时间：time，使用时在命令前添加time即可，如：time ./test，可得到三个时间：real 0m0.020s，user 0m0.000s，sys 0m0.018s
grep命令（重要的常用命令之一）：常用于打开文本修改保存，类似打windows开开TXT文本并修改；
sed命令（常用重要命令之一）：主要用于对文件的增删改查；
awk命令（重要常用命令之一）：取列是其擅长的；
find 命令（常与xargs命令配合）：查找 -type 文件类型-name 按名称查找-exec执行命令；
xargs命令：配合find/ls查找，将查找结果一条条的交给后***令处理；
gdb调试工具：
要调试C/C++的程序，一般有如下几个步骤：
①首先在编译时，我们必须要把调试信息加到可执行文件中，编译生成可执行文件-------> g++ -g hello.cpp -o hello；
②启动GDB编译hello程序----------> gdb hello;
③显示源码------------> l;
④开始调试：break 16——设置断点在16行，break func——设置断点在函数func()入口处，info break——查看断点信息，n——单步运行，c——继续运行程序，r——运行程序；p i——打印i的值，finish——退出程序，q——退出gdb。
7、C中变量的存储类型有哪些？
答：c语言中的存储类型有auto, extern, register, static 四种；
8、动态规划的本质
答：动归，本质上是一种划分子问题的算法，站在任何一个子问题的处理上看，当前子问题的提出都要依据现有的类似结论，而当前问题的结论是后面问题求解的铺垫。任何DP都是基于存储的算法，核心是状态转移方程。
9、实践中如何优化MySQL
答：四条从效果上第一条影响最大，后面越来越小。
① SQL语句及索引的优化
② 数据库表结构的优化
③ 系统配置的优化
④ 硬件的优化
10、 什么情况下设置了索引但无法使用
答：① LIKE语句，模糊匹配
② OR语句
③ 数据类型出现隐式转化（如varchar不加单引号的话可能会自动转换为int型）
11、 SQL语句的优化
答：alter尽量将多次合并为一次；
insert和delete也需要合并；
尽量使用union而不是or；
12.、数据库索引的底层实现原理和优化
答：B树，经过优化的B+树。主要是在所有的叶子结点中增加了指向下一个叶子节点的指针，因此InnoDB建议为大部分表使用默认自增的主键作为主索引。
13、HTTP和HTTPS的主要区别
14、 如何设计一个高并发的系统
答：① 数据库的优化，包括合理的事务隔离级别、SQL语句优化、索引的优化；
② 使用缓存，尽量减少数据库 IO；
③ 分布式数据库、分布式缓存；
④ 服务器的负载均衡；
15. 两条相交的单向链表，如何求他们的第一个公共节点
答：思想：
①如果两个链表相交，则从相交点开始，后面的节点都相同，即最后一个节点肯定相同；
②从头到尾遍历两个链表，并记录链表长度，当二者的尾节点不同，则二者肯定不相交；
③尾节点相同，如果A长为LA，B为LB，如果LA>LB,则A前LA-LB个先跳过；
——更多如链表相关经典问题：求单向局部循环链表的入、将两个有序链表合并合成一个有序链表、链表逆序、求倒数第K个节点，判断是否有环等。
16、求单向局部循环链表的环入口
答：思路：假如有快慢指针判断一个链表有局部环，链表起点是A，环的入口是B，快慢指针在环中的相遇点是C。那么按照原来的运动方向，有AB=CB，这是可以证明的结论。具体如下图说明：
17、IP地址如何在数据库中存储
答：常有以下几种存储方式：
说明一下：int类型的num存储在解码时是这样做的：
65=num%256；num=num/256;
120=num%256；num=num/256;
……
18、new/delete和malloc/free的底层实现
答：malloc和new的区别：
1）malloc与free是C++/C语言的标准库函数，new/delete是C++的运算符。它们都可用于申请动态内存和释放内存；
2）new 返回指定类型的指针，并且可以自动计算所需要大小。而 malloc 则必须要由程序员计算字节数，并且在返回后强行转换为实际类型的指针；
3）new/delete在对象创建的同时可以自动执行构造函数初始化，在对象在消亡之前会自动执行析构函数。而malloc 只管分配内存，并不能对所得的内存进行初始化，所以得到的一片新内存中，其值将是随机的；
既然new/delete的功能覆盖了malloc/free，为什么C++还要保留malloc/free？因为C++程序经常要调用C函数，而C程序只能用malloc/free管理动态内存。
new/delete、malloc/free底层实现原理：
概述：new/delete的底层实现是调用malloc/free函数实现的，而malloc/free的底层实现也不是直接操作内存而是调用系统API实现的。
new/delete的两种分配方式原理图如下：
注意，针对上图最末尾所述的“new[]/delete[]时会多开辟4字节用于存储对象个数”，作如下说明：
①对于内置类型：
new []不会在首地址前4个字节定义数组长度。
delete 和 delete[]是一样的执行效果，都会删除整个数组，要删除的长度从new时即可知道。
②对于自定义类型：
new []会在首地址前4个字节定义数组长度。
当delete[]时，会根据前4个字节所定义的长度来执行析构函数删除整个数组。
如果只是delete数组首地址，只会删除第一个对象的值。
19、overload、override、overwrite的介绍
答：（1）overload（重载），即函数重载：
①在同一个类中；
②函数名字相同；
③函数参数不同（类型不同、数量不同，两者满足其一即可）；
④不以返回值类型不同作为函数重载的条件。
（2）override（覆盖，子类改写父类的虚函数），用于实现C++中多态：
①分别位于父类和子类中；
②子类改写父类中的virtual方法；
③与父类中的函数原型相同。
（3）overwrite（重写或叫隐藏，子类改写父类的非虚函数，从而屏蔽父类函数）：
①与overload类似，但是范围不同，是子类改写父类；
②与override类似，但是父类中的方法不是虚函数。
20、小端/大端机器
答：小端/大端的区别是指低位数据存储在内存低位还是高位的区别。其中小端机器指：数据低位存储在内存地址低位，高位数据则在内存地址高位；大端机器正好相反。
当前绝大部分机器都是小端机器，就是比较符合人们逻辑思维的数据存储方式，比如intel的机器基本就都是小端机器。
21、守护进程
答：（1）什么是守护进程？
守护进程（Daemon Process），也就是通常说的 Daemon 进程（精灵进程），是 Linux 中的后台服务进程。它是一个生存期较长的进程，通常独立于
控制终端并且周期性地执行某种任务或等待处理某些发生的事件。
守护进程是个特殊的孤儿进程，这种进程脱离终端，为什么要脱离终端呢？之所以脱离于终端是为了避免进程被任何终端所产生的信息所打断，其在执
行过程中的信息也不在任何终端上显示。
（2）如何查看守护进程？
在终端敲：ps axj
从上图可以看出守护进行的一些特点：
守护进程基本上都是以超级用户启动（ UID 为 0 ）
没有控制终端（ TTY 为 ？）
终端进程组 ID 为 -1 （ TPGID 表示终端进程组 ID）
22、多线程
答：Java提供了3中多线程实现：Thread类、runable接口、使用ExecutorService、Callable、Future实现有返回结果的多线程。
而C++本身并没有提高多线程编程功能的库或接口，但Windows系统下的C++多线程编程还是可以通过<windows.h>库中的相关多线程接口实现，具体见：http://blog.csdn.net/xiongchao99/article/details/64441017#t107；
Linux写的C++多线程可以用头文件pthread.h，常用到其中两个函数pthread_create和pthread_join。下面是一个Linux下的简单C++多线程程序：
//Threads.cpp
#include <iostream>
#include <unistd.h>
#include <pthread.h>
using namespace std;
void *thread(void *ptr)
{
for(int i = 0;i < 3;i++) {
sleep(1);
cout << "This is a pthread." << endl;
}
return 0;
}
int main() {
pthread_t id;
int ret = pthread_create(&id, NULL, thread, NULL);//创建线程
if(ret) {
cout << "Create pthread error!" << endl;
return 1;
}
for(int i = 0;i < 3;i++) {
cout << "This is the main process." << endl;
sleep(1);
}
pthread_join(id, NULL);//等待线程结束
return 0;
}
多线程相关的同步的知识不再累述，此处来说说多线程优缺点：
多线程的主要优点包括:
(1)多线程技术使程序的响应速度更快 ,因为用户界面可以在进行其它工作的同时一直处于活动状态；
(2)占用大量处理时间的任务使用多线程可以提高CPU利用率，即占用大量处理时间的任务可以定期将处理器时间让给其它任务；
(3)多线程可以分别设置优先级以优化性能。
以下是最适合采用多线程处理：
(1)耗时或大量占用处理器的任务阻塞用户界面操作;
(2)各个任务必须等待外部资源 (如远程文件或 Internet连接)。
多线程的主要缺点包括：
(1)等候使用共享资源时造成程序的运行速度变慢。这些共享资源主要是独占性的资源 ,如打印机等。
(2)对线程进行管理要求额外的 CPU开销，线程的使用会给系统带来上下文切换的额外负担。
(3)线程的死锁。即对共享资源加锁实现同步的过程中可能会死锁。
(4)对公有变量的同时读或写，可能对造成脏读等；
23、长连接与短连接
答：（1）就是TCP长连接和TCP短连接：
①TCP长连接：TCP长连接指建立连接后保持连接而不断开。若一段时间内没有数据传输，服务器会发送心跳包给客户端，判断客户端是否还在线，叫做TCP长连接中的keep alive。一般步骤：连接→数据传输→保持连接(心跳)→数据传输→保持连接(心跳)→……→关闭连接；
②TCP短连接：指连接建立并传输数据完成后，就断开连接。一般步骤：连接→数据传输→关闭连接；
③使用场景：长连接适合单对单通信且连接数不太多的情况；短连接适合连接数多且经常更换连接对象的；
（2）HTTP是什么连接：
①在HTTP/1.0中，默认使用的是短连接。但从 HTTP/1.1起，默认使用长连接，用以保持连接特性。使用长连接的HTTP协议，会在响应头有加入这行代码：
Connection:keep-alive
注意：此处的keep-alive和上述TCP长连接原理介绍中的keep alive不是一个意思：此处表示告知服务器本http请求是长连接模式，而TCP长连接中的keep alive表示对客户端的保活检测。
②http长连接并不是一直保持连接
http的长连接也不会是永久保持连接，它有一个保持时间如20s（从上一次数据传输完成开始计时），可以在不同的服务器软件（如Apache）中设定这个时间，若超过该时间限制仍然无数据通信传输，服务器就主动关闭该连接。注：实现长连接要客户端和服务端都支持长连接。
③http连接实质：http的长连接/短连接实质上就是TCP的长/短连接。
24、二分图应用于最佳匹配问题（游客对房间的满意度之和最大问题）
答：题目：有n个游客和n个客房，每个游客对每间房有一个满意度，现要求做出一个入住安排，使得所有游客的满意度最大。
思路：用二分图解决，游客作为一边的顶点，客房作为另一边的顶点，取出所有最大匹配中满意度之和最大的方案。
#百度##面试题目##C++工程师#
答：因为gets无法截断数组越界部分，会将所有输入都写入内存，这样越界部分就可能覆盖其他内容，造成程序崩溃。
2、C++中引用与指针的区别
答：联系：引用是变量的别名，可以将引用看做操作受限的指针；
区别：
1） 指针是一个实体，而引用仅是个别名；
2）引用只能在定义时必须初始化，指针可以不初始化为空；
3）引用初始化之后其地址就不可改变（即始终作该变量的别名直至销毁，即从一而终。注意：并不表示引用的值不可变，因为只要所指向的变量值改变。引用的值也就改变了），但指针所指地址是不可变的；如下：
int m=23,n=13;
int& a=m;
a=12; //合法，相当于修改m=12
a=n;//合法，相当于修改m=13
3、C/C++程序的内存分区
答：其实C和C++的内存分区还是有一定区别的，但此处不作区分：
1）、栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其
操作方式类似于数据结构中的栈。
2）、堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回
收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
3）、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的
全局变量和静态变量在一块区域， 未初始化的全局变量和未初始化的静态变量在相邻的另
一块区域。 - 程序结束后由系统释放。
4）、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放
5）、程序代码区—存放函数体的二进制代码。
栈区与堆区的区别：
1）堆和栈中的存储内容：栈存局部变量、函数参数等。堆存储使用new、malloc申请的变量等；
2）申请方式：栈内存由系统分配，堆内存由自己申请；
3）申请后系统的响应：栈——只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。
堆——首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表 中删除，并将该结点的空间分配给程序；
4）申请大小的限制：Windows下栈的大小一般是2M，堆的容量较大；
5）申请效率的比较：栈由系统自动分配，速度较快。堆使用new、malloc等分配，较慢；
总结：栈区优势在处理效率，堆区优势在于灵活；
内存模型：自由区、静态区、动态区；
根据c/c++对象生命周期不同，c/c++的内存模型有三种不同的内存区域，即：自由存储区，动态区、静态区。
自由存储区：局部非静态变量的存储区域，即平常所说的栈；
动态区： 用new ，malloc分配的内存，即平常所说的堆；
静态区：全局变量，静态变量，字符串常量存在的位置；
注：代码虽然占内存，但不属于c/c++内存模型的一部分；
4、快速排序的思想、时间复杂度、实现以及优化方法
答：快速排序的三个步骤：
(1)选择基准：在待排序列中，按照某种方式挑出一个元素，作为 "基准"（pivot）；
(2)分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比该基准小，在基准右边的元素都比基准大；
(3)递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
基准的选择：
对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法效率会达到最大。
即：同一数组，时间复杂度最小的是每次选取的基准都可以将序列分为两个等长的；时间复杂度最大的是每次选择的基准都是当前序列的最大或最小元素；
快排代码实现：
我们一般选择序列的第一个作为基数，那么快排代码如下：
void quicksort(vector<int> &v,int left, int right)
{
if(left < right)//false则递归结束
{
int key=v[left];//基数赋值
int low = left;
int high = right;
while(low < high) //当low=high时，表示一轮分割结束
{
while(low < high && v[high] >= key)//v[low]为基数，从后向前与基数比较
{
high--;
}
swap(v[low],v[high]);
while(low < high && v[low] <= key)//v[high]为基数，从前向后与基数比较
{
low++;
}
swap(v[low],v[high]);
}
//分割后，对每一分段重复上述操作
quicksort(v,left,low-1);
quicksort(v,low+1,right);
}
}
注：上述数组或序列v必须是引用类型的形参，因为后续快排结果需要直接反映在原序列中；
优化：
上述快排的基数是序列的第一个元素，这样的对于有序序列，快排时间复杂度会达到最差的o(n^2)。所以，优化方向就是合理的选择基数。
常见的做法“三数取中”法（序列太短还要结合其他排序法，如插入排序、选择排序等），如下：
①当序列区间长度小于 7 时，采用插入排序；
②当序列区间长度小于 40 时，将区间分成2段，得到左端点、右端点和中点，我们对这三个点取中数作为基数；
③当序列区间大于等于 40 时，将区间分成 8 段，得到左三点、中三点和右三点，分别再得到左三点中的中数、中三点中的中数和右三点中的中数，再将得到的三个中数取中数，然后将该值作为基数。
具体代码只是在上一份的代码中将“基数赋值”改为①②③对应的代码即可：
int key=v[left];//基数赋值
if(right-left+1<=7){
insertion_sort(v,left,right);//插入排序
return;
}else if(right-left+1<=8){
key=SelectPivotOfThree(v,left,right);//三个取中
}else{
//三组三个取中，再三个取中（使用4次SelectPivotOfThree，此处不具体展示）
}
需要调用的函数：
void insertion_sort(vector<int> &unsorted,int left, int right) //插入排序算法
{
for (int i = left+1; i <= right; i++)
{
if (unsorted[i - 1] > unsorted[i])
{
int temp = unsorted[i];
int j = i;
while (j > left && unsorted[j - 1] > temp)
{
unsorted[j] = unsorted[j - 1];
j--;
}
unsorted[j] = temp;
}
}
}
int SelectPivotOfThree(vector<int> &arr,int low,int high) //三数取中，同时将中值移到序列第一位
{
int mid = low + (high - low)/2;//计算数组中间的元素的下标
//使用三数取中法选择枢轴
if (arr[mid] > arr[high])//目标: arr[mid] <= arr[high]
{
swap(arr[mid],arr[high]);
}
if (arr[low] > arr[high])//目标: arr[low] <= arr[high]
{
swap(arr[low],arr[high]);
}
if (arr[mid] > arr[low]) //目标: arr[low] >= arr[mid]
{
swap(arr[mid],arr[low]);
}
//此时，arr[mid] <= arr[low] <= arr[high]
return arr[low];
//low的位置上保存这三个位置中间的值
//分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了
}
这里需要注意的有两点：
①插入排序算法实现代码；
②三数取中函数不仅仅要实现取中，还要将中值移到最低位，从而保证原分割函数依然可用。
更多C/C++ linux面试题面试技巧及相关学习资料请加群563998835
答：预备知识介绍：
IO模型有4中：同步阻塞IO、同步非阻塞IO、异步阻塞IO、异步非阻塞IO；IO多路复用属于IO模型中的异步阻塞IO模型，在服务器高性能IO构建中常常用到。
同步异步是表示服务端的，阻塞非阻塞是表示用户端，所以可解释为什么IO多路复用（异步阻塞）常用于服务器端的原因；
文件描述符（FD，又叫文件句柄）：描述符就是一个数字，它指向内核中的一个结构体(文件路径，数据区等属性)。具体来源：Linux内核将所有外部设备都看作一个文件来操作，对文件的操作都会调用内核提供的系统命令，返回一个fd(文件描述符)。
下面开始介绍IO多路复用：
（1）I/O多路复用技术通过把多个I/O的阻塞复用到同一个select、poll或epoll的阻塞上，从而使得系统在单线程的情况下可以同时处理多个客户端请求。与传统的多线程/多进程模型比，I/O多路复用的最大优势是系统开销小，系统不需要创建新的额外进程或者线程。
（2）select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的，而异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间。
（3）I/O多路复用的主要应用场景如下：
服务器需要同时处理多个处于监听状态或者多个连接状态的套接字；
服务器需要同时处理多种网络协议的套接字；
（4）目前支持I/O多路复用的系统调用有 select，poll，epoll，epoll与select的原理比较类似，但epoll作了很多重大改进，现总结如下：
①支持一个进程打开的文件句柄FD个数不受限制（为什么select的句柄数量受限制：select使用位域的方式来传递关心的文件描述符，因为位域就有最大长度，在Linux下是1024，所以有数量限制）；
②I/O效率不会随着FD数目的增加而线性下降；
③epoll的API更加简单；
（5）三种接口调用介绍：
①select函数调用格式：
#include <sys/select.h>
#include <sys/time.h>
int select(int maxfdp1,fd_set *readset,fd_set *writeset,fd_set *exceptset,const struct timeval *timeout)
//返回值：就绪描述符的数目，超时返回0，出错返回-1
②poll函数调用格式：
# include <poll.h>
int poll ( struct pollfd * fds, unsigned int nfds, int timeout);
③epoll函数格式（操作过程包括三个函数）：
#include <sys/epoll.h>
int epoll_create(int size);
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);
int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);
（6）作用：一定程度上替代多线程/多进程，减少资源占用，保证系统运行的高效率；
更多细节待续……
6、常用的Linux命令
答：（1）查看CPU利用率：top
（2）查看当前目录：pwd和ls（ls -a可以查看隐藏目录）
（3）切换目录：cd
（4）查看文件占用磁盘大小：du和df
（5）创建文件夹：mkdir
（6）新建文件：touch
（7）查看文件：cat
（8）拷贝：cp 移动：mv 删除：rm
（9）查看进程：ps，如ps aux
（10）删除进程：kill -9 PID，注-9是参数
（11）程序运行时间：time，使用时在命令前添加time即可，如：time ./test，可得到三个时间：real 0m0.020s，user 0m0.000s，sys 0m0.018s
grep命令（重要的常用命令之一）：常用于打开文本修改保存，类似打windows开开TXT文本并修改；
sed命令（常用重要命令之一）：主要用于对文件的增删改查；
awk命令（重要常用命令之一）：取列是其擅长的；
find 命令（常与xargs命令配合）：查找 -type 文件类型-name 按名称查找-exec执行命令；
xargs命令：配合find/ls查找，将查找结果一条条的交给后***令处理；
gdb调试工具：
要调试C/C++的程序，一般有如下几个步骤：
①首先在编译时，我们必须要把调试信息加到可执行文件中，编译生成可执行文件-------> g++ -g hello.cpp -o hello；
②启动GDB编译hello程序----------> gdb hello;
③显示源码------------> l;
④开始调试：break 16——设置断点在16行，break func——设置断点在函数func()入口处，info break——查看断点信息，n——单步运行，c——继续运行程序，r——运行程序；p i——打印i的值，finish——退出程序，q——退出gdb。
7、C中变量的存储类型有哪些？
答：c语言中的存储类型有auto, extern, register, static 四种；
8、动态规划的本质
答：动归，本质上是一种划分子问题的算法，站在任何一个子问题的处理上看，当前子问题的提出都要依据现有的类似结论，而当前问题的结论是后面问题求解的铺垫。任何DP都是基于存储的算法，核心是状态转移方程。
9、实践中如何优化MySQL
答：四条从效果上第一条影响最大，后面越来越小。
① SQL语句及索引的优化
② 数据库表结构的优化
③ 系统配置的优化
④ 硬件的优化
更多C/C++ linux面试题面试技巧及相关学习资料请加群563998835
答：① LIKE语句，模糊匹配
② OR语句
③ 数据类型出现隐式转化（如varchar不加单引号的话可能会自动转换为int型）
11、 SQL语句的优化
答：alter尽量将多次合并为一次；
insert和delete也需要合并；
尽量使用union而不是or；
12.、数据库索引的底层实现原理和优化
答：B树，经过优化的B+树。主要是在所有的叶子结点中增加了指向下一个叶子节点的指针，因此InnoDB建议为大部分表使用默认自增的主键作为主索引。
13、HTTP和HTTPS的主要区别
答：略
答：① 数据库的优化，包括合理的事务隔离级别、SQL语句优化、索引的优化；
② 使用缓存，尽量减少数据库 IO；
③ 分布式数据库、分布式缓存；
④ 服务器的负载均衡；
15. 两条相交的单向链表，如何求他们的第一个公共节点
答：思想：
①如果两个链表相交，则从相交点开始，后面的节点都相同，即最后一个节点肯定相同；
②从头到尾遍历两个链表，并记录链表长度，当二者的尾节点不同，则二者肯定不相交；
③尾节点相同，如果A长为LA，B为LB，如果LA>LB,则A前LA-LB个先跳过；
——更多如链表相关经典问题：求单向局部循环链表的入、将两个有序链表合并合成一个有序链表、链表逆序、求倒数第K个节点，判断是否有环等。
16、求单向局部循环链表的环入口
答：思路：假如有快慢指针判断一个链表有局部环，链表起点是A，环的入口是B，快慢指针在环中的相遇点是C。那么按照原来的运动方向，有AB=CB，这是可以证明的结论。具体如下图说明：
17、IP地址如何在数据库中存储
答：常有以下几种存储方式：
说明一下：int类型的num存储在解码时是这样做的：
65=num%256；num=num/256;
120=num%256；num=num/256;
……
18、new/delete和malloc/free的底层实现
答：malloc和new的区别：
1）malloc与free是C++/C语言的标准库函数，new/delete是C++的运算符。它们都可用于申请动态内存和释放内存；
2）new 返回指定类型的指针，并且可以自动计算所需要大小。而 malloc 则必须要由程序员计算字节数，并且在返回后强行转换为实际类型的指针；
3）new/delete在对象创建的同时可以自动执行构造函数初始化，在对象在消亡之前会自动执行析构函数。而malloc 只管分配内存，并不能对所得的内存进行初始化，所以得到的一片新内存中，其值将是随机的；
既然new/delete的功能覆盖了malloc/free，为什么C++还要保留malloc/free？因为C++程序经常要调用C函数，而C程序只能用malloc/free管理动态内存。
new/delete、malloc/free底层实现原理：
概述：new/delete的底层实现是调用malloc/free函数实现的，而malloc/free的底层实现也不是直接操作内存而是调用系统API实现的。
new/delete的两种分配方式原理图如下：
注意，针对上图最末尾所述的“new[]/delete[]时会多开辟4字节用于存储对象个数”，作如下说明：
①对于内置类型：
new []不会在首地址前4个字节定义数组长度。
delete 和 delete[]是一样的执行效果，都会删除整个数组，要删除的长度从new时即可知道。
②对于自定义类型：
new []会在首地址前4个字节定义数组长度。
当delete[]时，会根据前4个字节所定义的长度来执行析构函数删除整个数组。
如果只是delete数组首地址，只会删除第一个对象的值。
19、overload、override、overwrite的介绍
答：（1）overload（重载），即函数重载：
①在同一个类中；
②函数名字相同；
③函数参数不同（类型不同、数量不同，两者满足其一即可）；
④不以返回值类型不同作为函数重载的条件。
（2）override（覆盖，子类改写父类的虚函数），用于实现C++中多态：
①分别位于父类和子类中；
②子类改写父类中的virtual方法；
③与父类中的函数原型相同。
（3）overwrite（重写或叫隐藏，子类改写父类的非虚函数，从而屏蔽父类函数）：
①与overload类似，但是范围不同，是子类改写父类；
②与override类似，但是父类中的方法不是虚函数。
20、小端/大端机器
答：小端/大端的区别是指低位数据存储在内存低位还是高位的区别。其中小端机器指：数据低位存储在内存地址低位，高位数据则在内存地址高位；大端机器正好相反。
当前绝大部分机器都是小端机器，就是比较符合人们逻辑思维的数据存储方式，比如intel的机器基本就都是小端机器。
21、守护进程
答：（1）什么是守护进程？
守护进程（Daemon Process），也就是通常说的 Daemon 进程（精灵进程），是 Linux 中的后台服务进程。它是一个生存期较长的进程，通常独立于
控制终端并且周期性地执行某种任务或等待处理某些发生的事件。
守护进程是个特殊的孤儿进程，这种进程脱离终端，为什么要脱离终端呢？之所以脱离于终端是为了避免进程被任何终端所产生的信息所打断，其在执
行过程中的信息也不在任何终端上显示。
（2）如何查看守护进程？
在终端敲：ps axj
从上图可以看出守护进行的一些特点：
守护进程基本上都是以超级用户启动（ UID 为 0 ）
没有控制终端（ TTY 为 ？）
终端进程组 ID 为 -1 （ TPGID 表示终端进程组 ID）
22、多线程
答：Java提供了3中多线程实现：Thread类、runable接口、使用ExecutorService、Callable、Future实现有返回结果的多线程。
而C++本身并没有提高多线程编程功能的库或接口，但Windows系统下的C++多线程编程还是可以通过<windows.h>库中的相关多线程接口实现，具体见：http://blog.csdn.net/xiongchao99/article/details/64441017#t107；
Linux写的C++多线程可以用头文件pthread.h，常用到其中两个函数pthread_create和pthread_join。下面是一个Linux下的简单C++多线程程序：
//Threads.cpp
#include <iostream>
#include <unistd.h>
#include <pthread.h>
using namespace std;
void *thread(void *ptr)
{
for(int i = 0;i < 3;i++) {
sleep(1);
cout << "This is a pthread." << endl;
}
return 0;
}
int main() {
pthread_t id;
int ret = pthread_create(&id, NULL, thread, NULL);//创建线程
if(ret) {
cout << "Create pthread error!" << endl;
return 1;
}
for(int i = 0;i < 3;i++) {
cout << "This is the main process." << endl;
sleep(1);
}
pthread_join(id, NULL);//等待线程结束
return 0;
}
多线程相关的同步的知识不再累述，此处来说说多线程优缺点：
多线程的主要优点包括:
(1)多线程技术使程序的响应速度更快 ,因为用户界面可以在进行其它工作的同时一直处于活动状态；
(2)占用大量处理时间的任务使用多线程可以提高CPU利用率，即占用大量处理时间的任务可以定期将处理器时间让给其它任务；
(3)多线程可以分别设置优先级以优化性能。
以下是最适合采用多线程处理：
(1)耗时或大量占用处理器的任务阻塞用户界面操作;
(2)各个任务必须等待外部资源 (如远程文件或 Internet连接)。
多线程的主要缺点包括：
(1)等候使用共享资源时造成程序的运行速度变慢。这些共享资源主要是独占性的资源 ,如打印机等。
(2)对线程进行管理要求额外的 CPU开销，线程的使用会给系统带来上下文切换的额外负担。
(3)线程的死锁。即对共享资源加锁实现同步的过程中可能会死锁。
(4)对公有变量的同时读或写，可能对造成脏读等；
23、长连接与短连接
答：（1）就是TCP长连接和TCP短连接：
①TCP长连接：TCP长连接指建立连接后保持连接而不断开。若一段时间内没有数据传输，服务器会发送心跳包给客户端，判断客户端是否还在线，叫做TCP长连接中的keep alive。一般步骤：连接→数据传输→保持连接(心跳)→数据传输→保持连接(心跳)→……→关闭连接；
②TCP短连接：指连接建立并传输数据完成后，就断开连接。一般步骤：连接→数据传输→关闭连接；
③使用场景：长连接适合单对单通信且连接数不太多的情况；短连接适合连接数多且经常更换连接对象的；
（2）HTTP是什么连接：
①在HTTP/1.0中，默认使用的是短连接。但从 HTTP/1.1起，默认使用长连接，用以保持连接特性。使用长连接的HTTP协议，会在响应头有加入这行代码：
Connection:keep-alive
注意：此处的keep-alive和上述TCP长连接原理介绍中的keep alive不是一个意思：此处表示告知服务器本http请求是长连接模式，而TCP长连接中的keep alive表示对客户端的保活检测。
②http长连接并不是一直保持连接
http的长连接也不会是永久保持连接，它有一个保持时间如20s（从上一次数据传输完成开始计时），可以在不同的服务器软件（如Apache）中设定这个时间，若超过该时间限制仍然无数据通信传输，服务器就主动关闭该连接。注：实现长连接要客户端和服务端都支持长连接。
③http连接实质：http的长连接/短连接实质上就是TCP的长/短连接。
24、二分图应用于最佳匹配问题（游客对房间的满意度之和最大问题）
答：题目：有n个游客和n个客房，每个游客对每间房有一个满意度，现要求做出一个入住安排，使得所有游客的满意度最大。
思路：用二分图解决，游客作为一边的顶点，客房作为另一边的顶点，取出所有最大匹配中满意度之和最大的方案。
实现：涉及匈牙利算法；
更多C/C++ linux面试题面试技巧及相关学习资料请加群563998835
#百度##面试题目##C++工程师#