我的秋招

杂记

　　秋招已经结束了，对于我而言，即使还有一家网易互娱刚通过一面，但已经无关紧要了。我的秋招从八月底开始，十月初结束。找工作的过程是很累的，需要耗费大量的时间和精力，经常是跑了一天但仍然感觉自己什么都没做，面试流程一面二面三面每一场都要等一周左右的时间。秋招总共笔试面试了 $10$ 家公司，被刷 $5$ 家，拿到 $offer~3$ 个，$2$ 家待定，其他 $9$ 家公司虽然通知笔试面试了但最后都咕咕咕了，也不知道几家被刷了简历。
　　大学期间与计算机相关的，除了 $ACM$ 和勉强算是一个项目的扫雷，什么都没有。秋招期间我的笔试策略就是专攻编程题，选择题只做数学、数据结构、算法和一些找规律的智商题，涉及到计算机网络、数据库、操作系统的就直接瞎选一个，简答题如果碰到这三大块的就直接空着，如果进入面试，面试官开始问这三个方面的问题的话，我直接说不会，他们也就跳过了。

　　暑假期间有个同学给我发了个阿里内推的微信推文，投了一个内推 $Java$ 工程师，这也是我投的第一家公司。笔试题是一个类似于旅行商的问题，在一个平面直角坐标系上，一个快递员从 $(0,0)$ 点出发，总共有 $n$ 个点，第 $i$ 个点的坐标为 $(x_i,y_i)$，其中 $x_i,y_i$ 都是正整数，快递员每次只能从 $(x,y)$ 点往上、下、左、右移动一个单位长度，问快递员要经过所有点后回到原点，最少需要经过的距离。旅行商问题用状压可以 $O(2^n)$ 内得到最优解，我打算写个贪心求个近似解差不多得了，然而对于我这种只会用 $Java$ 写 $BigInteger$ 的选手，找了半天类排序怎么写，不会，就写了一句：

import java.util.*;

提交了，接着又花两三分钟做了两百道情商智商测试选择题。我想他们看了我的提交应该不会再跟我联系了吧，没想到晚上就来了电话，面试官只看到我的提交，还没空点开我的提交内容。最开始他想通过一步步引导，让我能自己得出一个近似解。先问我会不会求最短路的算法，我想这张图上的距离全是曼哈顿距离，最短路不用预处理都可以 $O(1)$ 求出来的，为什么要用到最短路呢？我讲完迪杰斯特拉堆优化之后，关于这道题我们基本上是鸡同鸭讲。之后，面试官开始问关于 $Java$ 的问题，一问三不知：

“面向对象的三个特性了解吗？”

“……不了解。”

“封装继承多态没有听说过吗？”

“哦哦，听说过。”

“那你分别解释一下这三个特性吧。”

“%&$^#&%&#*#P@)……”

在毫无准备的情况下，关于 $Java$ 的任何问题都没有回答上来，回答了部分和 $C^{++}$ 有关的问题，最终顺利地挂掉了阿里一面。

　　$BAT$ 就是很喜欢培训机构出来的，有项目经验的，我认识的一个同学在很久之前这样说过。看来他们喜欢有项目经历的，对工程方面了解比较多的，自此，我没有再投 $BAT$。阿里不适合我，我也因为阿里的两百道情商智商测试题而对阿里完全没有好感，终于理解 $myk$ 上学期的心情了。阿里后来再给我发笔试通知的时候（提前批被刷的貌似都转到正式秋招去了），理都不想理，那时的笔试时间正好和美团的冲突，自然选择了美团的笔试。

　　这次面试结束后，发现要开始准备一些关于 $C^{++}$ 的面试题了，毕竟连菱形继承在 $C^{++}$ 中是如何解决的这个问题我都回答不上来，投简历的方向也都限制在 $C^{++}$ 和后端开发工程师，而算法、$Java$、前端之类的工程师，一概没投。在电信研究生 $ld$ 学长的推荐下，我先去下载了《$C^{++}~Effective$》，最后一场多校结束后就开始看，看一天大概也就看了一半，可烦，晚上又去查了下面经，发现一篇写得很不错的总结：C/C++ 面试知识总结，第二天又花了大半天看到了第六项“操作系统”，下了本操作系统相关的 $PDF$ 再根据网站上总结的知识点开始看，看不懂，挣扎了半天，终于决定放弃了，于是相当于花了两天时间复习了一下 $C^{++}$。

　　八月底平均每天晚上在牛客网上投四五家公司，刚开始投简历，总是比较心急的，希望今天投了简历，明天就能给回复，海投了五六天之后，由于仍然没有收到公司发来的笔试消息，一度感到失落，想过是不是由于自己的简历太难看了：

只有黑白，连个照片都没有；也想过是不是因为我的学校，毕竟华师相比于华科武大而言，计算机是一个弱项，来华师开宣讲会或者校招的 $IT$ 公司都是些完全不知名的小公司，又或者是我的专业，物理学师范？还是我简历上的项目经历毫无亮点，又或者是 $0$ 实习经历，导致我的简历直接被筛？

　　几天之后，终于等到了一家上海谦信投资的电面，这家公司估计是我在华科内推群里看到的，他们表示也没在武汉发招聘信息，也不知道我从哪里得知这个投简历的邮箱，莫名其妙地收到了一份来自武汉的简历，就给我安排了一次电面，面试过程平淡无奇，先问了面经上 $C^{++}$ 的问题，看了面经的都会，计算机网络和数据库方面的问题，我直接不会，他也就跳过了。然后问给一个数组找到第 $k$ 小的数字，我先调用了个 $sort$：

int n, k;
vector<int> vct;
// input data...
sort(vct.begin(), vct.end());
printf("%d\n", vct[k - 1]);

面试官沉默了一会儿，解释说其实是想看我写排序的过程……我就给他写了个归并排序，第二个问题是用链表实现队列，再给自己写个测试程序，最后让我介绍了一下我的扫雷，大概面了一个小时结束，结束之前告诉我说 $11$ 月之后如果还有 $hc$ 的话，就给我安排一次现场面试（我跟他说了我的物理老师实习要到 $11$ 月份），往返车费由公司报销。面完对这家公司的期望不大，毕竟我本来都忘了投过这家公司。

　　又进入了漫长的等待期……

　　$9$ 月 $1$ 日之后，陆陆续续收到了公司的笔试通知，悬着的一颗心终于可以放下一半了，毕竟笔试的编程题分数占比大，大多数的笔试都能通过，到现在没有通过笔试的有：$bilibili$、搜狗和携程。

　　$bilibili$ 只有几道简答题，一看是计网数据库相关的，直接跳过，倒二题是组合数算概率没什么问题，看编程简答题——实现一个 $Html$ 语法检查器，除了标签闭合的检查外，标签内还有属性格式检查，给出的合法格式有：

<label></label>             <!-- 普通标签闭合 -->
<label/>                    <!-- 自闭 -->
<label a="..." b="..."/>    <!-- 属性，引号内可以是任意字符 -->
<label1><label2/></label1>  <!-- 可多层嵌套标签 -->

其中 $label$ 可以是任意小写字母组合，属性名也是，除了用一个 $string$ 栈来实现标签的嵌套，其他的都是暴力检查，当然细节是很多的，比如在发现 < 符号的时候要找到下一个不在引号内的 >，还有命名检查之类的，两个小时笔试这题就写了一个小时，最后还剩属性格式检查没写，写到血崩。

　　搜狗也是两道我不会的简答题之后，两道编程题，一时半会想不出正解，那时候已经不想再面搜狗了，而且一个小时后还有其他事情，就写了一题暴力，空两道简答、一道编程题后，交了。携程貌似就三道暴力可以通过的编程题，人为要求设计数据结构，让平均时间复杂度在 $O(\log n)$ 或者 $O(1)$ 之内，最后是人工阅卷——携程可能是世界上最好的公司了，可惜我进不去。

Minieye

　　之前在 $Minieye$ 的学姐帮我投了个简历，那天刚吃完晚饭，$Minieye$ 给我打了通电话，本来想跟我预约笔试时间的，后来 $HR$ 小姐姐突然想到什么，就先问了一下我计划去实习的时间，我说明年毕业后……于是由于时间距离现在太远，希望明年继续联系。又经过几次辗转，将明年毕业后实习改成直接参加校招。题目直接挂在 $vjudge$ 上，半小时做完，就约电面了（以下对话有缩减或调整顺序）

“你是物理学专业的是吧？那你了解傅里叶变换和xx（已经忘了）变换吗？”

“傅里叶级数展开在高数书上有学过，作用是##@^&%……傅里叶变换好像数理方法的时候有学过，但是记不清了，另一个没听过。”

“OK，那你在大学期间有没有推导过什么比较牛逼的公式啊？”

“我一般都是按照书本上的公式来推的，虽然我是物理学专业，但是大学的主要精力还是在搞竞赛上，物理方面的课程只是保证及格……”

“你们物理学高数和线代吗？你们学的高数和线代和数学专业他们学的一样吗？”

“不一样，我们学会了公式只要会应用就行了，数院他们主要偏向于公式的证明之类的。”

“OK，那你打比赛的时候，在队伍中主要担任什么样的角色呢？”

“我主要是主代码手，然后在暑假集训期间除了打多校也刷了 $AC$ 自动机专题、二分图匹配专题，刷多重匹配的时候学了一下网络流……”（然后面试官的重点就从我的物理专业转移到网络流了）

“那你能证明网络流吗？”

“嗯？”（突然懵逼）

“就是为什么跑满增广路就能跑到最大流？”

“不好意思，#&#^@&*@W@#……（大意是不会）”

“那你知道几种最短路的算法吗？”

“迪杰斯特拉、floyd、spfa……（后面就是对这三种算法的简单介绍）”

“你迪杰斯特拉用的是堆优化的还是……”

“堆优化。”

“那你能手写堆优化的迪杰斯特拉吗？”

“可以。”

“那你能手写网络流吗？”

“呃……我学网络流的时候只整理了一个 $dinic$ 的板子，做题的时候主要是构图然后连个源点汇点……”

“嗯嗯嗯……好的，OK……那这样吧，给你这样一个问题，二维平面直角坐标系上，有两个凸多边形，这两个凸多边形有一部分是相交的，求相交部分面积。”

（确认了问题的一些细节之后，想了半天……）

“我只会 $O(n^2)$ 的做法，这个肯定不是最优解，但是我现在还没想到更优的做法。”

“那你能不能从积分的角度来考虑这个问题，看看能不能得到什么解决方法。”

（又想了半天）

“不会。”

“嗯嗯，好的，那你对公司代码规范有什么看法呢？”

“&%W&￥%&#￥%%&￥#*&￥#……”（表示强烈支持）

“好的好的……”

一番客套之后，就挂了电话。电面结束感觉自己凉透了，后来才知道，给我电面的那个是金牌爷……

　　你能体会那种明明什么问题都不会还要被吊着打的感觉吗？听到的所有问题几乎都不会，唯一回答上来的只有那个傻逼最短路……后来问 $shz$ 才知道原来求两个凸多边形相交面积是裸的半平面交，后悔暑期看平面几何的时候只看到半平面交就不看了，至少应该知道一下它的应用啊，问到后面一方面想尽可能抓住一个自己比较擅长的问题把一句话拆成几句话，然后回答他个四五分钟，另一方面又想马上结束面试，觉得越问面试官就会发现我越菜，如果这是一张考卷的话，我可能只能得 $10$ 分。

　　感觉自己凉透了，这是我最惨的一次面试经历，没有之一。

　　晚饭的时候 $Minieye$ 的 $HR$ 小姐姐通知我说又给我安排了一场面试，我心里那个万马奔腾啊——这是一面还是二面啊？什么叫又给我安排一次面试啊？那这次面试是通过了还是没通过，要再来一次一面吗？如果下次面试我的表现还是这么糟，那不是他们连收我的理由都没有了？虽然之前听说过 $zzq$ 面试的时候也是“不会不会不会”然后就过了，但是他可是金牌爷啊，我这么个弱鸡我……

　　好在第二次面试的问题简单很多，面试官先问了一些 $C^{++}$ 面经上的问题，看了面经的都会，突然问了一个“为什么模板函数的实现要放在头文件里”，我一下子懵了，完了又来了又来了……$Minieye$ 到底是家什么样的公司啊，问问题都不按套路出牌的哟，之前看的面经在这里通通要失灵。正当我有不祥的预感的时候，面试官开始换个方向，问了两个算法题，一个是计算 $n!$ 的末尾总共有多少个 $0$，$n_{max}=10^7$，这个只要 $O(\log_5n)$ 统计 $5$ 的因子个数就行了，是个套路题，第二个是求 $n!$ 去掉所有末尾的 $0$ 之后，末尾 $9$ 位数字，这个只要把所有 $5$ 和 $2$ 的因子相消，然后乘的时候不断对 $10^9$ 取模就行了，最后问了我平常的刷题网站（$vjudge$ 和 $codeforces$），又问了我的刷题量和 $vjudge$ 账号，还好没有瞎报刷题量。

　　再后来就拿到了 $offer$，商量了一下薪资和入职时间之类的，几家公司的面试时间是穿插着的，$Minieye$ 给我发《录用通知书》的时候，我拿到了更好的 $offer$，所以最终鸽掉了。

美团

　　美团笔试的选择题我已经记不清了，只知道编程题的第一题好像是个暴力，第二题是给定一棵 $n$ 个节点的树，从根节点出发，遍历所有节点，所需要走的最短路径，树上每条边的边权都是 $1$，最开始还想歪了，其实就是一遍 $dfs$ 求树的最大深度 $depth_{max}$，答案就是 $2(n-1)-depth_{max}$，过完就交了。

　　然后收到了面试通知，但是要去现场，地点在光谷，实际上到了光谷之后小黄车还要骑个二十几分钟，从开发区一中到丽顿酒店一般要两个小时，过去回来一趟就要四个小时。

　　一面二面从下午四点到晚上，都是技术面，一面的面试官是个很帅的小哥哥，一番自我介绍之后，让我介绍了下 $ACM$ 的比赛形式，他听了之后表示很有意思，看来他是完全不知道这个比赛的。接着出了个题目，判断两个单链表是否相交，如果相交就返回第一个相交的节点地址，一看就觉得是个《剑指 $offer$》的题目（可惜我没看），只想了个加 $vis$ 标记的方法，空间是 $O(n)$ 的，写了两个 $for$，节点结构是这样的：

struct Node {
    Node *Next;
    bool vis;
    int val;
}

这是一种很糟糕的做法，它修改了节点的数据成员，小哥让我先把这种做法写下来，这题可能主要还是想考察代码能力，写起来没什么大问题，算是勉强通过了。第二题是个概率题，问 $15$ 个学生平均分到 $3$ 组里，问其中的甲乙丙 $3$ 个同学分别被分到 $3$ 个组里的概率，$3$ 个组是无差别的（任意两组所有成员交换，认为是同一种方案），$\frac{C_{12}^4C_8^4C_4^4A_3^3}{C_{15}^5C_{10}^5C_5^5}$ 没什么问题。最后是一个二叉树求最近公共祖先，每个节点都没有编号，可能有什么很巧妙地运用二叉树性质的方法的吧，但我就是没想到，感觉和求两个单链表第一个交点的问题一模一样。最近公共祖先只知道 $LCA$，先问了下空间复杂度为 $O(n\log d)$，但时间复杂度可以达到 $O(\log d)$ 的解法能不能接受，小哥考虑了一下就让我先讲我想到的做法，给他从 $ST$ 表到 $dfs$ 序到 $LCA$ 讲了一遍，把他讲得一愣一愣的，面试官表示还是第一次听到这么清奇的做法，其实心里一直在偷笑还好他没搞过 $ACM$。真心感谢一面的小哥哥，即使我想到的不是“标准答案”，但还是给我机会展示我的解法，而不是“如果没想到最优解就往最优解的方向引导”，这样引导着引导着，可能本来能有一个基本的解决思路的，最后反而被引导得脑子里一团浆糊了，面试表现也可能会因此扣分。

　　二面的第一个问题就问倒我了：如果我不是美团的内部人员，我想要估计美团某个地区的骑手数量，有什么方法？我想了好久好久，才想出一个勉强能用的方法：通过手机号码标记来统计骑手。面试官表示其实通话记录也是一个隐私数据，不容易获取，但是也算是一种方法吧。又问了我觉得自己有哪些优点和缺点（一面的时候已经问过了，三面的时候这个问题还会问……），我在回答这个问题的时候，面试官还会根据我的回答提问：在代码没有通过的时候，我会考虑用什么样的数据进行测试，我回答一般是 $\pm1,0$ 和极限数据，如果还是没有发现问题，就只能暴力对拍。关于我的优点还提到“我写代码手比较稳，一些细节的地方可以处理得比较好”，我说了这句话之后，面试官就打断我让我来手写实现一个 $memcpy$ 函数，并考虑各种可能的异常以及异常的处理……确认了问题的各个细节之后，我就开始写了，实际上只考虑到两个指针指向的内存可能重叠的异常，其他异常完全想不到，当时设计的函数声明是：

template<typename T>
bool memcpy(T *a, T *b, int n);

$a$ 指向的是复制源内存，$b$ 指向的是复制的目标内存，$n$ 表示需要复制的元素个数，如果复制成功则返回 $true$，失败返回 $false$，稍微总结一下当时的对话吧：

”你有考虑到 $b$ 指针指向的内存不足的情况吗？“

”嗯嗯，考虑到了，但是不知道如何检查指针指向的内存大小。“

”有没有可能 $b$ 是一个野指针或者空指针呢？“

”emmmm……这个没考虑到。“

”如果 $a$ 和 $b$ 指针指向的空间有重叠部分，会出现什么问题？“

”复制过程会把源数据覆盖，如果在复制过程中才发现问题，可能导致无法恢复数据的情况。这一点在代码中写检查了。“

”那你在代码中是如何解决的呢？“

”哦，我忘了写异常处理了，直接返回了 $false$。“

”你现在考虑的话，要如何处理这些异常？“

”令 $b$ 指向一块新开的空间，然后再复制过去，这样的话指针就不能用值传递了，要用引用传递，这样原指针也能被指向新的空间。“

”这样会不会出现什么新的问题呢？“

（稍加思索……）

”在函数中新开了一块内存而没有在函数中释放，可能会导致一些隐式的问题，这可能算是一项禁忌吧。我目前能想到的就是如果函数外有另一个指针变量 $c$ 和 $b$ 指向的是同一个地址，$b$ 指向的原空间被释放后，指向了新的空间，指针 $c$ 就会变成一个野指针。“

到这里我已经很虚了，因为刚说完自己的手比较稳就马上被打脸，即使这里有我没有这方面经验的原因，但是面试官可能只看得到我写的代码漏洞百出。

　　第三个问题是有两个非常大的文件，文件中的每条数据都比较长，但是内存只有 $128M$，要如何找到两个文件中数据的交集，我想了个哈希，哈希一个是可以压内存，一个是可以快速判重，不知道这是不是最优解，但相比于前两个问题的回答，应该还是比较可以的吧。最后我的提问部分，问了面试官对我的面试表现的评价（我的每次面试如果让我提问，这是我必问的问题之一），他好像已经被问到好几次这个问题了，很熟练地把问题转移给我，让我对自己的面试表现做一个评价，好了，给自己挖了个坑。

　　最后有惊无险地过了二面，虽然已经比较晚了，但是由于一次面试来回就需要四个小时，所以我仍然极力争取在当天晚上面完三面，但是他们三面面试官八点有事推掉了，跟他们约了周五下午两点，也是现场面试。

　　周五早上 $9$ 点，突然接到美团的电话，表示计划在早上就结束所有面试，让我 $11$ 点到，我马上跟老师请了个假过去了，到光谷已经 $10:30$，肚子饿得咕咕叫，本来打算买点水或者面包休息一下，他们又给我打了个电话催了一下，我就什么都不管加速骑过去了，$11$ 点整正好签到。

　　三面已经不问技术了，是个素质面，主要考察我是否适合在团队中与别人合作，在碰到困难时我的应对策略，还有我对自己未来的目标和规划，让我期望三年之后我的生活、大学四年除了打比赛碰到的最大的困难之类的，我感觉得到面试官想要看到的是一个有很强的上进心的人，我尽力表现出面试官期望的样子，但是那样也太 $fake$ 了，我自己都能感觉得出来，我能从我的面试表现里看到的只有虚伪，这不是真实的我。

　　最后终于放弃了挣扎，三年之后我的生活吗？一份比较轻松的工作，朝九晚五，有时间做自己想做的事情，学自己想学的东西，我那时的状态是两眼无神，说话不带脑子，像在梦游一样。面试官问我到目前为止拿到的 $offer$ 和投过简历的公司，问我为什么没有投 $BAT$，问我没有拿到 $offer$ 的公司中，最想去的公司是哪家？我没有说自己是因为不喜欢 $BAT$ 而不投他们，我回答最想去的公司是吉比特，如果其他公司给你 $20k$ 而吉比特只有 $10k$ 呢？我依然选择吉比特，选择吉比特的理由，我说的第一句话居然是 $10k$ 已经达到了我的工资预期……最后面试官向我吐槽了吉比特是一家不知名的小公司之后，让我回去等通知了。

　　面试到后面我已经不知道自己在说什么，眼睛快眯成一条缝，看着坐在我面前的面试官一直在高频晃动，就差饿晕在面试官面前了，下楼后赶紧找了一家小吃店点了一碗面。

　　凉了。

吉比特

　　虽然都是在牛客网上找到的公司，但一看到吉比特就觉得很舒服，一个是它的岗位要求：

1. 逻辑力 $Max$，探索欲强，打破砂锅问到底，不破难关终不还；
2. 十足的极客范，对技术有着近乎狂热的痴迷，专业和创造是你的代名词；
3. 如果你在 $ACM/ICPC$ 等编程比赛中斩获过奖项，或对图形渲染 / $AI$ / 游戏物理/程序优化等技术了如指掌，那就更完美了。

这不是……相当于什么都没说？我目前见到过的公司的岗位要求里，只有吉比特提到 $ACM$ 这一点，真的一下子就被吸引了。还有一点就是它在厦门有分部，正好我老家也在福建，如果进了这家公司的话，工作起来就爽多了。

　　$9$ 月 $3$ 日的笔试，题型为选择、填空、编程大题，按惯例先做了编程大题，第一题数据范围只有 $1000$ 直接 $O(n^2)$ 暴力，虽然后来发现 $O(n)$ 可以过，但是笔试的时候没想它是不是对的，反正代码短就是写得快，暴力就是稳。第二题是定义一个数字是 $2018$ 数：这个数字的 $10$ 进制表示中，含有 $2018$ 子序列，如：$2301488$，的第 $1,3,4,6$ 位就分别是数字 $2~0~1~8$，允许重复，但不允许交换数字位置，如 $8102$ 则不含有 $2018$ 子序列，问从 $1$ 到 $n~(n\in[1,10^{18}])$ 之间，有多少个 $2018$ 数。虽然之前写过数位 $dp$ 的题，但都没有独立通过，都是 $shz$ 帮忙 $debug$ 完过的，就很虚，先写了一发加了优化的暴力，通过 $0\%$，只能硬刚数位 $dp$ 了，这题大概是我独立通过的第一道数位 $dp$ 吧，过的时候还挺兴奋的，这题过了就能拉别人很多分。

　　然后是选择题，数据库计网 $C^{++}$ 语法相关的问题都没有，都是算概率、算法和智商题，有一道卡特兰数（$6$ 对小括号问能够构成多少个合法的本质不同的括号序列），递推式和证明过程都给忘了，当时也没有推出递推式，放弃了那题。填空题是好几道看代码填输出，每道题六七十行代码，有递归有 $dp$，除了前面两小题，后面的题目其实都不能完全看懂代码要做的是什么，一路猜下去，时间到了，最后剩下两空没填。

　　做完这个笔试感觉神清气爽，整场好像都是在面向 $ACM$ 出题，特别是那道数位 $dp$，为了找工作而临时刷 $leetcode$ 的，哪有多少人能刷到数位 $dp$ 的。总之这场笔试做下来，对这家公司的好感又更强了，美团的面试就是在这次笔试之后。

　　在吉比特校招群里，很多人是因为从小玩问道而很喜欢吉比特的，有的是因为吉比特是一家开的薪资比较高的公司，有的是因为吉比特是一家很有态度的公司，我就属于第三类，以及吉比特对 $ACMer$ 特别友好。

　　面试是 $9$ 月 $17$ 日吉比特来武汉宣讲的时候（$18$ 号开始宣讲，参加宣讲的算是第二批了，第二批参加的是现场笔试），在 $HR$ 面之前只有一面。

　　公司介绍了半小时之后，就开始面试，我是第一波通知进去面试的，先问了一下笔试题数位 $dp$ 的思路，大概是看看有没有作弊之类的吧，没什么问题。然后要求手写一下 $O(\sqrt n)$ 暴力筛，只要求输出 $100$ 以内的素数，其中有个地方习惯性地写

for(int j = 2; j <= i / j; ++j)

面试官就提了一下说乘法更快，我解释说是为了防溢出，$100$ 以内的乘除法防什么溢出……他继续把这个问题延伸：实际上每次判素数不必达到 $O(\sqrt n)$，如果把之前求得的素数存下来的话，可以直接判 $i$ 是否是小于它的所有素数的倍数可以更快，在这种优化的基础下，问如果要求输出 $2^{32}-1$ 范围内的所有素数，需要的最小内存是多少？我第一反应就是小于 $n$ 的素数个数约等于 $\frac{n}{\ln n}$，在这个结论上绕了半天，尽管面试官反复提示这个问题不需要借助数论的知识，只从当前给出的方法来想这个问题。后来我才发现题目要求是输出所有素数，而不是储存所有素数，所以对于每个数字，只要能够判断它是否是个素数，就能满足判断能否输出的要求了，因此是空间只需要 $O(\sqrt n)$，总 $2^{16}\times4$，面试官再次提示后发现其实只需要 $2^{16}\times2$（用 unsigned short）。还能不能再少呢？再少……就用容斥了，最开始选了 $2$ 和 $3$（把 $2$ 和 $3$ 的倍数删掉），面试官又问能不能再少（我可能没答到点上……），我没想到其他的方法，就又选了个 $5$，反正选的素数越多能省的空间越多……面试官看我貌似没法再往前想了，就让我估算一下大约能节省几分之几的空间，我写了个公式：$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}-\frac{1}{6}-\frac{1}{10}-\frac{1}{15}+\frac{1}{30}$ 给了面试官，他只要让我给个结果就行了，其实这个计算也不是很复杂，不知道为啥当时就是觉得计算结果放到计算器上一按就出来了，没必要算，现在想想，这个面试官还是比较重视口算能力的——他看我死活不去算，这题就勉强算过了吧。

　　第二题是给出下面这张图：

分析小球下滑的过程，只要个思路，不用写草稿。嗯，是个口糊题，我大概从两个方块的受力变化，再搞个水平方向的分力算一下两个方块的加速度然后假设由于方块和地面之间存在摩擦力，小球落地前一直没和两个方块分开，就搞一个积分方程，就没了。面试官又问如果地面和方块之间没有摩擦力呢？我……第一个想到能量守恒，不过放在这里好像没什么用，然后就说它们可能向两边翘起来，很难分析，就混过去了。

　　第三题让我估算 $\sin 0.0001$，可以保留到小数点后两位，当时一看懵逼了，这个对估算能力要求也太高了吧，画了两下图发现这个角很小，就是 $0.0001$，保留小数点后两位这个坑设得好啊……面试官接着问原因，就回答了 $\lim_{x\to0}\sin x\approx x$，又问这个公式怎么来的，就是泰勒展开到二阶无穷小，然后他就让我将 $\sin x$ 在 $0$ 附近泰勒展开，展开之后结果就是 $x$，他又让我展开到三阶导，就再减个 $\frac{x^3}{6}$。

　　问了我学过离散数学没，学过，第四题就问 $F\to T$ 是真命题吗？是，为什么？只记得是“$A\to B$ 等价于非 $A$ 或 $B$”，但是一写出来不对啊，$┐(A\vee B)$ 的真值表好像不太对，化了半天才想到 $A\to B$ 只有在 $A=T,B=F$ 的时候为 $F$，才推出来 $┐A\vee B$，上面那个式子去个括号就行了，真的蠢，接着让我举一个实际的例子来说明 $F\to T$ 是真命题，没想出来，放弃。然后用与非式表示 $A+B$，$5$ 种基本逻辑运算符最少用几个可以表示所有的逻辑表达式之类的，都是考基础知识。

　　再往后就是素质面的套路题了，还问了一下 $ACM$ 经历，然后 $HR$ 面，第一次 $HR$ 面，之前听说进 $HR$ 面就稳了，所以就感觉很轻松。一开始先介绍了一下自己的公司和公司文化，问了我找工作主要考虑的是哪几方面，然后问我在学习之余做什么（追剧看电影），追什么剧（刚追完琅琊榜、大军师司马懿），那不是去年的剧吗，喜欢看古装剧？（我可能追得比较慢，只看口碑好的）然后问对滴滴的事情怎么看，总的意思是滴滴仍然很有希望，它确实给我们带来了极大的便利，一段时间整顿结束后，我仍然会使用滴滴。然后就是唠家常，最后问一下薪资预期，就结束了。

　　商量薪资的时候觉得反正游戏公司就是有钱，而且后来群里有自曝 $10$ 多 $k$ 的，一直觉得没什么，直到知道有一个少更多得多的（也是游戏研发岗），才发现原来他们这次开的薪资是这么高的，总之就是对这个薪资越来越满意。因为他们是从厦门过来的，只在武汉待几天就到下一站宣讲去了，所以商量完 $offer$ 就急忙让签了双方，当时头条才刚过一面，进不进头条还没什么把握，而且 $HR$ 小姐姐也非常负责任，自己对吉比特的印象也特别好，又在厦门……总之各种好，很快就签了。

　　签了吉比特之后，对吉比特特别满意，自己也变懒了，不想再面其他公司，后来的笔试面试通知，除了头条和网易互娱都直接拒掉了。

头条

　　之前一直听说头条里面很多 $ACMer$，所以像我这样大学只打 $ACM$ 其他什么都没学的，可能也可以进吧，就对头条很有好感，而且据说白菜价一年 $30w$。

　　头条每次笔试都是五道编程大题，开始第一周笔试的时候我还没反应过来，一道貌似是背包加滚动数组的不会做，我是第二周才开始投简历，笔试过程中摄像头坏了，画面就一直卡在那里，估计最后被判为作弊了，没有过（因为和我一起笔试的其他同学的分数还没我高，也进了面试）。真的是福祸相依，第二周的笔试超难，我只有两题满分，其他题分数都没得全，第三周的笔试就又超简单了，最后一题虽然考 $Tarjan$ 但是是原题，详见 Popular Cows，刷过 $Tarjan$ 的应该都做过吧……一小时五题全过就交卷了，感觉之后面试成绩的参考，也和这次笔试成绩有些关系吧。

　　牛客网上的视频面试，一面的面试官有点皮，一直没露面（我最开始以为所有面试官都是这样不露面的）。先来一道 $dp$，有 $10$ 个格子排成一行，编号为 $1$ 到 $10$，一个人最开始站在编号为 $1$ 的格子上，每秒可以从当前位置移动到左边一格或右边一格，在位置 $1$ 时左移一格可以到达 $10$，在位置 $10$ 时则可以右移一格到达 $1$，问从 $1$ 出发经过 $n$ 秒可以回到 $1$ 的方案数。用 $dp[i][j]~(i\in[1,n],j\in[0,9])$ 表示第 $i$ 秒时到达位置 $j+1$ 的方案数，初始状态为 $dp[0][0]=1$，然后递推就行了，发现 $dp[i]$ 的方案数只依赖于 $dp[i-1]$ 的方案数，所以可以用滚动数组来维护，时间 $O(10n)$ 空间 $O(20)$ 两个 $for$ 循环没什么问题。然后就是 $C^{++}$ 面经问题，看了面经的都会，计网数据库操作系统不会，跳过，最后让我介绍一下我觉得最牛逼的项目，就介绍了一下扫雷和一些改进，就没了。面试官对我的评价是在有优势的地方很突出，但是弱点也很明显，不知道我后面会怎么样，一面这里他先让我过，一个工作日内会给我答复。

　　中间穿插了吉比特的一次面试和签双方，签了吉比特之后，对头条所抱的期望已经没有那么大了，毕竟已经对吉比特很满意了，再继续面头条，只是为了看看自己的实力在头条能走到第几面，抱着的是能过则过，过不了算了的心态。

　　可能是因为我在笔试和一面的时候代码能力比较突出，二面的面试官只给了我一道码农题，写完二面就结束了——实现一个简单的 $Html$ 语法检查器，因为有过一次 $bilibili$ 笔试经验，所以这次在写之前就不用考虑很久，在写的过程中我多次向面试官提问，这种情况属于存在语法错误吗，那种情况需不需要考虑……代码写到快结束的时候，才发现我考虑的比面试官提的要求要多得多，要是一开始就完全地了解面试官想让我实现的大概是什么要求的话，我可能二十几分钟就写完了，最后写了四十几分钟才写完，感觉这个时间真的有点长。提交的时候通过了所有的测试样例，除了完成的时间，我比较关注就是这个，就相当于看我的代码是否 $AC$ 了嘛，但是面试官好像不是很关注这个，最后还是一天内给我答复。

　　感觉二面基本凉了，只给了一个问题，我还写了那么久，我也没跟面试官说我的代码能够检查的情况比给出的条件要复杂得多，所以写了很久，什么都没解释，可能面试官就会觉得我的代码能力其实也不是很突出，就完了。第二天 $HR$ 小姐姐通知我进了三面，我还是有些意外惊喜的。

　　三面的面试官就有点帅了，第一道还是编程题，面试官可能以为我做过，所以就直接说出来是 $leetcode$ 原题，就是一个序列，序列上的第 $i$ 个数字表示这个位置有一个高度为 $i$ 的柱子，问在这样的柱子分布下，如果下雨了，最多能够装下多少体积的水（如下图，蓝色部分表示积水）。

　　想了个单调栈的做法，从左往右扫的过程中，每个柱子的左边如果存在一个比它矮的柱子，这两个柱子之间一定有积水，积水的宽度可以用下标相减得到，积水的高度就减去上一次计算积水贡献的高度就行了，每次要快速得到上一个比自己低的柱子，就是用单调栈，从左往右维护一个单调递减的栈，空间和时间都是 $O(n)$ 的。面试官问能不能用 $O(1)$ 的空间，就是类似用两个指针扫一遍，想了半天没想出来，还是面试官说了解法，这个图有一个性质就是如果某个柱子的另一边有一个比它高的柱子，那这两个柱子之间所有比它们矮的柱子上方一定有积水，然后两个指针分别从头尾扫到中间就行了。接着面试官问，如果要从这些柱子之间选取一个位置切开，使这些柱子分成两部分，应该选哪个点切开，才能使得剩下的柱子能够装下的积水体积最大，比如上面这张图就可以选 $10$ 和 $11$ 之间，或者 $11$ 和 $12$ 之间，正好我的做法是单调栈，第二问直接从左往右和从右往左各扫一遍，就可以得到到达第 $i$ 个位置时能够装下积水的最大体积，然后 $O(n)$ 枚举切点就可以了，最后代码实现没什么问题。

　　第二题是，如果要从网上爬取大量的网页，如何判断当前爬取的网页是否已经爬取过，第一反应计算机网络相关，直接放弃，面试官又说其实这个和计网没什么关系，是一个应用算法的题，我才继续想这个问题，想到字典树，面试官又说了字典树的倾斜问题，比如 baidu 域名下有很多链接，但是一些小网站可能就没那么多，整棵树就会往以 baidu 为根的子树倾斜，后来说了哈希的方法，并且表示让我不要那么轻易放弃……然后就是关于哈希的一些套路问题，常用哈希算法啊，冲突的概念啊，解决哈希冲突的方法啊之类有标准答案的，然后问哈希是如何实现动态开辟空间的，突然愣住，想了半天……面试官提示有一个填充因子 $\alpha$，我才反应过来好像有一个哈希效率和空间利用率最高的理论值，只要储存个数与总空间的比值超过这个数值，就需要重新分配空间。最开始想了半天是想哈希动态开辟空间的代码是如何实现的……

　　第三题是二叉搜索树平衡树红黑树之类的东西，都是有标准答案不需要动脑只要能记下来就行的，就不提了。最后问了一些素质面的内容，周围的同学怎么评价我的啊，关于秋招花了多长时间来准备啊，有没有去自学过数据库之类的课啊，等等等等。后面的问答就比较随意了，不知道面试官是不是有什么其他事情要忙，总之问得很快，好像也不是很关心我的回答是什么样的，最后表示其实他提的问题都比较偏向思维方向的，然后告诉我三个工作日内会给我回复，就很快结束了面试。

　　回想面试的过程，面试官提的需要思考的问题我都没有给出最优的解法，而且面试官还经常给我提示，可能觉得我思考的时间太久了有些不耐烦，还有我那道哈希的题目居然直接放弃了，面试官会觉得我是个轻言放弃的人吧？在“周围同学怎么评价我的”这个问题上，我居然说了一条“智商高”，对另一个程序员说自己的智商高，会不会让他觉得很傲慢、不谦虚呢，而且最后提问得那么随意，好像已经确定我要被刷的样子，不想再多浪费时间了。之前看群里说头条的面试都是五面起步的，这才三面就从一个工作日内回复改成三个工作日内回复了，越想越觉得自己凉透了。

　　三个工作日过去了，没有任何回复，真的凉了，有些不甘心，难受啊。反思一下，一方面我真的除了代码能力，什么都不会，要说还有什么优势，就是思维比别人快一些了吧，但是在三面的时候表现得也很糟，从笔试满分到三面凉透，有种泯然众人的感觉。只能用“头条加班多，不去也罢，至少还有个吉比特”来安慰自己了。

　　头条三面，就是国庆前的最后一场面试了，既然决定是吉比特了，那国庆回家就把这个消息告诉家里人吧，家里人当然很高兴啦。我妈之前跟我说我要么毕业后去当老师，要么去考研计算机，现在研究生满大街都是，我一个本科生怎么会有竞争力，知道我找到工作后，就没再继续劝我了，正好带了女朋友回去，家里人聊天大概就围绕在“女朋友的工作地点”、“结婚”和“买房”这三个话题上了。

　　国庆结束后，回一中监考了两天的月考，周二吃晚饭的时候，头条突然来电话，因为投了简历最近很多招聘的骚扰短信和邮件，一开始没听清公司名称，以为现在这些公司都开始打骚扰电话了，差点要挂掉。知道是头条后，第一反应就是，头条又把我从备胎池里捞出来了吗，$HR$ 小姐姐让我拿张纸记一下，大概就是说一下薪资待遇和工作时长，一听感觉不对，怎么我的薪资比白菜价还低这么多（当时以为头条白菜价 $30k$），然后就跟她说“我知道自己在面试过程中除了代码能力其他方面的知识也有欠缺，表现不如其他同学那么优秀，但是……（后面就是用客气的说法表示我的薪资比白菜价还低）”$HR$ 小姐姐表示应该是我听错了，白菜价是 $30w~/$ 年，然后就解释我这个薪资比研究生还高，是靠能力而不是靠学历争取来的吧啦吧啦……他们特地申请了这个薪资，所以导致没有在三个工作日内及时给我回复吧啦吧啦……感觉得出来 $HR$ 笑得很开心的样子，所以我也用笑得很开心的语气和她通话，其实心里想的是“信你才怪嘞，一句话也就半句是真的，反正我已经决定去吉比特了。”她还问了我是否有拿到其他 $offer$，$HR$ 说了头条相对于这两家的优势吧啦吧啦……最后我表示要和家里人商量一下再定。

　　晚上跟同学聊才知道原来头条 $HR$ 说的都是真的，突然就很开心，聊了一小时左右，又恢复了原来对头条的喜爱。这时候才开始纠结是头条还是吉比特，总之过程是很纠结很纠结，周三早上我给头条 $HR$ 发了一个很长的感谢信拒绝了头条，她邀请我周五去公司一趟，我觉得可能是我的态度不够明确，又写了一封准备在说不过她的时候拿出来给她看。周五去头条的时候不是 $HR$ 跟我聊，是我的主管（如果我最后进头条的话他就是我的主管了）——也是我二面的面试官跟我聊的，他的话多一些，我的话少一些。

　　我把我要表达的跟他说清楚了，他也跟我说了在面试过程中给我开的绿灯啊（那三大块的知识完全不会），对我的性格评估啊，发现我是一个有特点的人啊，有些人都已经有过实习经历可以直接用，我却还有很多东西要学啊，看中的我是的潜力的啊之类的，总之他们在给我面试的过程中是做了很多我不知道的工作。直到晚饭的时候我才见到我一面的面试官（就是那个给我视频面试一直没有露面的），他见我第一句就是为了捞我费了好大的劲啊，哦吼吼，有意思。

　　终于写完了，从 $10.9$ 结束秋招，$10.17$ 开始写到 $10.24$，这之间我的心态也发生了一些转变，最开始觉得 $sp$ 很难得有多厉害，还兴奋了好久，后来看了牛客网上一些别人的面经之类的，又感觉满大街都是 $sp$，比我优秀人多了去了，满手都是 $sp$ 的大佬也不少，大佬的 $offer$ 都是 $7~8$ 个地拿，而我才到第 $2$ 个就已经开始怠惰了，现在有些后悔咕咕咕掉网易互娱的面试，网易毕竟也是一家大厂，而且我一面的表现也不错，为什么不看看最后自己能到几面，能否再拿一个大厂的 $offer$ 呢。还有欢聚时代、爱奇艺、虎牙、小红书，$360$……这些之前海投了，却在拿到吉比特之后咕掉的笔试面试通知。投的大厂还不够多，一方面是海投的时候天天只看牛客网上的求职栏，一方面也没去了解有哪些大厂，见的世面还不够多。

　　本以为毕业后找个工作，没了 $ACM$ 就没有学习的目标了，每天写写需求拿点工资能过活就行了，现在看来，我好像又有新的目标了，那就这样吧，等着和优秀的人一起做有挑战的事。