21届秋/校招面经

开篇先说一下我自身情况，东南大学本科计算机科学与技术专业毕业，gpa3.2/4.8。零零散散搞过一年多ACM，去年（2019）在icpc上海站拿了铜之后增加了信心（因为当时训练总时间半年不到），于是更用心地一直训练到今年六月底，预计比赛差不多上学期没法正经举办之后颓然泄劲，然后开始投入考研，这次秋招打算一是感受一下当前互联网行业行情，二是也希冀能为考研战败捞个后备选项，总共投了四家公司：字节（客户端开发）、腾讯（PC客户端开发）、猿辅导（客户端开发）、网易云（C++开发）。接下来我就按照时间顺序来分别介绍我经历的每一场面试&笔试，以供参考。

字节一面

这个我感觉铁挂了……本来就是抱着试试的心态参与的，什么都没准备。面试官上来问我是不是投的安卓开发我内心：现在客户端开发直接指移动端开发了吗555。然后他就开始提问os和计网的知识，大概有：进程线程区别、进程调度算法都有什么以及区别、http和https的区别、描述tcp三次握手四次挥手以及为什么要握手三次挥手四次、http的get方法和post的区别、tcp和udp区别等。这些我大概还能零零散散答出来一些，毕竟刚复习过这两门课，没答出来的部分是真的因为考试的重点和面试的考察重点不太重合，侧重方面不同，比如为什么握手三次挥手四次我是没做过题。

接下来是关于java的一些问题，我感觉我答的糟透了，问题大多集中在多态虚函数这些的实操以及原理，很多很基础的东西我都记得模棱两可，毕竟最近做过的java课设还是一年前的时候，语法细节根本记不清，遑论概念。然后就被面试官吐槽面哪个岗位就应该提前了解一下相关要求。。

接下来总算到了写算法题环节，不过我也没能发挥出来，估计面试官是觉得我前面太差了所以也 不问我太难的，只是让我写了个排序并且问了如果内存不够把所有数据调入要怎么办。这个时候我已经被打击得无地自容，好像也都是瞎答的。整个面试过程大概30分钟结束。

腾讯一面

这次面试经历算好一些了，有了前车之鉴，就去提前看了一下面经，再加上C++本身也是我写题的主语言所以较为自信。

面试一开始建端自我介绍之后就开始笔试，两道题50分钟。分别是求最少多少线段能覆盖[0, L]范围，和树的按层输出和ZigZag输出。前一道题我半分钟就想出思路先按x排序再用优先队列搞了，可是可能因为过于紧张吧，到最后仍有小逻辑毛病，存在一些反例。第二道题挺简单，Zigzag遍历就是按层一行从左到右一行从右到左地输出，其实就把普通按行输出里面用的临时队列改成临时栈即可，栈能颠倒输入输出次序嘛。这两道题做的结果面试官应该是满意的，就提了一句为啥树不用指针写，我说算法题习惯了hhh，全局数组写起来舒服。

接下来就是考察专业课，依然是操作系统和计网两门，大概问的问题有：os的虚拟内存、同步和互斥、知道哪些操作系统、有没有在某种os上开发的经验呀。虚拟内存这个我回答了就是把硬盘一部分当作内存hh结果被说没在点上，可能是想让回答逻辑地址这个方向吧。http/https区别和get/post区别依然问了，还有http的两种连接方式，一种每传一个对象建立一次tcp、另一个传完再结束tcp的这个，常用端口以及各种返回码是什么意思。整体感觉腾讯这边pc客户端开发很看重http相关知识。最后面试官还让介绍了自己做的最大的项目，我就勉强讲了之前那个java课设哈哈哈，虽然细节记不清，不过整体框架印象还是很深的，毕竟里面有我当时设计了很久的东西。

这场面试感觉还行，算是发挥出了应有水平，除了写题时太紧张导致第一题有错有点后悔，还有一个原因是用的牛客面试网页调试器功能太少，，没有gdb感觉寸步难行，之后可以训练一下无调试切水题的能力。

腾讯笔试

一面之后没过几天就收到了笔试通知。看了笔试说明以后还以为有除了算法题以外的概念题啥的……结果并没有。

整场考试共五道题，难度应该是递增的，知识点范围大概在简单图论、stl使用、dp以及构造。dp题出了一个背包的变种，物品数量和价值相等，然后如果最后背包有剩余，则可放进任意一个物品。大概意思就是最后物品总重量可以超过背包大小，但要满足从物品中去除某个之后，剩余物品重量是小于背包的。这题只过了百分之80……可能还是想法不对吧，看官可以自行思考一下怎么搞。然后说到简单图论题，这题太值得吐槽了，因为它数据没按范围要求给！！本来就是闭着眼睛都能过的图遍历问题，结果直接给我报了通过0%？？？最后想了二十来分钟，实在没方法了就孤注一掷，把数组都开了几倍大，并且数据的标号都按着最大而不是输入的上限看待，然后就全过了。。。至今不知道问题出在哪一块，太锅了这题如果在区域赛出题人能被骂死，，

然后说到第五题，当时因为前面被图论题数据问题把心态搞崩了，就根本没法用心思考。大概是这样：给定一个n，求最大的m使得能构造出一个长为n的数列，使得对于[1,m]中的数，任意两个xy在数列中都有相邻的存在。我大概就是按着上界想的：类似于每两个数据都连一条边，则最少m(m-1)/2条，而n个数据有n-1个相邻关系，相当于提供n-1条边，所以解方程n-1>=m(m-1)/2最后发现全错qaq。

整体得分380/500，感觉放在认真找工作的群体里应该是平均水平吧差不多……算法题技术盲点还是有很多啊，以后还要继续练。

网易云笔试

一道简答题四道编程题，简答题问了大小端和C++虚函数的实现方式，感觉全跪orz，大小端好像写反了，后者不了解。

四道编程题难度分明，前两道是简单递归/树，数据弱的一批；后两道难度极大，我集中精力搞出了第三题，在这里和大家分享：（其实感觉这题够单独开个题解了）：

给一个1e5大小的正整数数组，求出最大的可以被7整除的子集和

乍一看无从下手，我们来慢慢分析。首先对应于整除7这个条件，所有的数可以按模7结果分类，然后从其中找出满足要求的最大组合。我先想了好几种假做法才意识到组合不能贪心做，最典型的一个假做法是16、25、34这样组合233。然后就想到要找出所有的组合路径，觉得需要建图做。就是构建7个点代表当前结果模7的值，然后连边（i，j）表示所有模7=j-i的数组数值，这样从0出发经过若干条边（总和y）到达x（每条边只能使用一次）时，代表可以找到权值和为y的，且模7等于x的子集和。于是更改思路为求出所有数的和sum，然后减去模为sum%7的最小子集和。这样就变成了最短路问题：设sum%7=x，sum-则0到x的最短路即为所求。

至于如何求这个最短路，需要魔改一下Floyd算法，之前最外层是所有点，内层是遍历两层用它当中介的点。现在我们把外层当成所有数组数据，因为是求最短，所以每种模值下最多取7条边就够了，然后每种模值内从小到大遍历边；内层就取该边的模值在图中对应的边，然后再遍历一个顶点作为该边松弛操作的前一个/后一个点。四层遍历共7^4解决。贴下代码

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=1e5+4;
vector<int> shang[7];
int a[maxn];
char s[maxn*10];
int es[7][7][2],val[7][7];
int main(){int n=0,cur=0;cin.getline(s,maxn*10);for(int i=0;i<strlen(s);i++){if(isdigit(s[i])){cur=cur*10+s[i]-'0';}else{a[++n]=cur;cur=0;}}a[++n]=cur;int ans=0;for(int i=1;i<=n;i++){shang[a[i]%7].push_back(a[i]);ans+=a[i];}for(int i=1;i<=6;i++){sort(shang[i].begin(),shang[i].end());}for(int i=1;i<7;i++){int cur=0;for(int j=0;j<7;j++){es[i][j][0]=cur;es[i][j][1]=(cur+i)%7;cur=(cur+i)%7;}}memset(val[0],inf,sizeof(val));for(int i=0;i<7;i++)val[i][i]=0;for(int i=1;i<7;i++){for(int j=0;j<min((int)shang[i].size(),7);j++){for(int k=0;k<7;k++){for(int a=0;a<7;a++){val[a][es[i][k][1]]=min(val[a][es[i][k][0]]+shang[i][j],val[a][es[i][k][1]]);val[es[i][k][0]][a]=min(val[es[i][k][1]][a]+shang[i][j],val[es[i][k][0]][a]);}}}}ans-=(val[0][ans%7]);cout<<(ans>0?ans:-1)<<endl;
}

猿辅导笔试

时间真心短……一个半小时15选择3编程题，选择考了数据库、概率论、计网、os，很有特色。

编程题码量不小，这应该是我做的最惨的一次编程题qwq，一个小时就写出一道半。第二题是模拟表达式运算，规则很繁，没状态耐心调试最终只过了40%，第三题瞅了一眼好像是字符串类dp没时间想了……哎也许最后二十分钟应该放下第二题去冲最后一题的。策略问题。