准备过程

期间算法看了《算法导论》的动态规划、贪心算法章节，包括如何计算时间复杂度、空间复杂度，穿插着看了一些动态规划的背包题；

看了《算法》里的所有排序算法并写了代码、查找算法；

然后看C++，以前看过《STL源码剖析》，然后自己看了几个网站总结了C++标准库（就是所有头文件下面各有哪些类，有啥注意点，大概看了有些示例代码），然后《C++ Primer》必看；结合牛客网面经汇总里的C++面经汇总，查漏补缺，有些书里没提到的就找博客看，然后总结成自己的回答；

在面了一家小公司之后，查漏补缺，又准备了很多多线程、多进程方向的东西；设计模式整理了一个自己的回答套路；

面经

小公司（凉）

笔试：

15道C基础，一道阅读理解（5题好像）；笔试记得要求都要有一定正确率才能过；错了一道C基础；主要是指针、if else匹配、与或非等这种基础题；

机试：

使用两个进程（不能简单fork），然后用一种IPC（进程通信）方式，一个进程获取数据，另一个进程拿到数据处理并输出结果；需要处理的数据为：

问：5张扑克牌（A~10），每个扑克牌最多出现2次（一对），一对比一张要大，要求进行排序；

答：使用int flag[11]存储出现的扑克牌，出现1次的直接打印，出现2次的push到vector中；

问：5张牌使用11个int，空间效率太差，有什么方法优化么？

面试：

自我介绍

用过哪些设计模式（答单例，问怎么实现的）

智能指针如何实现；

都有哪些排序算法（答：冒泡、插入、快排、希尔排。。。 问：快排如何实现的）

多态的虚函数是怎么实现多态的，详细描述下使用过程（具体是怎么调到虚函数的）每个对象都有自己的一份虚函数表么（答是的，其实不是，是每个对象都有自己的虚函数表指针）

虚析构函数的作用

C++11新特性

你们这个项目如何实现高并发；

线程间同步都有哪些锁；

京东（凉）

先是简单的电话面试（十几分钟）：自我介绍，项目，epoll的ET和LT的差别

现场面一面：手撕算法

1.简单实现strstr（双重循环，不用KMP）

2.在map中做删除value（注意iterator失效问题）

3.单向链表的反转（双指针）

现场面二面：

自我介绍，聊项目（主要想问分布式相关的经验，但是没有这方面经验。。。）

撮合是单进程的么？ 挂了怎么办？（备机。。。）

如果服务端挂了，使得连接断了，怎么恢复从而客户无感知？（不知道。。。）

数据库如果挂了怎么办（备机。。。）

有什么要问我的么？

结果一到两周会通知（凉凉）

华为（offer）

算法机试使用牛客网，电脑需要开视频（电脑屏幕也会被监控）、手机需要扫描二维码然后维持考试画面，预防作弊；

六轮面试；一面二面是晚上7点~9点，进行线上面试；

一轮机试算法：

两个排序题（一个是两个数组合排序，一个是三个数组合排序，写一个class然后重写operator<就行）

一个纸牌分析题；五张牌，每个牌有花色，分析这五张牌是同花顺还是4张带一对还是啥；A2345也是一个顺子；（设计一个map存储牌和index，循环遍历牌和花色，统计是否有四张、三张和顺子，注意顺子的A2345处理）

一轮心理测试：

网上找了一个什么是好的性格什么是不好的性格大概看了下；然后结合自己特点写；

两轮基础+项目+算法：

一面：

自我介绍；

问：堆和栈区别；

问：c++和C差别；

问：多态；

算法：删除链表中重复节点；(需要用IDE编写并调试出结果)

二面：

问：进程和线程有什么区别

问：堆和栈有什么区别

问：用到哪些设计模式（SOLIDE具体的一一对应）；知道生产者消费者模式么？

问：项目相关的内容

问：安全编程：知道缓冲区溢出漏洞吗？

答：只知道内存写溢出，然后网络安全方面会有利用这个漏洞然后来攻击的；

算法：股票买卖问题；仅买卖一次；求最大收益；//面试官说可以用贪心算法，但是这个应该不行吧。。。 不是买卖多次的问题；

商汤（offer）

问：给定一个n，给出0~n过程中2出现的次数// 比如13，则0/1/2/3..../12 一共出现了两个2，所以结果是2；

答：假设一共有n位，每一位的数字分别为num_n;则num_n上出现2的次数为f(n)。。。。。

问：给出前序遍历和中序遍历，输出后序遍历；

用后序遍历：（用中序遍历确定前序遍历的左子树和右子树范围）

map in_map; 存储中序遍历每个字符的下标便于后面查找

问：由3、5、7的乘积组成的数，求第k个大的值； 3/5/7/9(33)/15(35)

将3、5、7存入set，循环k，每次从set中取出一位，然后3、5、*7再存入set；

2.一面：

讲下三道算法题思路

C++基础

3.二面：

C++基础：

空class有哪些构造函数（默认构造、拷贝构造、赋值构造、移动构造、移动赋值构造、析构。。。）；

多态：静态多态、动态多态（虚函数，如何实现）

三次握手四次挥手，time_wait，2MSL

什么情况下需要在构造函数中做特殊处理：1.会有一些堆分配的内容  2.const、包含其他类需要构造 //堆分配、const、包含其他类需要调用构造函数的、（const什么时候初始化—）初始化列表）

构造和析构的顺序：父类的构造、包含其他类，其他类的构造；

线程同步、线程的生产者消费者模式实现（A完成了通知B，B完成了C再接着做这种协作模式）：

算法题：两个有序链表合并；单链表查找倒数第k个节点；（时间复杂度是多少）

多线程：实现单链表的插入和get，线程安全（不仅是atomic，还有atomic_flag、）；

auto和decltype的区别；

多态情况下，父类指针指向子类对象，怎么用这个父类指针调用到父类的对应虚函数？

在main函数之前会执行哪些操作；

lambda表达式[=]中间的等号是什么意思；

linux的软连接和硬链接；

4.三面：

问下为什么想换工作；工作过程中会和哪些人有接触；项目；

5.hr面：

问下为什么想换工作；对公司的了解；手上有其他offer嘛；对岗位的期望；

项目组有多少人，工作内容怎么分配；

6.加一个交叉面（牛客线上面， 算法工程师；结果实际改为了电话面；问的比较底层，很多都答不上来，但是面试官有很好的做引导，聊得比较轻松；下面记录的回答可能很多不对，仅做问题参考）

问：自我介绍

问：STL中提供的容器vector，这个allocator是做什么用的，跟系统自动分配相比有什么好处；

答：系统可能本身只是做简单的分配；但是自己提供的话可以在里面做一些额外的定制的操作

问：假设一个class A; A *p = new A; free(A);这里不用delete，而是用new，可能会发生什么情况

答：由于free并不会去调用析构函数，因此析构函数中做的一些额外操作，比如指针指向的堆里分配的内存，就无法释放（还有继承中父类的析构、包含其他类的其他类的析构也不会调到）

考官答：除了上面的，还有new中不一定能调用的是malloc分配的内存；（尤其是某些debug的版本），因此直接使用free可能会有问题； 另外new返回的指针不一定就是malloc的指针，比如new出来的对象的大小是3，编译器做对齐，可能会将指针往后移动一位，返回之后的那个位置；（C++11 新引入操作符alignof， 对齐描述符alignas，基本对齐值 alignof(std::max_align_t)）

问：string里面的traits是用来干嘛的

答：之前看过STL源码剖析，traits用来萃取特性，比如萃取iterator的类型，具体的没用过//这里并没有回答出来

问：c++中static有哪些用途

答：用于变量和函数；用于函数外的变量和函数，改变它的external/internal属性；用于函数里的变量，延长它的生命周期；用于类的成员变量和成员函数，变成静态的成员变量和成员函数；

追问：上面说到用于函数外的变量，改变external、internal属性，这个具体编译器如何实现，比如一个文件中有一个external的变量，还有一个internal的变量，别的文件怎么知道用的是哪个？

追答：猜测，c++中有namespace，可能是external的话在一个全局的namespace中，每个文件有每个文件的一个namespace，如果是internal的话，就放在文件中的namespace下； 其他文件访问的时候，如果不带namespace，就直接去全局的namespace下找到这个符号

面试官追答：也可以这么用；实际上是给这些符号加一些限制名称；

追问：类的普通成员函数和static成员函数有什么区别；普通成员函数是一个对象有一份的嘛？

追答：实际上普通成员函数和static成员函数，代码是都只存储一份的；普通成员函数在代码段中存一份，static成员函数在静态区存一份；差别只不过在于static成员函数没有this指针，而普通成员函数有this指针

追问：所以普通成员函数是多个对象公有一份是嘛（这里我感觉有坑，所以普通成员函数到底是怎么存储，怎么调用的？？？）

追答：是；

问：假设有个程序员，写了一个算法，能将一张普通图片转为艺术照片，现在写了一个循环来测试这个算法性能；读取一张图片，然后循环调用算法；假设现在算法前面几次执行的时间由长到短，可能的原因是什么：

答：调用的时候会存储一些中间计算的结果，后面可以直接拿来用； cpu底层的寄存器会存储一些使用频率较高的数据，后续使用的时候用时就比较短；

问：还有其他可能嘛？

答：不知道了

问：看到你有做c++封装为python，python是有垃圾回收机制的，因为python里存的都是引用，那你做的这个垃圾回收情况？？？

答：我们封装的接口是提供create和release的

追问：c里面会经常有这种create_handle，free_handle的情况，就是把它当做c++的new和delete的，现在假设用C实现一个stack，提供create_stack，push，get等，但是不提供release，客户在外面直接调用free(stac k)，可能会有什么问题？

追答：一个是多线程的一个同步问题，假设缓存用完了，这个时候需要开辟更多的内存，然后做一个数据迁移，如果再迁移过程中客户调用了free，就会导致出问题

追问：还有其他情况么？

银联数据（凉）