C++后台腾讯实习面试经历
时间：2018年4月16日
岗位：C/C++后台开发（Linux）
BG：WXG
关于我：本科大三 预计2019年毕业
一面（普通技术面）
过程：递交简历 -> 手撕代码 -> 开始面试 -> 结束
耗时：about 1 hour
手撕代码：一颗二叉搜索树，找出树中的第k大节点
拿到题目之后没有任何思考，想用中序遍历然后把遍历结果放到一个容量为k的队列中（基本操作）。但是为什么顺手就写下vector？？？面试官看见我这么快下笔之后看了看我写的东西，然后提醒说不能转存。思考了不到30秒，有点慌，然后迅速冷静下来。第二个思路：利用递归中序遍历把二叉搜索树转成一个双向链表，然后遍历链表k步找到第k大节点或者返回NULL表示k无效。中途写的时候，面试官看了看我写的代码，然后问我思路，然后给他介绍了一遍。快写完的时候，他说其实我只是想考考你中序遍历，我说不能转存但是还是可以用栈的...（那我用队列有错吗...）
开始面试：
-
fork过程
Q：介绍一下fork的流程
A：从源码来看，fork就是简单的把父进程的几乎所有东西都拷贝一份，比如会复制父进程的地址空间、已打开文件描述符、命名空间啊这些之类的...然后修改一些标志让自己与父进程变得不一样
Q：栈和堆会拷贝吗
A：emmm...会
Q：在复制之前会做些什么呢
A：emmm...（思考半天，没做什么呀...）
Q：表示进程的那个结构体呢，会复制吗
A：task_struct吗？对对对，在这之前会先从slab中分配一个PCB...
FIXME：copy-on-write没有表达出来
-
fork、vfork以及clone的区别
Q：介绍一下fork、vfork还有clone的区别
A：从源码来分析，它们都用来创建linux轻量级进程的，vfork与fork的区别是，vfork共享父进程的地址空间，vfork之后父进程会让自进程先运行，因为vfork主要用于为了让子进程exec，exec之后子进程会用新程序的数据将内存重新刷一遍，这样它就有了自己的地址空间。子进程exec之后，会向父进程发送信号，这个时候父进程就可以开始运行了，如果子进程修改了父进程地址空间的话，父进程唤醒的时候就会发现自己的数据被改了，完整性丢失，所以这是不安全的。clone的话呢，它提供选项，让你自己选择每次复制哪些东西，但是它调用的还是do_fork好像...
-
僵尸进程
Q：介绍一下僵尸进程吧
A：僵尸进程就是死掉之后还没有被父进程wait的进程，它们在运行结束之后PCB这些资源还没有被释放，等待父进程wait它们获得它们的状态。如果父进程不wait的话，僵尸进程多了，未被释放的资源就很多，这个时候系统性能就会受到影响。如果父进程早死了的话，子进程就会被托管到pid为1的进程，以前是init现在是systemd好像，它会定时wait掉所有死了的子进程
Q：怎样避免僵尸进程呢
A：单独一个线程wait子进程，或者emmm...有两个信号，一个SIGCHLD、一个SIGCLD，设置这两个信号的处理方式为忽略，它们告诉内核，不关心子进程结束的状态所以当子进程终止的时候直接释放所有资源就行。它们的区别是SIGCLD在安装完信号处理函数的时候还会检查是否已经存在结束的子进程，如果有就调用信号处理函数，而SIGCHLD不会，也就是可能会丢掉已经有子进程已经结束这个事实
-
从汇编层去解释一下引用
Q：从汇编去解释一下引用
A：我们先来看看左值引用吧（画图示意），左值引用封装了一个指针，指针指向被引用的对象，每次使用这个引用就是解引用这个被封装的指针。右值引用的话，底层是将原来的对象进行了一份内存拷贝，然后封装了对这个拷贝的指针。因为是拷贝，所以实际上右值引用其实也是左值，emmm...STL里面有一个forkward函数，它的作用就是用来进行右值引用的类型恢复...
-
惊群效应，如何避免
Q：惊群效应了解吗
A：网络泛洪吗（搞错了概念）
Q：不是，比如说一个资源有效的时候会通知所有用户（其实已经把惊群效应的现象给讲出来了...）
A：我先举个例子吧，linux内核中的等待队列，等待队列中的等待节点有两种状态，一种是互斥等待，一种是非互斥等待。如果某个事件一发生，会唤醒对应的等待队列中的所有非互斥等待节点，而如果是互斥等待节点的话，可以选择唤醒所有节点，也可以选择唤醒指定个节点。Pthread线程库里面也有一个很好的例子，pthread_cond_signal与pthread_cond_broadcast，signal只通知一个信号量，而broadcast会通知所有信号量。但是有时候就绪的事件只能满足一个用户，如果选择广播的话就会通知所有用户，然后最终只有一个用户可以得到满足，其他用户还是被阻塞导致不必要的性能浪费
Q：那你如何解决惊群呢
A：...（写了一段伪代码，大致是加锁、条件判断...）
-
中断的作用
Q：中断的作用是什么
A：...（从cpu去分析的中断，什么特权级呀、中断门啊、陷阱门呀、任务门呀之类的都讲了一遍）
Q：你这是从太底层很细节的方面去分析的中断，但是我想从宏观的方面去了解一下
A：...（语塞）
Q：比如说任务调度？
A：哦，时间中断吗，如果没有时间中断的话，多任务操作系统就不能及时调度，恶意程序就可能霸占处理器，然后就把操作系统给弄死了
Q：也不一定会弄死呀，你看批处理操作系统呢
A：对对对...
-
tcp的连接关闭
Q：讲一下tcp关闭连接的过程
A：四路挥手吗，我画个图吧
Q：好
A：我用socket描述这个过程吧（讲了每一个函数操作之后的包发送情况还有状态变化，之前说被关闭方收到FIN之后会变成CLOSE_WAIT状态，他说不是，后来他发现是的...）
A：....（解释中），这个时候主动关闭方的状态变成TIME_WAIT...(被打断，开始提问下一个问题）
-
TIME_WAIT
Q：TIME_WAIT的话那你来解释一下它的作用吧
A：...（两个作用）
Q：如何避免呢
A：...（我讲了两个，socket选项和线程池）
Q：假设现在系统中有很多处于TIME_WAIT的连接，这个时候你会怎么做
A：有一个socket选项，可以进行地址重用，我们可以可重用这些处于TIME_WAIT状态的连接的地址，没有问题的
-
如果网络延迟很高，但是又没有发生丢包，利用tcp会使吞吐量下降，该如何解决呢
Q：tcp滑动窗口了解吗
A：了解（刚想开始介绍就被打断）
Q：ok，那tcp的拥塞控制呢
A：也知道
Q：好，假设现在网络延迟很高，但是又没有发生丢包，这个时候用tcp进行传输你觉得速率怎么样
A：不是很好
Q：那你会怎么解决呢
A：如果网络延迟很高，但是实际上网络没有发生丢包的话，tcp的拥塞控制可能会进行快重传使发送速率下降，你是觉得瓶颈出在快重传是吧
Q：嗯，也就是我想避免拥塞控制
A：（哇突然问题清楚了...）从应用层封装udp协议或者使用raw socket直接封装ip数据报
Q：...网络延迟还没高到要封装ip数据报的地步
-
Ddos攻击原理
Q：DDos攻击的原理介绍一下
A：emmm...listen有一个队列，处理连接请求。在收到匿名IP发过来的SYN之后，会在listen队列中存放一个记录，但是队列容量是有限的，当这样的恶意请求过多的时候，listen队列里就塞满了这些无效的连接请求，然后装不下更多的连接记录了，所以就拒绝其他请求了
Q：嗯，大致是这个意思
-
如何在共享内存上使用stl标准库
Q：假设我现在开辟了一片共享内存，然后我想在这块共享内存上使用stl库，该怎么做呢
A：假设两个进程A和B，它们使用相同的共享库，（画了一下进程的内存布局）加载器会自动的帮它们把共享库映射到共享内存呀，我们只要在链接的时候指定共享链接就行了
Q：不是，你理解错我的意思了，比如说我使用vector，我想要它的元素全部在共享内存上，就算是新添加的元素也是被分配在共享内存上
A：emmm...让我想一想...（把vector模板声明写了出来，指着vector的模板参数Alloc），我们可以重写一个allocator，把共享内存划分给它，用这些共享内存实现一个内存池，让allocator来对它进行管理
Q：重写一个allocator吗
A：对
-
数据库引擎
Q：数据库引擎了解吗
A：不是很了解
-
数据库三个重要范式
Q：数据库的三个范式你知道吗
A：第一二三范式吗
Q：对
A：...（大致介绍了一下）现在还有时间吗，要不要我给你讲个例子
Q：...（看了看时间）例子就不用了
-
网络层、数据链路层、传输层的设备有哪些
Q：数据链路层的设备有哪些
A：网桥是的，集线器...emmm集线器是物理层的，还有就不清楚了，就只知道网桥这一个
Q：网络层呢
A：路由器
Q：传输层呢
A：OSI七层模型中的传输层、会话层还有应用层在Tcp/Ip五层结构里面统归于应用层，这个时候不就只有软件了吗
Q：对呀，软件也算是一种设备呀
-
网络层、传输层协议有哪些
Q：网络层有哪些协议
A：ip、icmp、igmp就这三个主要的了，对了，还有一个rip
Q：传输层呢
A：传输层的话主要就tcp、udp两种
-
网络层、数据链路层、传输层使用的寻址地址分别是什么
Q：网络层用什么寻址
A：ip地址
Q：数据链路层呢
A：物理层是mac...emmm...不是数据链路层是mac
Q：传输层呢
A：（在纸上写下{ ip: port }）这个
Q：传输层有ip吗
A：（圈出port）那就是这个...
-
内存分配原理
Q：介绍一下内存分配原理
A：...（把堆的内存（《深入理解计算机系统》中有一章具体介绍）讲了一遍，再仔细描述了一下伙伴系统的具体实现）
-
多态的实现原理
Q：把C++多态的实现讲一下吧
A：...（从虚表表、虚函数表、虚函数表指针去具体介绍，然后介绍了构造析构过程中虚函数表指针的变化过程，然后从这些变化过程去解释语言级别的现象...）
-
AVL树、B+树、红黑树
Q：介绍一下平衡二叉树、B+树、红黑树
A：平衡二叉树每个节点的两颗子树高度相差小于2，所以也叫高度平衡树。红黑树根据黑高来实现每个节点的左右两颗子树高度相差低于2倍，虽然红黑树的平衡性没有AVL树严格，但是研究好像表明红黑树性能更好而且这个平衡度已经足够了。B+树的话不是很清楚，但是知道它在数据库里用的多，还有只有它的叶节点包含实际数据，其他节点只含有键
-
gcc选项
Q：gcc选项知道哪些
A：-O优化选项、-W加强警告...还有分阶段编译：-E预编译生成.i文件，-S预编译+编译生成.s文件，-c生成.o文件，-o指定输出文件，-l指定链接库，差不多用得多的就这些了
Q：加调试信息
A：最简单的，比如说内核调试有个pritnk...
Q：不是不是，我是说gcc在编译的时候给程序加调试信息用什么选项
A：-gstabs
Q：多线程编译呢
A：-j（现在回想起来，发现-j选项是make的选项，gcc不支持多线程编译...）
-
poll和epoll的区别
Q：poll和epoll了解吗
A：从内核源码来分析吧，诶不用介绍select吗...算了，其实select跟poll是差不多的，复用了很多代码，只是记录监听events的数据结构不一样...（先介绍了select，然后讲了一下与poll的区别）。epoll的话，在类unix系统中好像只有linux有，epoll把epoll实例创建、events增删改还有events轮询都分开了，这样的话epoll实例就可以被同一个进程中的所有线程共享。epoll跟poll一样，使用链表节点记录监听events，但是呢它有三个链表型结构（就绪链表、辅助链表、红黑树），首先想要监听的events的节点被放到红黑树里，这样可以加快events节点的访问。events就绪之后会被挂载到就绪链表里去，当epoll_wait从内核空间向用户空间写出就绪events的时候，会遍历就绪链表，同时这个时候可能还会发生新的就绪events，这个时候已就绪的events不再添加到就绪链表里去，而是使用辅助链表...
-
epoll中ET模式与LT模式的区别
Q：再讲一下epoll的ET模式和LT模式
A：在epoll_wait调用中，epoll会遍历就绪队列里的每一个events节点，然后通过文件的poll方法再次获取事件的最新状态revents，然后把该events节点从就绪链表中删除。当revents中包含我们关心的事件events的话，LT模式还会把该节点重新加入到就绪队列里，而ET模式也就是edge边界模式不会。这么做有什么影响呢，emmm...让我举个例子，假设我们监听一个管道可读，当事件就绪之后，我们只读了部分内容，还有部分内容没有读。当我们再次epoll_wait的时候，对LT模式来说，就绪队列里还有这个事件的节点，再次获取状态，对！还是可读的，所以还是不从就绪队列里删除，然后返回这个这个事件；对ET模式来说，就绪队列里没有这个事件的节点了，所以也就不会再对它进行通知了。那LT模式中的这个事件节点什么时候被删除呢，假设第一次epoll_wait的时候，我们把管道里的内容全部读完了，下次epoll_wait遍历到这个节点然后重新获取它的状态的时候，它已经不再就绪了，因为管道空了，这个时候LT模式就不会再把这个节点重新添加到就绪队列里了。
Q：LT模式和ET模式各自的应用场所
A：LT模式比较慢，但是比较安全，也就是如果真的是就绪的话它会再次通知你；而ET模式比较快，但是有可能造成事件的丢失，这就可能让程序永远阻塞。LT为了担责，降低了效率，而ET为了效率将责任推给了用户
-
最后的一分钟
Q：好了，面试就到这里了，你这两天还在**吗
A：嗯还在，接下来会有什么安排吗
Q：我马上给你安排一下复面，你应该很快就能收到消息
A：嗯，好的，谢谢
A：（从地上把包拿起放在腿上准备起身）评价一下我吧
Q：很不错
A：这么简单的吗
Q：嗯，很不错...
A：好吧...
总结（感想）：第一场面试也是第一次面试，6岁的我就不能为面试慌一次？收到面试通知叫我前往面试官房间的时候特别紧张，在电梯里大呼了好几口气。刚开始不在状态，后来马上调整了过来，总体感觉发挥地不错，问题几乎能够答得上来。面试官人也比较好，好几次提醒了我，也和面试官谈笑风生。面试题目大多来源于简历的个人技能，来源于项目很少。
二面（总监面）
过程：递交简历 -> 开始面试 -> 结束
耗时：about 20 min
开始面试：
-
开始的一分钟
Q：介绍一下你在学校期间都学过哪些东西
A：在学校期间几乎所有东西都是自学...（然后介绍了大一上学期至大三下学期都学过哪些东西做过哪些东西对什么感兴趣）
从简历上写的项目中学到了什么
-
STL allocator
Q：介绍一下allocator
A：...（从SGI STL源码入手，把第一二级分配器介绍了一遍，着重介绍了内存池的实现）
-
iterator 与 container 之间的耦合关系
Q：介绍一下迭代器与容器之间的耦合关系
A：在SGI STL中只有容器对迭代器的依赖关系，而迭代器并没有对容器的耦合关系。所以，比如说vector扩容之后，迭代器会失效，解引用这样的迭代器可能会造成非法访问。但是以前用VisualStudio使用它的C++的STL库CRT的时候，如果容器进行了扩容，然后解引用它们已失效的迭代器的时候，会引发异常。所以我猜想它们的实现里，一定是将迭代器与容器进行了关联，每次对迭代器进行操作时候，都会根据容器检验迭代器的有效性，如果无效就抛出异常。
-
Type traits的作用
Q：类型萃取有什么作用
A：...（我从STL设计里举了好几个例子来说明它的作用，但是好像说得不是很明白）
-
二叉搜索树与哈希表
Q：...（举了几个应用的例子，具体内容印象很模糊）
-
数据库索引
Q：数据库索引的作用
A：加速访问
Q：索引使用什么数据结构实现的
A：...（我听成了键是用什么实现的...然后就语塞）
Q：是用hash表实现的吗
A：...（我好像回答的是？？？这个问题在关于hash表的问题之后，脑子有点懵）
-
数据库事务
Q：数据库事务介绍一下
A：...（数据库基础不是很好，只是简单地介绍了这个操作的原子性，然后他又问我事务的实现是怎样的，我只是讲了一下个人的猜测...）
-
写一个简单的FTP服务器
Q：我现在想要写一个简单的web服务器，响应用户相应的数据，该怎么写
A：FTP服务器可以吗
Q：FTP服务器就FTP服务器吧...
A：...（手写伪代码）
Q：不用一行一行写出来
A：...（停下笔）首先创建一个服务器socket，然后bind地址，listen监听，然后把socket加入多路转接监听链表。当有连接到达的时候，我们对socket调用accept，返回一个已连接套接字描述符，然后根据用户传输过来的文件名去查找文件，读取文件内容并回送给用户（被打断）
Q：读取文件的时候服务器socket怎么办呢
A：accept之后创建一个线程，如果使用线程池的话就从池中取一个空闲线程，然后把已连接文件描述符传给这个线程，然后让线程去处理这个用户请求
Q：一个线程处理一个用户请求吗
A：对
-
设计网页访问cache数据结构
Q：假设我想要缓存web服务器的访问记录，该如何实现这个数据结构
A：用队列吧，根据last visited排序，先进先出
Q：如果你用队列的话，你怎么确定cache是否命中呢
A：emmm...你根据什么判断是否命中
Q：键
A：那我还是用队列，每一个元素包含键值两部分，值的话呢就是访问的记录。然后我再用一个红黑树保存键值，这个值呢是指向队列元素的指针
A：其实用hash表更好一点，这样更快，但是我一般都比较喜欢用红黑树...
-
最后的一分钟
Q：好了，就面到这里
A：...（我都不敢相信只面这么短的时间，当时真的很虚很虚很虚）
A：评价一下我吧
Q：啊？（面试官全程无表情很高冷，可能被我这个问题惊呆了...）
A：评价一下我
Q：本科有这个基础已经够了，但是还是有一些不足
A：数据库和网络吗
Q：你的数据库基础不是很好
A：好的，谢谢，接下来还会有什么安排吗
Q：你回去等通知吧，我尽快让HR联系你，明天应该就行，最迟也就这一两天
总结（感想）：等叫号就超出预期时间50多分钟，被叫号以后来到面试官房间，那时还有一个女生在面没有出来。当时我以为是两个人面我，然后我敲门，他让我等一下。在门外听见他们一直在讨论数据结构与算法的问题...当时很慌，虽然不是很怕，但是在这种让人紧张的环境下迅速把算法题做出来还是有些担心。下午整体感觉不是很难，但是氛围不是很好，因为面试官散发出一种吊炸天的气质让我很怂，而且我每说一句话他就嗯一大声（有时候让我特别尬），而上午那场是偶尔ok一下...以为二面会手撕很多算法，结果并没有，虚惊一场。最后他说就面到这里的时候真的很有被吓到，因为时间真的太短太短了吧...心想不会就这么凉了吧。然后主动问他要的评价也说我渣，以及“你回去等通知吧”，种种都让我很怂。面试状态当晚0点还是没有更新，直到凌晨三点起床才发现状态变成了HR面...面试题目全部来源于简历的个人技能以及项目经历。
三面（HR面）
17号凌晨3点起床写下的一二面面经，中午12点还在赖床然后接到HR电话通知14点前往酒店参加面试。那天心情状态都不好还很困，下午hr面试的时候，hr小姐姐问什么就顺口回答什么，没有任何经过大脑思考，然后从话语出暴露出很多破绽，甚至还表现出了一些不存在的阴暗面和缺点。问的内容大致是学习方法、社交、未来规划、学历、为什么不考研、为什么来微信事业群（志愿填的是WXG、深圳－不服从调剂）...其实hr也会问项目的...而且她会仔细检查简历比如说有没有错别字、项目时间科不科学等等等等...看别人的hr都有问户籍啊有没有女朋友之类的，可是为什么不问问我有没有女朋友？？？（其实我早就心知肚明只是不愿说透，她看我本人这么帅怎么可能会没有女朋友嘛（害羞...）...其实我真的没有女朋友啊...）
总结（感想）：遭遇hr压力面，以为自己铁定会挂，并且面试状态持续两天都处在“hr面试中”，后来我主动问hr什么时候状态才可能会更新，跟她说自己可能要凉凉，然后她反问我为什么觉得自己会挂，然后让我去看状态...以为最新状态会是“不适合该岗位”的，看了之后是“已完成所有面试”，真是巨开心！
4月24日更新
4月23日上午10点半，收到offer call，下午5点半收到录用函...
