微信又改版了，为了方便第一时间看到我的推送，请按照下列操作，设置“置顶”：点击上方蓝色字体“程序员乔戈里”-点击右上角“…”-点击“设为星标”。加星标不迷路!

文中集合了BAT三位大佬的面试干货分享，可谓干货满满，另外公众号后台回复C面经，可获取三位大佬求职面试期间整理的pdf和word面经。

Linux后台CPP学习之路 & 面经知识点收录

面经知识点收录

CPP

• extern "C"的作用：可以把程序编译成汇编文件，然后从汇编代码去看它的作用

• C/CPP const关键字：再了解一下CPP字符串常量以及普通const常量的内存布局，还有与volatile一起使用的效果，然后可以看出C里的const与CPP里的const还是有一定差别的…

• C/CPP static关键字：了解一下ELF（参见《深入理解计算机系统》第七章：链接），然后从符号表的角度去分析static关键字的作用，注意：CPP不像python等解释性语言，它不会执行类定义的代码，所以类的静态数据成员必须在类外定义（除了静态常量），这个时候static的作用跟普通的static语义不同…还有，static函数在单例模式中有一个应用（参见《Effective CPP》条款4：确定对象被使用前已先被初始化）

• C/CPP volatile关键字：在底层代码中用得多（之前调试linux文件系统的时候，想要获得一个file_struct对象指针，然后这个指针总是被优化掉，不清楚是不是跟volatile有关…）

• C/CPP restrict关键字：在函数库接口中用得多

• C/CPP内存分配管理：CPP中的new只是对malloc进行了一层封装，malloc的具体实现可以看glibc的malloc源码，然后调用system call，最终会接触操作系统的内存管理模块，所以最终还是需要了解操作系统的堆管理（简单堆管理参阅《深入理解计算机系统》第九章：虚拟存储器，linux中内存管理具体实现可以阅读linux源码），需要特别了解内存池的实现（可以阅读sgi stl源码）还有伙伴系统与slab…

• CPP反射：工厂模式以及CPP17了解一下

• CPP异常机制：网上有很多讲CPP异常机制的博客

• CPP智能指针：可以按照接口要求自己实现一下四个简单的智能指针，其中share_ptr里的析构器其实是一个仿函数，然后可以自己想办法去实现一下function，any之类的模板类

• CPP四种类型转换：
  http://www.cplusplus.com/doc/tutorial/typecasting

• CPP string实现原理：其实实现与vector差不多，具体实现参阅sgi stl源码

• CPP map、set实现原理：封装了一颗红黑树，红黑树重要的就是旋转，还有平衡度（根据黑高证明）,具体实现参阅sgi stl源码

• CPP函数重载、覆盖、隐藏：重载可以从汇编代码去看（根据参数类型去重命名函数名），覆盖可以去从虚函数表去分析，隐藏可以从作用域去理解

• CPP编译时多态与运行时多态：类的多态（运行时多态）一定要看看《深度探索CPP对象模型》这本书，stack overflow上有一个帖子深度讨论了类的多态、虚继承这些，讲到了构造析构过程中vptr的变化，然后可以自己去适当理解为什么虚函数的具体调用依赖于构造析构的当前进度（链接：
  https://stackoverflow.com/questions/6258559/what-is-the-vtt-for-a-class）。注意，函数模板不能局部特例化，不然就是模板重载，不得不多说一句，函数模板实例化后的函数与普通函数不在同一命名空间中（不是CPP语言支持的namespace，是编译器所用的命名空间），所以能够出现具有相同名字相同参数类型的函数，实际上，从汇编代码去看，其实最终的名字还是不同的

• CPP为什么构造函数不能设置为虚函数：vptr还没有被设置，会出现先有鸡还是先有蛋的矛盾

• new/delete和 malloc/free的区别：《Effective CPP》定制new和delete（条款49～52）了解一下

• 如何实现只能动态分配类对象，不能静态分配：只是要求不能在栈上分配，必须在堆上分配

• 动态链接库与静态链接库的区别

设计模式

• 单例模式（static函数可以实现）

• 策略模式（举例：share_ptr的析构器）

• 简单工厂、工厂方法、抽象工厂模式

• 装饰模式（闭包：CPP lambda、Python decorator了解一下）

• 代理模式（举例：iterator有点代理模式的意思）

• 原型模式（举例：实现boost库中的any时需要用到的clone方法）

• 模板方法模式（《Effective CPP》条款35：考虑virtual函数以外的其他选择 有介绍，但是举的例子感觉不是很好，感觉最大的突出点是事前和事后，之后看了《大话设计模式》对模板方法的介绍，感觉它的最大特点应该是实现最大化代码复用）

• 适配器模式（举例：STL中的容器适配器）

• 迭代器模式（举例：iterator）

数据库

• 数据库基本操作：可能还会要求通过sql语句对数据库进行调优

• 数据库索引：索引数据结构的实现，如何设置索引、以及复合索引内部的顺序（比如说，假设有一个复合主键包含A、B两列，索引AB与索引BA对数据库的影响）

• 数据库事务：底层如何实现事务

• 数据库引擎

• 数据库存储过程

• 数据库的第一二三范式

• delete、truncate、drop的区别及应用场所

计算机网络

• HTTP状态码

• 流量控制

• 拥塞控制：高延迟拥塞控制会降低tcp传输效率，这个时候需要自己实现拥塞控制或者避免拥塞控制，所以需要封装udp或者ip数据报（如果需要重写拥塞控制算法，可以了解一下BBR算法）

• TCP连接的建立与终止：从tcp三次握手可以引入Ddos攻击

• TIME_WAIT：作用以及如何避免

• Ddos攻击原理：listen队列

• 长肥管道

• 7/5层模型协议、设备

• 简单ftp服务器socket编程：注意尽量使用一个请求一个线程/进程模型

算法

一定要把《剑指offer》刷到滚瓜烂熟，里面的算法最好能全部手写出来，一般面试的手撕算法几乎都来源于这本书

• 大数据处理：大数据top 100啊之类的问题很常见

• 大整数计算：转为字符串计算或者很强的可以自己用位运算实现一下…

• 如何设计好的散列函数

• 动态规划：了解一下动态规划基本概念以及有哪些常见算法

• 贪心算法：了解一下贪心算法基本概念以及有哪些常见算法

• 排序算法：快速排序、堆排序、归并排序、插值排序、冒泡排序、选择排序、计数排序（了解一下）、基数排序（了解一下），除了两个需要了解的，其他六个都需要快速写出来，而且知道它们的平均、最坏时间、空间复杂度

• 搜索算法：折半查找（一定要能快速写出来，还有其变种），二叉树查找，hash查找

• 数据结构-堆

• 数据结构-链表：数据结构-跳表、算法：二叉搜索树转为双向链表、链表回环、反转、复杂链表的复制…

• 数据结构-树：数据结构-AVL树、红黑树、B 树，算法：二叉树的前中后序遍历，还有《剑指offer》上的树算法

• 数据结构-图：dfs、bfs、dijkstra、floyd、prim、kruskal都要能够写出来

• 字符串算法：kmp、boyer-moore都要能够写出来、正则算法了解一下

• 手撕算法：手撕算法的代码量一般都不是很大，所以应该去权衡一下什么算法更容易被考到什么不容易被考到。除了《剑指offer》，还有很多跟程序鲁棒性和性能有关的手撕代码题：strcpy，实现单例模式…，还有一些题来源于leetcode，但是几乎都是easy或者medium程度的题

操作系统/Linux 内核

• 中断：介绍中断的作用，要是再能从硬件、汇编级别去介绍一下中断会发生什么就更棒了

• 信号：几乎所有讲操作系统的书都有介绍信号，linux信号参阅《Unix环境高级编程》第10章：信号，以及《深入理解linux内核》第11章：信号，需要了解可靠信号与不可靠信号的区别，还需要特别了解SIGCHLD、SIGCLD信号

• 进程与线程：轻量级进程、系统级线程、用户级线程、进程，这些可以读linux内核源码以及一些资料很容易理解，协程（Python中yield的效果以及它的具体实现（C源码）了解一下），可以去网上找找CPP的协程库去读一读

• linux常见的调度算法：知道这些算法的思想就行，读个linux源码就更棒

• linux文件系统：《深入理解linux内核》第12章：虚拟文件系统 以及 第18章：Ext2和Ext3文件系统 以及 第16章：访问文件，可以让你深入了解linux文件系统

• linux IPC：System V、Posix IPC熟悉一下，可以参阅《Unix环境高级编程 进程间通信》，以及清楚它们的作用与优缺点，当然还是推荐去阅读一下IPC的linux内核源码

• 如何实现linux的高并发，线程池的思想：github上有好多好多线程库，抓一个下来自己读一读，代码量不是很大，很推荐自己动手写一写

• 死锁产生的四个必要条件及如何预防

• 编写linux的并发测试程序：生产者消费者并发程序要求能够写得出来

• 惊群效应：举例子讲一下惊群现象，然后去了解一下如何避免。内核中存在两个惊群的例子，accept惊群与epoll惊群，linux内核经过改进避免了一些惊群，可以从内核源码去解释一下它是怎么做的

• fork、vfork、clone的区别：这个真的只能读源码才能深入了解了，注意，phtread线程库就是使用的clone

• 僵尸进程：清楚一下概念以及它的危害，然后知道如何去避免僵尸进程

• select、poll、epoll的区别：从内核源码去分析，select与poll实现差不多，读了一个源码差不多很快就能读懂第二个，epoll设计很独特也很有意思，赶快去读一读

• linux内核伙伴系统、slab缓存（实现原理、与普通内存分配的区别以及优势）：简单介绍参阅《深入理解linux内核》第8章：内存管理，深入了解就去读linux内核源码…

学习方法

收到好几条私信评论，问我学习方法，知道自己很菜，虽然有时候会盲目自信，但是跟一些大牛比起来还是会深深感到自卑…没了解学习过一个领域，看到别人在这方面有见解，然后就会觉得别人特别牛，可是一旦了解，就会发现并没有想象中的那么厉害，所以说我真的很菜的（并没有装逼，是真心话）…

适合一个人的学习方法，不一定适合另一个人，所以在这发表的见解，大家取其精华去其糟粕…

有好几个非cs专业的同学问我学习方法，那么先贴一个链接：http://study.163.com/curricula/cs/grade-1.htm，这里有cs专业大一到大四开的所有课程，可能这里有些课程质量不是很好，但是还是可以了解一下具体开过哪些课，然后自己去找教程去认真学习。这些课程中开的数据结构课感觉还不错，可以去认真看看…

看到好几个同学说，问别人学习方法都是推荐了一大堆书，哪看的完…其实很多东西只有看书才能看得明白的也能看得更透彻，我几乎都是看书看源码，遇到一些很难的就google或者找视频看…因为如果所有东西都看别人讲（google看博客或者看视频），就可能遇到一个知识点不同的人不同的看法，然后自己就弄弄不明白还会被带歪然后就心情爆炸…所以我还是会推荐大家看书或者看源码，但是会讲重点哪些地方应该看哪些地方简单了解一下，这样对大家的时间还是能省一点的…

大家一定要有明确的目标，知道自己该学些什么又有哪些东西学了对主线没有帮助的，目的明确一点真的很重要，我明知我是linux后台CPP，以前还花了很长时间去学习windows下的编程，虽然学习了一点东西，但是对我的发展并没有多大帮助而且真的很浪费时间，因为我把它当成主线来认真学习了…就算是这样，以后还是接触linux，windows用得少了也很快就会忘记，所以希望大家能好好权衡…

我很强调动手以及发散思维，发散思维比如说学到一个东西能很快联想到之前学过的另一个东西，以及遇到新的东西希望能够从更底层去猜测它的实现，要是等以后再接触到它的实现的时候，可以将具体实现与之前自己的猜测进行比较…动手是真的巨重要，我讨厌伸手党，也讨厌纸上谈兵，遇到问题我会尽量去用代码或者实现源码去解决问题，有时候跟踪程序的具体过程可能还要反汇编，有时候遇到很难很难的调试问题，比如说之前调试linux文件系统，我真的花了巨长巨长的时间，这个时候需要很强的耐心还有明确的目的，因为有时候调试着调试着突然忘记了自己想要干吗…

我从很早开始使用linux作为自己的日常工作环境，为了学习《Unix环境高级编程》，我几乎尝试了所有linux发行版还有其他unix系统（这些作为虚拟机部署），部署其实也是一件很有趣的事，也能让你更加深入的了解类unix系统…推荐大家使用linux作为自己的学习环境，而且还能克制自己玩大部分游戏…

ok，开始吧…

CPP语言

在学习CPP之前，我只有C基础。我是啃《CPP Primer》这本书，当时是第五版，那个时候最新的还是CPP11标准，也推荐大家看这本书，因为CPP14、17都还是太新，用的很少，而且大多公司也才从CPP98过渡到CPP11。这本书我读了很多遍，重点是STL与类，模板编程与OO几乎都占了CPP的半壁江山。关于CPP面向对象，读《CPP Primer》这本书关于类的讲解还有《深度探索CPP对象模型》，然后这部分内容就差不多了。把细节列出来吧：拷贝控制（默认构造、值构造、拷贝构造、移动构造、拷贝复制、移动复制、析构）这些需要很熟练很熟练的了解，这其中初值列与隐含的析构列很重要，对象模型（简单继承、含有虚函数的继承、含有虚基类的继承）它们的内存布局需要很清楚的知道，还有看上面那个stack overflow的帖子…命名返回值优化顺便了解一下（见《深度探索CPP对象模型》），然后就能理解为什么有时候类实例的创建没有按照正确流程…模板编程首先我推荐一定要把SGI STL库源码阅读一遍，就算源码没有看过，STL还是得会熟练的使用，重点在set/map、string/vector，要是能自己写一写就最好了，很喜欢侯捷先生的两句话：“源码之下，了无秘密”，“天下大事，必作于细”。内存分配器、几个容器、几个容器适配器、几个范型算法，代码量大约在1~2w行左右，然后可以自己再实现更多的东西，例如可以再实现一些boost库中的东西、四个智能指针、any、tuple之类的，然后能真正让你体会到模板元编程的乐趣…模板编程几个重要细节列出来：函数模板--显式实例化、特例化，类模板--显式实例化、全特化、局部特例化，模板容易出现的问题见《Effective CPP》条款43：学习处理模板化基类内的名称以及条款46：需要类型转换时请为模板定义非成员函数，可能会帮到你。还有一个很容易出现的问题应该就是关于模板的链接错误了（提示没有找到指定的函数），其实就是没有模板实例化，具体问题去google…CPP11还有很多特性，右值呀、lambda呀、function呀，RTTI呀…右值可以从汇编角度去看；lambda也可以从汇编角度去看，lambda其实就是个闭包，在CPP中lambda没有一个具体的类型，将一个捕获列表与一个函数捆绑在了一起，所以从汇编去看的话，返回一个lambda其实就是返回捕获列表中捕获的数据；function运用了类型擦除，具体实现可以google，其实boost库中的any也用了类型擦除，RTTI的话其实读完《深度探索CPP对象模型》，从虚函数表中应该已经知道了它的原理；还有一些高级部分：类型萃取呀、tuple呀这些…，类型萃取读完SGI STL源码之后应该已经能够深刻的理解了，tuple的话就是用了模板递归这些嘛，一些模板元编程…书籍推荐：《CPP Primer》、《深度探索CPP对象模型》、《STL源码剖析》、《CPP标准程序库》（参阅）、《Boost程序库完全开发指南》（简单读一读）、《Effective CPP》（想要更好的学习CPP强烈推荐）、《More Effective Modern CPP》（让你更好的了解CPP11，但是这本书目前还没有中文版，但是感兴趣的同学可以啃一啃…）

设计模式

推荐阅读《大话设计模式》，提醒一下，设计模式面试考得不多，但是想要了解的话还是去看一看…其中好几个设计模式可以联系已学过的东西加深印象，学习设计模式最好最快的办法就是理解它的UML图…

数据库

我的数据库不是很好，快速、基本地学习数据库推荐阅读《Sql必知必会》（很薄的一本书）

计算机网络

《Tcp/ip详解》（卷一）了解一下，看上面收录的面试知识点，着重去学习重要的那些。详细介绍tcp可以阅读《计算机网络》（谢希仁）（对也就是大多学校发的那本教材）第7章：运输层，其中的tcp可靠传输相关的一定要认真认真读！！，列出细节吧：滑动窗口、拥塞控制、还有状态图、还有TIME_WAIT（重中之重），socket编程可以阅读《Unix网络编程 套接字联网API》，其中跟SCTP相关的可以忽略掉，其实再省略一点的话只读第一二部分就行了…

算法

上面收录的面试知识点基本已经全部讲了，也就是面试的时候所有数据结构与算法都可能会考到。我算法还是有点薄弱，因为花了太多的时间去学习专业课然后没有太多的时间去刷题，但是强烈建议大家多去刷刷题，ACM尽量参加，含金量特别特别高。leetcode、牛客算法都该做做，尤其是牛客上关于《剑指offer》的专题一定要全部刷到滚瓜烂熟…刚刷算法可能会很困难，但是坚持去做，做完去看看题解还是会很有进步的。上面我还给了网易云课堂的链接，里面有开数据结构的课，学习基础可以去看看…推荐书籍《Algorithms 4th Edition》（英文版，所以可能有点难读，英语不是很好的话就参阅），《算法导论》

操作系统

还是上面给的网易云课堂链接，里面有一门操作系统的课，简单学习的话可以去看看。

linux内核

先简单读一遍《Linux内核设计与实现》，偶尔可对照一下linux内核源码。但是呢，这本书其中感觉有很多错误，不是很严谨，所以不推荐作为深入学习linux内核的书籍，只是作为简单的入门。深入学习linux内核的话，可以认真读linux内核源码然后对照《深入理解linux内核》这本书，当然，重点还是读源码…读了《Linux内核设计与实现》之后已经有了基础了，然后其实已经可以有能力自己读懂源码了…可能会觉得还是有困难，讲一下我的linux入门之路吧…我先读了一遍《Linux内核设计与实现》，当时对照着源码读的，当然啦，书上不可能所有东西都讲，只是挑一些特别重要的讲，其他的还是需要自己去看去理解…读完这本书之后，大致的内存管理、进程控制之类的还是了解了，我真正入门是在读多路复用select、poll、epoll源码的时候，这三个函数源码真的很简单，读懂之后能很有效地增强自信心，然后就觉得很有趣，然后就开始了真正的linux学习之路。之后慢慢地linux文件系统、内存管理、IPC之类的都能看懂，不懂google，看博客，然后继续读…linux内核源码其实并没有特别难学习，难的是不知道怎么入门…这里有奥特曼的epoll源码总结：https://www.nowcoder.com/discuss/26226，之后要是有时间我再把我对do_fork、select、poll、epoll、ipc、文件系统、内存管理、大多数系统调用、进程调度呀之类的源码总结贴出来…

汇编

对了，走CPP后台这条路，就是需要与底层进行接触，所以了解汇编是必不可少的。尽早学会汇编，对以后学习任何高级语言、操作系统都会很有帮助。推荐阅读《汇编语言》（王爽），《X86汇编语言 从实模式到保护模式》，《汇编语言程序设计》（简单阅读一下，了解AT&T汇编格式）

帖子内容没用md把格式做好，所以将就读一读吧…虽然很菜，但是还是希望上面的总结能够帮助到大家…有什么学习相关的问题可以私信我或者给我评论….

C++技能树

图片出处（需要的可以后台回复 C面经）：

https://www.nowcoder.com/discuss/103228?type=1&order=4&pos=4&page=2

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什么时候状态才可能会更新，跟她说自己可能要凉凉，然后她反问我为什么觉得自己会挂，然后让我去看状态…以为最新状态会是“不适合该岗位”的，看了之后是“已完成所有面试”，真是巨开心！