面经

4月份才开始真正的投简历、找实习，就有点晚了。有些公司的网申都快截止了才投。这个时候有点着急了，所以我是看到c++关键字就投了简历。

腾讯 后台开发 （第一次正式面试）

第一次投递，还没来的及看面经看看都有什么题目就受到了面试邀请。因为时间冲突我申请了延后一天，不知道为什么当天下午就直接来了电话面试。

一面 （挂了）

c++

1. 虚函数

   大概把虚函数表，有继承的情况，继承多个父类部分有虚函数的情况简单说了一下

2. STL

   1. set和map底层实现

      使用自平衡二叉树

   2. 确定是平衡二叉树吗

      感觉是吧, 我没有太过仔细看里面的实现(实在是太紧张了, 脑子空白, 当时就凭着记忆回忆了数据结构学的所有的树, 回答了我觉得最合理的一棵树. 后面回想可能是面试官希望听到具体的红黑树而不是泛泛的平衡二叉树)

   3. 你是没有了解过STL的实现吗?(察觉到我没有准备或者很菜, 有点不开心了)

      不好意思, 我平时这边可能欠缺注意.

   4. 那要是你实现一个链表你会怎么实现?

      用双向链表吧, 牺牲一点空间换一点性能吧

3. 看过的书

   没仔细看过c++的技术书，看的一般是应用类的。

网络

1. tcp三次握手4次挥手 4次挥手的最后一次客户端发送（ACK=1）之后等待2个最长报文时间描述错了。 面试官问我确认吗？我回答：刚学计网这边有点记错了

反思

确实是我自己的问题, 我没有做好准备就开始浪费他们的时间. 痛定思痛, 专心准备几天

字节 系统工程 (第二次面试)

初生牛犊不怕虎, 投了一个不知道的岗位. 因为其他位置要求了一些很具体的要求, 我没有达到. 只剩下这个相对吻合.

一面（挂了）

项目

一开始简单讲了一下项目，觉得没有特别之处，就开始问基础知识了

体系结构

1. struct 关键字的size判断 看机器, 和字节对齐要求.比如我的是64位机器那么int long 是32位.
2. 64位机器, long 是32位吗? 我记得是这样的, c语言的这些保留字混乱, 在int, long, long在平台不一定, long long 一定是最长的. 我记得我试的时候在我的平台和编译器上是32位.
3. 那你的机器是32位的吧. 那你说这个对齐. 为啥要这么对齐, 以8位对齐和3、5对齐有什么区别呢? 8位对齐的话位便宜的最小单位是8, 同样3、5对齐就是3和5. 8位的话对于常用的指针和int等类型来说浪费较大. 对齐位小了,效率又低. 比如3, 5 位这种非2的幂对齐则会对性能有影响。因为现在计算机体系的寻址位移导致2的幂次寻址快。

写算法

1. 在无序数组中找到按序左右差最小的两个数 归并排序排序加线性扫描（其实在最后一次合并的时候可以直接扫描出来不用真的合并，当时太急着给答案没想到）

反思

被转岗，简历没通过。面试过程很轻松和舒适，我都不知道是怎么挂的。

smartX（最难受的一次面试）

一家做存储的公司，但是我看要求上没有太多，所以我去试试了。

面试官个人情绪很重。

一面（挂了）

项目经历

1. 项目经历，我看你这些项目都没啥意义，你这个存储项目还是比较近期做的是吧，先考考你基础知识。

操作系统

1. 你了解VFS吗？open操作是怎么做的。 是要站在什么角度去思考这个问题，是要考虑定时器终端吗（一开始我没有反应过来VFS是虚拟文件系统）
2. 不用粒度那么细，就是考虑VFS就行 VFS我没有了解（我们学校新换的教材，是OSTEP，没有讲虚拟文件系统，而是一个真实的文件系统。我后来才想起来虚拟文件系统的缩写是这个VFS）
3. 你们不学操作系统吗，你不是计科吗？那我问你IPC中哪个最快。 信号量，或者共享内存吧（这边真的是记不清楚了，忘记信号量是怎么实现的了。 明显面试官已经不耐烦了）
4. 进程，线程，协程的区别？ 进程线程很简单，但是我协程说的少，我就知道c++要支持协程了，协程比线程更轻量。

网络

1. 问了一个网络链路的问题，具体也忘记了好像是同一子网下已知ip通信的问题，感觉考的是arp。被质问这不是网络书第二章的内容吗，你为啥都没学，那后面网络也不用问你了。 （虽然解释了，现在的教材是自顶向下，第二章是应用层http啥的，但是面试官已经被我的不专业搞得不开心了。）

日常学习

1. 你都是怎么学习的，你最近不是再做一个单机KV吗，你看了什么。 我整理了目前主流的数据库索引方式，比如b+树，还有一些内存数据库的索引有：跳表、哈希、平衡二叉树。（我发现我说自平衡二叉树，好多人都只会以为我要表达的是AVL这种平衡深度的树，其实红黑树也是的啊是黑色平衡以后这边我会强调是红黑的） 还有最近在看Redis分析的文章，在看一下我需要的点。
2. 那你是一篇paper都没读过吗，你没有度过paper你的高度就只会在那个写《XXX剖析XXX》的水平，而且还有可能会被误导。 嗯，因为我确实是没有想过看他们的储时paper，我在官网看了官网的文章。
3. 官网文章是给使用者看的，你看这些没有意义。那你随便讲一下你最近阅读过的paper。 我最近可能没怎么看过paper(我是真的没想起来，因为我以为问的是那种顶会很出名的那种)我看过一个人改良了传统的hash map成为了内存友好型。并且分析了和谷歌提供的map空间利用率。在他的future work里面提到了他已经有想法把利用率提高到87.5%
4. 好，你说hash map的内存友好，hash map为啥内存不友好。 这个不友好是相对而言的吧，你和红黑树比肯定快，但是消耗空间。
5. hash怎么就比红黑树消耗空间了，hash就是一个计算的再存储，你同样要存储相同的数据，树还有指针索引的浪费，为啥hash内存不友好。 我不太清楚，我以为是红黑的分配是动态的，而hash不太一样，hash map 要指定大小，为了冲突降低或者雪崩效应，hash要分配的空间要大于自己暂时需要的大小。
6. 真的是这样吗，你都没有好好了解。hash确实在一些场景内存不友好，但不是你说的。
7. 后面就是我问他咋学习，咋看paper学习。面试官虽然十分不耐烦，语气声音已经不正常了，但是依旧非常详细的给我解答并且告诉我看paper的重要性。因为这是一个项目开始的纲领，虽然实现和这个paper会差的很远，但是你这样才会知道为什么这么做，还有方向

反思

这次面试直接自闭，感觉就很废物。啥都不会，但是也托这次面试的福，我再后面两天刷了一下raft一致性的初始论文、MapReduce、GFS的论文，发现其实这种paper其实也就是一种正式的博客。只不过很权威性。而且这些技术博客的语言已经很简单了，就是思想比较难而已。

这次面试很痛苦，但是收获也多。

深信服 （三轮技术面，已拿offer）

一面

简单聊项目，聊了聊面试过程中遇到的难处。和重新设计会怎么操作。

1. c++ 虚函数
2. tcp 三次握手、四次挥手
3. 一道智力题

还有一些比较基础给忘记了

二面

项目

先聊了一些校园经历

1. 你们的并发操作是什么实现的 我写的线程池，一单一个线程休息了，用消费者锁从任务队列取一个任务做。把cpu的一些核隔离起来，让cpu不能把任务安排过去，然后把程序绑定过去。
2. 这个项目做的时候有遇到什么坑吗？ 我是写线程池和负责http报文解析和构造的人，我有一个队友在写socket任务的时候在一个地方忘记释放文件描述符了，造成了每次运行能承载的量是不一定的，很诡异的问题。我后来发现文件描述符的问题之后，帮他改释放了。同时修改了系统配置，把文件描述符的上限开到了100k，因为我电脑笔记本的一级缓存只有256k，100k足够用。
3. 我现在有足够用的服务器，如果想要承受600m并发数的访问，你要修改那些配置。 我觉得首先就是哪个文件描述符的数量，然后把后面的保留端口全部打开，因为一共有65535个端口，而后面被保留了很多全部打开，每个端口分配一定的线程让乘积大于等于600m就可以。

c++

1. int (*a[8])(int)是什么 函数指针数组，参数int、返回int、这个系列有八个函数可以用偏移或者[]访问到。

2. 给了一个更复杂的式子，其实也是一个函数只不过已知其地址位0x1000000。要求是如何跳转到这个地址上。 首先想到的是CSAPP里面的缓存区溢出攻击。被反驳，

   因为段错误。后面才想到其实可以定义一个二维指针，指向的地址是0x1000000。然后用这个指针就可以使用这个函数了。

算法

考了两个智力题，在面试官引导下做完了。

三面

被鸽了30分钟，然后对方在家里面试我。

项目

1. 看了你的简历，没有很多的科研经历。你做过什么吗，我看你在导师那里做了一些东西。 我balabala说了一堆，概括了一下核心：其实是一个非对称加密的密钥分配的一个改进。
2. 那其实也不是很复杂的东西，我是说那种开源的东西...又聊了为啥校园生活没有经历ACM啊等等。
3. 聊了很多项目理解啥的

算法题目

1. 做了两个题，简单题被卡了20分钟很尬尴。然后一个稍微难一点的题3分钟A了

反思

最后我问了面试表现，面试官说你这个第一天确实很失望，但还好第二题做回来了。

我以为挂了，因为简单题没搞出来。但是没想到一天后收到了offer，都没有什么HR面。深信服反馈也挺快的。

其实仔细想想，其实在一二面确定了基本功。在三面想了解我的拓展性，但是这轮面试我没把握好，浪费了。

阿里（一面，在流程）

1. 成绩咋样，讲述项目。
2. 几个基本知识
3. 一道算法题目就是一个子集树。（中间写了一些不必要的临时变量）我给删了，所以稍微耽误了时间。
4. 我问他我的表现中有什么不满意的吗？ 面试官说我写代码思路乱乱的？没懂面试官的意思。

腾讯（被捞，刚一面）

第一次被三个人同时面试，被吓到了以为是直接准备三面结束呢。

一面

项目经历

真的很详细。我每说一个点基本都会被仔细的问一下。

比如我提到解数独算法，在普通的书的遍历基础上加入随机性提高效率。

对面一下子来兴趣了。

1. 项目设计的算法

   1. 你这个算法是有数学证明吗

      不是数学整明，而是在解的分布上，大致遵循正态分布在整个解空间中，所以我建立的随机算法也是准寻一个正态分布。所以我们就是这样做的。

   2. 那为啥不直接从中间找

      直接从中间找其实有点类似与深度学习过程中的过拟合，把正态分布过拟合成了中间为100%概率。这样虽然在这个区间内有良好的性能，但是对于最差情况就很糟糕了。加入随机性就是希望降低最差情况的影响。在最后的40G数据量测试下都能保证较好的性能

2. 编译器

   1. 你说的这个编译器里面的闭包特性是你预计要实现的是吗

      用我对维基百科的了解讲了一下闭包的概念。实现思路就是一个匿名函数，然后把定义这个匿名函数的函数的局部变量设置为调用处的内部匿名变量。使得在被调用的词法作用域内值被记录达到一种保存状态的效果。

操作系统、网络和c++基础

这里问的频繁就没记住

算法

问了几个子集树算法的问题，要我分别用BFS和DFS给出解。比较不同

反思

这次总体体验很好，感觉把我的一些项目的细节都扣的很细节。

阿里UC中台（已面一轮）

一面

时间稍微有点远，忘记细节了。

操作系统

IO模型

数据结构

1. b+树，红黑树的特点

   1. 红黑树是自平衡树，平衡依据是：黑色平衡，不同于AVL树的深度平衡。黑色平衡对插入节点和删除节点时触发平衡操作的概率降低，所以这两种操作性能好性能，但是正是因此查找性能差。因为深度不平衡

   2. B+树是B树的一种，B树类是m叉树，所以高度比红黑树低，索引次数少。B+树在B树的基础上更改设定为只有叶子节点有值，并且叶子节点之间呈现一种链表状，因此对于范围查找性能好。同时对于数值的空间局部性更好，因此更好的利用了磁盘预读的功能。有利于连续的数据的IO。

   3. 两者区别：

      1. B+树优点

         1. 范围查找中红黑树需要中序遍历，而B+树只需要查找最小值然后线性遍历。此刻性能
         2. B+树对于磁盘的利用率较好。同时查找节点次数少即IO粒度大。

      2. 红黑树优点

         1. 红黑树的优势就在于查找，因为B+树的局部更近似于线性表所以性能必然差于二分查找。

计算机网络

手机或者端设备再一次页面访问的时候会进行怎样的操作：

1. 首先，如果这个端系统是第一次链接这个局域的路由器等设备的话会先进行DHCP广播从路由器获取到本机的IP和路由器IP，子网掩码等。当然还有可能自己手动配置在获取到路由器的可分配的IP中静态分配IP。
2. 然后获取IP之后像访问非局域网还有可能有NAT这次协议进行一个本地IP到外部的映射。
3. 然后要进行DNS的查询，有可能本机已经有缓存，但是在无缓存的情况下，要先找到DNS服务器，发送DNS请求报文。然后获得域名的IP。
4. 在知道的服务器的IP地址可能根据客户端可能是TCP或者UDP协议发送请求。如果是TCP还需要三次握手。
5. 在得到服务器的数据包之后客户端获取报文内容根据需求生成指定的效果。

字节跳动后端（已面三轮，在等HR面）

一面

操作系统

1. 线程数的确定依据

   1. 优先考虑操作系统能分配的线程数，因为过多线程切换回来的负面影响

   2. 然后考虑线程的任务类型：

      1. 计算密集型（CPU依赖重）则性能被限制的原因是单线程上的计算，过多的线程反而因为频繁切换线程而性能下降，尤其是线程之间有公用资源时且使用锁需要修改而不是只读
      2. IO密集型（CPU依赖不大，主要是在等外部数据）这种则可以适当增加线程数，用线程被切换出去的时间IO反而会提升性能

2. 页、分段的问题

3. 进程、线程、协程

4. 线程之间的资源利用的权限，一个线程是否可以访问另一个线程的内容

   1. 如果说另一个线程的内容是指另一个线程栈上的内容，并且两个线程是同一个进程的线程是有可能的。因为同一个进程的线程是同一片虚拟内存空间的。所以只需要知道另一个栈所对应资源的虚拟地址即可
   2. 其他情况，如不同进程的线程则需进程间通信的方式

算法

1. 对同一个IP的在一段时间内访问一定次数限制。

   思路：

   1. 用一个map，最好是hash map对时间性能好，如果任务场景的存储空间有限则也可以使用红黑树这种map（其实主要是c++11 STL组件的新加的hash map我忘记怎么写了，牛客没有提示，不敢写怕尴尬）

   2. 然后每次来一个IP查询一次map，

      1. 如果没有则加入，并且写入IP的上次访问时间，访问次数置位为1

      2. 若有，

         1. 当前时间戳与保存的时间戳比较，如果在限制的时间内则，累加访问次数。不改变时间

            1. 如果此时访问次数超过了限制要求，则返回失败
            2. 反之，返回成功

         2. 如果超过了限制的最短时间，则刷新时间戳，并置位访问次数为1

   这个题就是用std::map<IP,std::pair<Time,uint_8>>。即可其中IP和Time是我自己定义的数据类型，因为面试官让我自己设计。uint_8就是为了省空间。编写代码的时候两个尴尬的事情，我忘记了std::pair库是哪个头文件的，编译出bug，还有就是不知道为什么中间输入法变为中文，有一个地方的,变为中文的，但是在牛客上的提示却很奇怪。让我和面试官找了一会。后面样例全过了。

二面

一面二面是连着来的，二面没怎么问基础知识，主要是聊了项目经历。

算法

1. LRU算法，leetcode 原题。我说了用次数因为考虑频度，因为直译是最少最近使用，但面试官非要让我用时间，怀疑我没理解LRU。没有办法，其实我估计面试官也是在leetcode上看到的这个题，因为leetcode官方给的答案也不是LRU的真正含义，而是类似于最近没被使用（最远被使用的踢出cache）但是面试官怎么要求怎么来。

   思路(面试官没有给要求，完全自由度)

   1. 自己定义一个类，有get、put、find_lr_node操作。主要维护一个map<node,Time>
   2. map的size小于限制，插入
   3. 反之，使用find_lr_node踢出，再插入
   4. find_lr_node的算法就是找到最小Time，是一个排序时间复杂度(nlogn)
   5. 提示时间性能的方式：用辅助空间，优先队列存放pair<Time,node>优先级用Time作为标准。每次使用堆删除节点重新插入。O(1)时间复杂度

2. 最大岛屿面积。一个二维空间中，1表示岛屿，0表示海洋，上下左右四个方向相连的区域认为是一个岛屿。

   思路（简单题，暴力搜索）

   1. 定义BFS算法，因为上下左右都有用广度优先更符合直觉，

      1. 如果当前节点为1，设置当前值为1，并把当前节点清零表示访问过了

         1. BFS访问上下左右节点

      2. 反之，返回零

   2. 遍历岛屿

三面

系统（Linux系统，而不是操作系统）

1. 常用命令

2. 查看内存命令

   不会，因为我是用的是wsl的Linux，查看的时候都是之间看windows的任务管理器。Linux平常就写代码和编译

网络

1. HTTP报文格式和内容

2. 判断一个报文如何读完了

   1. 找到content-length, 根据这个读
   2. 没有则用超时，发送以读长度，客户端收到比较，没有则重传

数据结构

1. 常用数据结构，及其应用场景

   1. 线性表

      1. 数组，队列，栈，hash table

   2. 树

      1. 平衡二叉树（红黑、AVL）、外查找二叉树（B树类）、哈夫曼树、...

   3. 图

   还没讲完被打断了

其他

1. 分布式协议

   我就讲述了我实现版本的2pc（和一开始提出的不同，因为有恢复追踪）

2. 平时咋学习的

   1. 遇到陌生学课一般先看一下历史脉络，看一下一开始提出了什么，为了什么缺陷又提出了什么，解决什么功能。看一下有没有专门的引导或者书籍或者paper。

   2. 如编译，

      1. 我是从MIT的SICP开始入门，接触了Lisp。
      2. 然后再看了一个叫做《7周7语言的书》领略了一下编程语言开发者引入特性的思考和实现的细节，还有一些哲学观念比如语法结构和编程范式。
      3. 再后来上课学习了编译原理即龙书。
      4. 自己写了一个小编译器，用新的框架和库。体会一下深入体会一下。

算法

1. 对一个无序数组中给出最大的组合（最后都没编译出来，面试官也不熟悉c++，有一些库函数忘记是哪个库了，所以我自己写了find函数啥的）

   思路：

   1. 利用排序，只需要写比较函数即可

   2. 比较函数原则：

      1. 当前位比较，不同则返回比较结果

      2. 相同则比较下一位

         1. 直到不同
         2. 或者两个数都没有下一位，返回相同
         3. 有一个数当前位没有数字，则在没选择过的列表中选一个当前位最大的。

   这个思路最后给面试官讲出来了，后来我发现可能在一部分case下出错。判断函数可以很简单：

   xxxxxxxxxx
   3
   1
   bool cmp(string a, string b) {
   2
       return a+b > b+a;
   3
   }
   

   整明用反证法。主要思想就是两个数拼起来能让整体大的在前。

最后聊天

1. 你平时在学校刷过题吗？

   老老实实回答，没有。就写过20多道mid题目，剑指offer看了10几道。