深信服『大牛』计划C++开发面经（已意向书）

大牛计划相当于深信服的秋招提前批吧，出于地域的考虑，秋招继续投了深信服，技术面总共三面

春招也投了但后期懒得面了，发现秋招投递时还不能内推，于是直接上官网投递了大牛计划，结果是一样的

一面

昨晚组内聚餐喝酒，晚上有点着凉，早上起来晕乎乎的，还迟到了五分钟，状态不是很好，面试官给我的感觉有点慵懒，不知道是不是我迟到的原因

自我介绍完后，压根没问我的项目与实习经历，或者说压根没看我的简历，直接问基础

String类的拷贝构造函数，第一版代码写出来有个瑕疵，拷贝构造函数是没有返回值，我返回了*this，经过提示后修改了。然后在回答中提到了自赋值的问题，说拷贝构造函数要解决自赋值的问题，面试官反问确定需要吗，想了一下说不需要，然后面试官要我写一个赋值构造函数，要我判断一下自赋值的问题，我写成了rhs == *this，最后被纠错了，应该是&rhs == this。开头第一个问题，还没进入状态，有点懵，附上一个不错的资料：C++面试中STRING类的一种正确写法

排序算法有哪些（内扯了一堆），STL的sort怎么实现的，口述快排代码实现

哈希表呢（表空间，开链法，开放寻址法，Java的哈希表种链表长度超过8转红黑树，负载因子，rehash，质数，扯了一堆）

树的遍历方式有哪些，最开始达成前序中序后序，第一儿子下一兄弟什么的，扯了一会才说bfs和dfs，bfs和dfs如何用代码实现（队和列栈）

TCP三次握手协商了哪些东西，我说：协商了哪些东西？窗口大小？序列号？面试官说：你是不是对网络这些东西只是有个概念的了解，我说：不是，我有实践经验，用wireshark抓过包，用tcpdump抓过包blablabla。然后面试官就换问题了，计网再也没问过了。这里很憋屈，感觉根本还没发挥就结束了，毕竟相对来说计网是我的强项

最后给我出了个问题，给定一个二维象棋盘，马的走法是日字型，可能会被棋盘的棋子別脚，随机给出一个起点和一个终点，求最短路径

我想了一会，没啥好方法，感觉不就是dfs回溯一把梭？

然后面试官说要遍历所有到终点的可能，时间复杂度太高了。

我再思考了一会，说用动态规划，弄一个二维数组dp，dp[i][j]是从起点到第i行第j列的最短跳数。

面试官想了一会，说『如果能建立这样的二维数组，那就没必要建立了，因为能够建立的前提就是你已经知道了答案』。

其实这里没太懂他说什么，不过我对马的走法有一定的疑虑，因为马可以迂回前进的，如果是卒子，肯定可以用dp的。于是继续考虑其他方法。

面试官这时提示：能不能转换一种数据结构？我想了一会说：应该可以用Trie（念作try）树吧，面试官好像没听过这个数据结构，反问：Trie树是什么。我说前缀树，每个节点保存当前点，当探索到终点，输出这条路的路径就是最短路径了。

显然，我的回答不是题库中的标准答案，他提示到：你提到了树，用什么遍历方式来解这道题呢？我心想，这不就是刚才的面试问题吗，回答bfs和dfs。

面试官问道：对于这道题，哪种更好呢？

我想了一会，对于面试官而言，他应该期望听到的答案是bfs，但是我对马的日字形走法还抱有疑虑，但也不想耽误太久时间，直接说bfs。

问为啥。

我说：可以想象一幅地图，用bfs可以从起点开始一圈一圈的往外遍历，当探索到终点时即可直接输出当前路径就是最短路径。我一边说一遍看面试官反应，这好像就是正确答案。

但是我没等他开口，说出了我的想法：我刚拿到这道题时第一反应是用dfs，感觉和我现在说的bfs是差不多的，因为给定了棋盘的起点和终点，你就知道了大致的方向，dfs是一条路走到黑，那我就给他定一个初始的方向。这就有点像启发式的A star算法，用来搜索最短路径是很合适的

面试官说：起点和终点之间可能会有其他棋子阻拦，你能保证你说的dfs是个好方法吗

我心想：bfs还得遍历其他方向，dfs碰到南墙还可以迂回一下，想象一个地图，我感觉dfs的方案会更快，但是我不太想和面试官争了，十二点了，感觉面试官要到点下班了，于是我说：这样看来，的确bfs会更好一点。

果不其然，面试官很快就说今天的面试就到这里吧，我说好的，然后双方就互道拜拜了，没反问环节。

我面试官过这么多场，感觉这次面试的感觉很奇怪，有点不爽，特别是我在洋洋洒洒地讲排序算法与哈希表的时候，面试官好像在低头划手机。害，可能是正好有事吧，我又迟到了，减了很多印象分。但从面试问题来看，问的东西都很基础了，都是中规中矩的问题，没啥发挥空间，我的两段大厂实习经历也根本不问，不知道咋表现自己。有些知识点我是很清楚的，但是面试官没get到我的点，双方的风格不是很匹配，在某些问题上，面试官点到为止，『没有引导我去深挖』。

二面

隔了一周

很愉快的一次面试，面试官非常耐心温柔有礼貌，跟一面面试官风格迥异

聊实习

malloc最大分配多少内存（我不太清楚具体最大值，但是我知道小于128K用brk在堆区，大于128K用mmap在内存映射区，关于这题的具体解答可以参考这篇文章：malloc最多能分配多少内存

C++内存分布（从虚拟地址空间高地址往低地址看，堆栈blabla

内存碎片怎么解决呢（答了伙伴算法和slab算法

io多路复用（select, poll, epoll

一千万个域名，怎么知道一个域名在不在里面（前缀树or布隆过滤器）

设计一个日志系统，包括采集、存储、查询（答了我在腾讯实习时接触的那一套ELK stack

100层楼，两个鸡蛋，用最少的次数测试哪层楼会摔碎（鹰蛋问题，我直接说了最优结论，在第14层测，在+13层测。。然后很简短地说了下这个最优结论的推导过程，其实推导过程记得不是特别清晰，好在面试官也没细问

我说个大概的思路，第一个鸡蛋为A，第二个鸡蛋为B：

1. 假设A先尝试第x层：
1.1 如果碎了，B必须尝试1、2、3...x-1，所以总共需要x次
1.2 如果没碎，那A还可以继续使用，出于利益最大化的考虑，A的后续尝试肯定是『跳』着去尝试，假设每次尝试都是+x
2. 基于以上考虑，我先随便假设一下，假设x=10
2.1 如果A在x=10碎了，那么最坏情况下，B得从1尝试到9，所以总共需要10次（A的1次+B的9次）
2.2 如果A在x=10没碎，按照每次+x的设想，
2.2.1 A的第二次尝试是20，如果这时A碎了，B得从11尝试到19，所以总共需要11次；
2.2.2 A的第二次没碎，第三次尝试30碎了，B得从21尝试到29，所以总共需要12次；
2.2.3 以此类推，一直到A尝试90，如果碎了，总共需要18次（A的9次+B的9次）；如果没碎
3. 可以看到，每次+x是不太好的，越到后面，所需次数越大，究其原因，**A的每一次尝试都算作尝试次数，而B的搜索空间永远都是`[kx+1,(k+1)x]`，所以最坏情况下，尝试次数是递增的**，所以现在我们的目标是设计一种方案，使得无论危险层在哪层，我们的方案都是稳定的，且在最坏情况下是最优的
3.1 如果A没碎，A可以继续尝试，但A尝试的『这一次』算作一次了，所以后续尝试的层数不应该是+x，而应该是+x-1
3.2 假设A第一次尝试为x，那第二次尝试就应该『跳』x-1（这x-1的区间是用来给B搜索的），第三次就应该『跳』x-2（这x-2的区间是用来给B搜索的）。。。

3.3 那x的选择就可以通过等差数列来求，1加到13的和比100小，1加到14的和比100大，所以x必须得从14开始选择
4. 综上，A的尝试轨迹应该是14、27、39、50、60、69、77、84、90、95、99（这里共11次），举几个例子验证一下最坏情况
4.1 危险层是14层，总共需要1+13
4.2 危险层是50层，总共需要4+10
4.3 危险层是99层，总共需要11+3
5. 结论很简洁，关键是要把这个过程讲清楚

手撕代码：假设你是个咖啡店老板，你有一个一天的流水单，流水单每行是交易发生的时间及其金额，求两小时内最大金额发生在哪个时间段，输出起始时间即可

（为了简化，时间就用int型吧，可以用纪元时间戳表示

讲了下思路，维护两小时的滑动窗口blabla，这个时间复杂度是On，我觉得是个不错的方法，然后就让我写代码了

#include <iostream>
using namespace std;
bool isWithinTwoHours(int l, int r) {
    // 两个时间戳如果在两小时内则返回true
    return (r - l) < 2;
}
int func(vector<pair<int, int>> vec) {
    int n = vec.size();
    int l = 0, r = 0;
    int sum = 0; // 记录两小时窗口内的销售额
    int res = 0; // 记录两小时窗口内的最大销售额的左端点（起始时间）
    while (r < n) {
        vec[r]
    }
    return res;
}

还没写几分钟，面试官就说到时间了，你的想法很不错blabla（表扬了一通），明确告诉我过了