C++面试题
https://www.nowcoder.com/discuss/231656
红黑树性质
poll，epoll
new和malloc区别
TCP四次挥手为啥不更多 TCP有哪些特性保证了其可靠性，其中哪一个可以去掉
指针和引用？什么时候用指针什么时候引用？
(指针可以不初始化，引用必须初始化，且绑定后不能再变；向函数中传递指针和传递指针的引用的区别：
传递指针，会先复制该指针，在函数内部使用的是复制后的指针，这个指针与原来的指针指向相同的地址，如果在函数内部将复制后的指针指向了另外的新的对象，那么不会影响原有的指针；
对于传递指针引用，如果将传递进来的指针指向了新的对象，那么原始的指针也就指向了新的对象，这样就会造成内存泄漏，因为原来指针指向的地方已经不能再引用了，即使没有将传递进来的指针指向新的对象，而是在函数结束的时候释放了指针，那么在函数外部就不能再使用原有的指针了，因为原来的内存已经被释放了)
8、什么是堆？
答：平时只用数组模拟堆，不知道真实的结构，认为是父节点-子节点这样状态的数据结构（超高频问题，一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS（操作系统）回收。分配方式类似于链表。向上增长，栈的分割开辟在程序运行时进行，内核顺着链表找到一块足够大的空间交给程序，如果没找到就析构调无用内存再找一次，更具体的请自行总结一下并时常复习，区别包括申请方式、系统响应等很多）
9、堆和栈的区别
栈就是存东西的空间，往最里面存，出来是最外面出来（超高频问题，函数运行时分配，函数结束时释放。由编译器自动分配释放 ，存放为运行函数而分配的局部变量、函数参数、返回数据、返回地址等。向下开辟，速度很快，局部性能好的话会和寄存器交互，存PC指针，函数参数多也会组成栈帧存到栈里面）
10、进程和线程
（超高频问题，我看了深入理解计算机系统后的总结：1、进程就是活着的程序，程序不过是一些文本，运行着的程序就是进程，是系统进行资源调度和分配的基本单位，掌握资源，包括内存等，线程就是轻量级进程，是CPU调度和分派基本单位。2、由于进程占有资源，压栈和出栈慢，所以切换不灵活，线程不占资源，只占必要的资源（递归要压栈所以有一点资源），所以线程容易通信->在进程分来的内存中直接通信，容易并发->切换灵活，同一进程的线程切换速度很快，因此线程开销小3、地址空间，进程独立，同一进程的线程共享资源，对其他进程的线程独立）
1、include的时候怎么避免重复include
ifdef(当时就说了这个词，懂得自然懂)
(还有ifndef都一个意思，ifdef是否定义过了；ifndef是否没定义过，就这一点区别，都是一个意思，因为.h默认就是用来声明的，我们显然不希望include多次，不仅效率低，而且变量会被重复声明，因此在开头加个判断，如果定义了，就不执行下面程序了等等。此语句是预编译需要的语句，因为它指明了接下来的程序段要不要被编译，所以带#，表明这是预编译过程，格式上和结束判断一起使用，格式一般是
#ifdef XXX
;
#else
#define XXX
#endif
或者是
#ifndef XXX
#define XXX
XXXX
#endif
)
2、static
static对全局变量，限制全局变量作用范围。链接的时候，变量被分为内部、外部、全局。全局变量就是这个可重定位文件内部的全局变量，外部变量就是外部文件的全部变量，内部变量就是static修饰的变量。作用域就是先全局变量(对应当前的全局变量、然后再内部再外部)内部变量重定位的时候，外部变量无法通过自身外部变量的指示找到这个变量，就实现了保护？还是屏蔽？总之就是限定作用域。
static修饰局部变量，存储位置就从栈变为静态存储区，(生命周期变长)，函数迭代的时候就可能用到上一次的局部变量。
static修饰类内变量，存储位置从类里面转移到外部，这样所有的类实体公用(或共用)一个变量。
static修饰类函数，类函数因为在外面，看不见类的变量，所以只能看到类的static变量，也只能使用它，不能用别的变量。
其他的想不起来了。
(还有初始化为0这个功能。解决重定义的功能:就是把变量限制在本文件中，和上面一个意思，最好都说出来)
3、static类内函数和类内普通有什么区别？
感觉答上一个题的时候答完了，复述一下，提到static变量是共享的要注意就结束。
4、extern用过吗
我说链接的时候，extern就是外部的全局变量，就去找。巴拉巴拉。
还有其他的功能吗？答没想起来。
(还有这个，链接指示功能，extern"C"就是用C语言的方法去搞，类比得出extern"其他语言"，估计面试官想让我答这个，除了背谁能想到，大家都会用，谁不知道还有这个功能，灯下黑。。。和static默认初始化0一样没答出来)
5、malloc和free
malloc的功能是隐式空闲链表(不是通用分配器用的方法，是简单的实现)，找一合适大小空闲空间挖出来返回，先找一下，找不到申请帮助，内核会合并相邻小碎片，重新找一次，找不到就调什么什么brk还是rbk去申请更大的空间(sbrk函数)，然后返回的是void*，需要我们自己强制类型转换成需要的类型。malloc是库函数。
那么new呢？运算符，可以重载，如果没申请出来就中断。malloc返回空。new还是一个就是可以输入类型符，就是new个int，然后算大小他会把int的大小算进去，malloc需要自己算。一个存储区上一个在堆上，这两个的区别是巴拉巴拉。
(new会调构造函数、malloc不构造函数)
6、堆和自由存储区区别？
**(我不是刚说了么)**堆是C的概念，自由存储区是C++的概念，两者在概念上有根本的不同，但C++沿袭了C，实际使用的是一块空间。
7、malloc后的返回值是一个指针，然后这个指针可以加数吗？
可以加。(指针不就随便加)
能吗？那么这个值+了几个数后在free会怎么样？
懂了，面试官上一个问的应该是这个含义->新空间的首地址，可以加么。不可以加，这样free的时候内存泄露。
8、你有没有检测过内存泄露。
没检测过。我程序最大的问题是重复析构，当时想办法解决了这个问题。巴拉巴拉。为什么会这样，巴拉巴拉。如何解决巴拉巴拉。
(问了问收割大佬，以下是原话：VS有个CRTDBG可以打印内存开辟和内存释放，也可以对内存使用情况快拍，这是VS工具，单独的工具有bound_checker，功能是类似的其实。Linux是Vargrind)
9、内存泄露会怎么样？
和面试官同时回答:占得空间越来越大。
10、重复析构会报错啊？
是的。我的软件中间有一段时间会在主程序在退出的时候会把申请的空间释放掉，所以关程序会报错(程序崩掉，就是弹出一个报错框，0x什么什么，一个大数字)。
11、智能指针？
用python的角度介绍了智能指针，计数法析构内存，python是引用自动析构内存，没有显式指针可用，用的是引用，被引一次就+1，不被引了就-1。为的0的时候，我们就找不到这块变量了，就自由析构了。
一边讲一边想到面试官可能要问循环引用了，就讲python本身解决不了，用的是gc垃圾收集器定位然后析构掉。C++用的是weak_ptr解决这个问题。(点到即止，懂得自然懂，面试官想问就问不问拉倒)
12、智能指针转普通指针注意什么？
说没转过，懒得分析说不会。
(找了另一个工具人大佬问了问，大佬说智能指针的作用就是帮你把这些东西封装成比较安全的使用的类，如果把share的指针转化为普通指针，这个时候share的又自动释放掉了这个东西，如果这时候此指针当普通指针用，会用到已经被释放掉的东西。而weak_ptr转换为普通指针的时候，不会改变计数，引发访问到已被释放空间的时候，就会报错，发生如此之风险)
char多大？
本来想说-128到+127，突然顿悟，答1字节。此题有些意思。
上下文切换需要保存的内容？？
保存PC指针，其他的想不起来了。
1、从数组找三个数，三和与value差最小
要求时间O(n2)空间O(1)
我的写法是排序+双指针，leecode上的原题**，**没怎么刷过leecode，还好解法一致。
排序是手写快排。
另有解法是打表法，注意value = 3*nums[i]的特殊情况，python不要用set这种结构，不太好。用dic。C++可以用map。
7、重载和重写
(注意重写是对虚函数的重写，我当时就答错了，所谓重载就是同名函数参数表不同，编译时会对函数改名，其实运行的时候他们已经不是同名的了；重写是虚函数重写，子类对父类的非虚函数在写一遍叫重定义或者隐藏，反正不是重写，重写是对虚函数的重写)
8、大数据 买东西 找买东西最多的100个 怎么做
建个哈希表 小顶堆。
9、MAP底层怎么做的
我说还没看底层代码。（话说我一直不知道有MAP这种东西存在，都是手撸哈希表，准备有时间看一下STL源码分析）
(底层红黑树，一种O(log(n)的查找插入和删除数据结构，实际是2-3树，伪平衡二叉树)
1000以内的最大素数
说了Python能够O（1）空间实现素数生成器，筛选法，但是没写，没要求就不写，直接bool判断就好，注意从大到小
分析复杂度，如何减少复杂度？从上到下，从999开始往下搜，搜到就停，每次-2。
bool判断，从2到根号x开始，全求模，非0跳出False。
6、静态内存和动态内存?
讲了static和堆栈是静态,编译的时候决定了大小，动态内存可以自由开辟->堆，也不知道对不对。。
（回来问了问另一个收割大佬，应该是这样）
7、堆是？
说了向上开辟，速度慢、运行时改，然后开辟的过程，链表存着下一个位置和这一块有没有使用，如果没找到就析构合并内存再找，再找不到返回null（可以参考前面的答案）
8、堆栈是？
说了向下开辟、速度快、编译时分配、主要是存PC指针，然后函数入口参数多组成栈帧存进去等着恢复
9、malloc和new区别 free和delete？
1、一个是函数（面试官没问，但我自觉呀，诚实回答忘了是哪个头文件里的了，事后查了查是stdlib我擦我天天写没想到是这个）一个是关键字
2、malloc要算大小，返回void*(然后随口提到void*可以转XX *),强转后按转完后的类型用，要自己算大小；new的时候传类型，就比如100个int，然后直接开100个就好了，他自动将int长度算进去
3、malloc再堆上，new在自由存储区（然后回答忘了自由存储区再哪了） 讲着讲着忘了free和delete的事了
(自由存储区和堆似乎是概念上的区别？我丢，深入理解计算机基础是按C讲的，我哪知道C++的自由存储区和C的堆有啥区别呀，按理来说假如new是依赖malloc实现的，那么他们不该开辟于同一块区域么。C++默认在堆上开辟new需要的空间，所以new来自自由存储区和堆都行。
网搜的答案：
自由存储区是C++中通过new与delete动态分配和释放对象的抽象概念，而堆（heap）是C语言和操作系统的术语，是操作系统维护的一块动态分配内存。
new所申请的内存区域在C++中称为自由存储区。藉由堆实现的自由存储，可以说new所申请的内存区域在堆上。
堆与自由存储区还是有区别的，它们并非等价。
)
10、智能指针了解不？
我从python的内存管理角度讲了计数法析构内存，和智能指针原理一致。但我自觉诚实的说出我没用过智能指针
11、python怎么解决循环引用的？
是不是想问我智能指针的循环引用解法？我忘了呀，我就直说python本身解不了循环引用的问题（这实话实说，确实解不了，python又不是神，循环引用要靠自己析构，对python来说，循环引用的东西就算程序关了都还在），但python有个库函数可以发现循环引用位置，然后调用垃圾收集器析构掉就好（其实就是定位内存泄露，然后gc把它干掉）
12、计网了解不？计算机网络TCP和UDP的区别？
答自学。回答了很多，挺详细了
(UDP主要用于那些对高速传输和实时性有较高要求的通信或广播通信，
TCP用于在传输层有必要实现可靠性传输的情况
1、TCP面向连接（如打电话要先拨号建立连接）;UDP是无连接的，即发送数据之前不需要建立连接
2、TCP提供可靠的服务。也就是说，通过TCP连接传送的数据，无差错，不丢失，不重复，且按序到达;UDP尽最大努力交付，即不保证可靠交付
3、TCP面向字节流，实际上是TCP把数据看成一连串无结构的字节流;UDP是面向报文的；UDP没有拥塞控制，因此网络出现拥塞不会使源主机的发送速率降低（对实时应用很有用，如IP电话，实时视频会议等）
4、每一条TCP连接只能是点到点的;UDP支持一对一，一对多，多对一和多对多的交互通信
5、TCP首部开销20字节;UDP的首部开销小，只有8个字节
这里建议不是特别熟的回答首部设置不一样，别说的太详细。
6、TCP的逻辑通信信道是全双工的可靠信道，UDP则是不可靠信道
)
13、长传输和短传输？
不知道
(是http的长连接和短连接吗？HTTP1.1规定了默认保持长连接（HTTP），数据传输完成了保持TCP连接不断开（不发RST包、不四次握手），等待在同域名下继续用这个通道传输数据；相反的就是短连接。)
14、操作系统呢？
回答自己看的深入理解计算机系统，看的很详细，收获了特别多
15、进程和线程？
程序不过一段文本，运行起来才是进程，一顿讲，资源/调度单位啊、共享内存啊、并发啊XXXXXX
二、先来的简单的，构造顺序和析构顺序。
先父后子，先子后父。然后说这也太简单了。。
三、虚函数，构造函数可以虚函数吗？
不可以会构造错误。然后面试官质疑后回答了正确答案，构造函数构造后才有虚函数，所以构造函数不可以虚函数。
(构造函数不是虚函数是规定，构造函数之前，没有实例化，没有内存空间，就没有虚函数表，构造函数就不能是虚函数。另外如果构造函数可以是虚函数，那么子类构造时，不可能用父类的指针去调用构造函数，因为构造函数是对象创建时自动创建的。)
四、析构函数呢？为什么
析构错误，只析构基类。面试官质疑，说错，然后她说很多人答案都是这个，但这个不对。
(显然面试官说错了，通过基类的指针来销毁对象。这时候假设析构函数不是虚函数，就不能正确识别对象类型从而不能正确调用析构函数。用基类指针去析构子类，如果析构函数不是虚函数，那么只析构了基类而没有析构子类，正常析构应该是先析构子类，再析构基类，少析构了一部分）
五、类里，不用虚函数，函数隐藏怎么做的？不同参数列表的同名函数怎么实现？
答了同名隐藏，函数签名修改。
(同名隐藏是子类重定义了父类的函数，会把父类的隐藏，函数签名修改是函数重载等，在编译阶段把同名不同参的同名函数改成不同的名字)
面试官解释了析构函数为什么要是虚函数，因为虚函数只析构子类不析构基类，因为指向的是子类所以只调用了子类的析构函数。。我表示疑问，但不质疑，说自己下去看看(内心怀疑人生，真的假的，感觉学的假C++)。
这两个问题间扯了一些自己对接口重用的理解。
六、malloc过程？
讲了讲链表找空间块，然后怎么标记的找没找到，没找到析构一些合并，再找，找到返回。
面试官说还会析构无用变量，malloc这么智能？我说析构是操作系统内核做的，怎么怎么的。面试官说malloc应该没那么智能。我没做表示，并想回去再看看深入理解计算机系统。。心想应该有析构这一步吧。。不确定
(C标准库提供了malloc程序包的显示分配器，调用malloc函数从堆中分类块，返回一个指针，指向大小至少为申请size字节的内存块，由于对齐可能实际大一点，32位模型返回块地址是8的倍数，64位是16的倍数。如果失败，则返回NULL，并设置errno
我仔细翻了翻深入理解计算机基础，应该是有这一步，面试官不要乱质疑啊。。。在9.9章，隐式空闲链表一节里面，malloc沿着连接表找到一个够大的空间切成需要的块返回，free的时候回把释放的空间返回空闲链上，这时候空闲链就会产生会多连续的小碎片！然后malloc时发现没有足够大的空间，就会请求延时，一个个检查内存片段，如果有相邻的小空闲块，就将小空闲块合并一下。若是还不够大，就调用sbrk函数，向内核请求额外的堆空间，将额外的的内存转化为一个大空闲块，插入进空闲链表中，被请求的块放置在新空闲块中。
只是自动析构无用变量这一步我不能肯定一定有，就是一个变量占用空间，但无论如何我们也找不到这个变量的位置，此时这个变量会自动析构。不确定。
至于隐式分配器就是垃圾收集器)
七、上述说****的找合适大小怎么找到？
不知道怎么回答，说了从头找，上一次找，最优情况，并说实际比较复杂，但最优的情况(找合适大小)存在于理论很难实现。
(深入理解计算机系统里，说的这三种，也就是我仅会的三种，这三种的名字叫首次适配、下一次适配和最佳适配
首次适配：从头搜索空闲链表，选择第一个合适的空闲块。
优点是大的块放后面，缺点链表起始位置碎片多。
下一次适配：从上一次查询结束搜索空间链表，选择第一个合适的空闲块。
优点是运行速度块，缺点是内存利用率比首次适配低很多。
最佳适配：搜索整个链表选个最合适的，彻底搜索。
实际中用的方法接近最佳适配但不需要彻底堆搜索。)
八、智能指针用过吗？
没用过，为什么了解呢，因为和python内存管理一致才知道的。
这时候面试官补充说析构函数+虚函数为了能析构子类。。我就说嘛。。。
九、map和unordermap底层，怎么用
没用过啊真没用过，我这种老学究喜欢自己打表，不喜欢用stl。。
(map红黑树，后者哈希表。)
十、什么时候用什么map，什么时候用unordermap？
内心想什么时候用就什么时候用。说了自己的理解。
(map底层红黑树，因此是有序的(中序遍历)，依靠大小关系建树，增删改都是log(n)，缺点是占用的空间大，需要保存父节点、子节点还有颜色。unordermap底层哈希表，依靠哈希函数建表，查找可以达到O(1)，但是建表比较慢，占用空间更大
实际怎么选看场景。要求速度用哈希，要求有序用红黑树。静态数据用哈希表更好一点，动态的红黑树更有伸缩性。内存要求高，就用红黑树，时间要求高，用哈希表。)
十一、操作系统锁机制？线程安全？
开始胡言乱语。。哈哈不会，聊了聊信号量，临界区，也不知道自己在说啥，哈哈。
(锁机制就是对临界区的保护，临界区同一时刻只能被有限的线程进入临界区代码。信号量常用于多进程或线程对同一资源访问竞争的问题，是一个值，只能PV两种操作，P是信号量大于0减，为0挂起进程；V是其他进程挂起则恢复，没有挂起自增1，加相当于门上挂着一把钥匙，进来一个人开门带着钥匙进屋，出来再把钥匙挂门上。信号量常用于二元信号量，同一时刻只能进来一个。
多个线程同时操作临界资源，不出现二义性叫做线程安全，如果我们对临界操作进行了非原子操作，这是可能不安全。解决线程不安全的方法包括同步和互斥，同步就是线程占用这个临界资源，其他线程看它占着就不用这个临界资源了，是访问的合理性，互斥就是不管你进不进来，我都要尝试进一下，但是同一时刻只能有一个进入，这就是互斥
线程的互斥主要用互斥锁，也就是0/1计数器，进来一个线程互斥量就减1，解锁就是加1，为0则不可以再进入资源。
互斥量和信号量的区别在于互斥量用于线程互斥，信号量用于线程同步。互斥量对资源限制访问，无序；信号量可用于线程也可用于进程，实现资源有序范文。互斥量0/1，信号量可以0/1，也可以是自然数。互斥量对同一线程加锁和解锁，信号量A释放给B)
十二、继承的虚函数表结构
口述的稀烂，但是面试官反馈还可以
(类A有两个虚函数，那么类A虚函数表就有两个虚函数指针，表中放两个虚函数指针，类B继承于A，定义了自己的虚函数，那么B的虚函数表，除了保存B自己新定义的虚函数，另外都是继承于A的虚函数，如果B重写了A中的虚函数，那么B表里相应存的A被重写的函数指针改成B自己新写的就可以了)
一个数组找两两异或的最大值。
这道题出了三年了。。。今年又出了可惜我没看别人的面经。
字典树模板题。当时不会，有思路但不知道用什么数据结构，后来知道了字典树，其实前缀做成set集合也可以。说没思路问能不能换一道。给换了一道。
leecode有就几行代码的python版本，用的是前缀打表的方法。
正数数组找到长度为k的三段，使三段和最大。
复杂度从O(n^3)优化到了(n^2)，最后问面试官他说最优O(n)，提示了一句就知道思路了，先做前后缀长度超过k的最大和，然后中间滑窗就行了。写代码。没有一遍bug free，最后关头的连续两行出了小bug，一个边界短了1一个是滑窗初始化错了。就最后了被面试官看到了，说明面试官可以review代码的。其他都没问题。
一道题：给出AB两个数组，然后AB每次出一个数字，比较，A大于等于B，A加分，否则B加分。AB长度一样，都是奇数个，先已经知道了A的排兵布阵，问B是不是有必胜的安排策略。
一开始我直接就想到了递归或者一步一步DFS或者BFS，但是复杂度很高，思路是很简单的，就是贪心的拿分。
然后突然就顿悟了答案，就是知道了A的排兵布阵，那A的出列顺序就无所谓了，直接对A排序，把A最小的(n+1)/2个数和B最大的(n+1)/2个数一一比较即可，全小于则B胜。然后一直在说证明这样可行，用了递推和反证。最后面试官说方法对了就结束了面试。