20Fall留学渣渣的后端春招总结

情况介绍

先说一下拿到的offer情况吧：投了6家实习，都是内推。其中鹅厂和亚麻没有回音，福报厂明确回应不要大四实习生。剩下三家都拿到了offer，按顺序排如下：

百度，核心部门，全职，白菜
猿辅导，不知道是不是核心，实习
字节，非常核心，全职，sp

疫情 + 川皇搞事儿

本人大学期间十分蔡，申请到的研究生学校也比较一般，但是离硅谷近，所以还是挺满意的。
可惜疫情影响 + 特没谱似乎想对留学生开刀（尤其是最近那个对留学生的限制政策，本人的本科大学不小心上榜了，very high， top secret了解一下）于是决定推迟半年入学，下半年在国内找实习。
这应该是目前大部分留学生面临的处境。我因为做准备比较早，从4月中旬就开始刷题准备找实习，所以在风暴来临之前成功上岸。但是眼看着形势越来越差，啥时候能出国越来越渺茫，就在已拿到实习offer的情况下，提出转校招，运气好拿到了不错的offer，所以美研梦暂时是碎了...但是不管形势如何发展，和我情况一样的准留学生同学也请尽快行动起来，越早越有主动权。这也是我写这篇面经的原因，希望可以帮助到更多的人。

提前声明：本人本科期间代码能力还不错，有专业课基础，所以复习方法可能不适合所有人，请根据自己情况酌情观看。
这篇中不涉及基础知识问到哪些，因为我不记得了...只有算法，大伙儿将就着看。不过说实话，我个人感觉，面经里的算法题看看就好，毕竟每个人遇到的题不一样。比较有价值的部分，可以看我最后给出的复习与准备面试的建议。

字节面试两次，共8轮技术面 + HR

一战：

第一次学长内推了自己部门，没有后来拿到offer的这个部门核心，但也算是个核心，跪在了第三轮。

一面：Add up two numbers + 口述LRU实现

很简单没什么可说的

二面：Three Sum + Intersection of k vectors

3Sum用了Sort，3 pointers的那个方法；
第二题是分治，nlogn

三面：快速查找IP + 虎吃羊 + Friend Circle

第一题是前缀树；
第二题是智力题：有n虎1羊，老虎吃了羊会变成羊，并且这些老虎很聪明，不想被别的老虎吃。那么有n只虎的情况下，老虎会不会吃羊；（分奇偶数）
第三题我给了DFS，但是写法过于繁琐，而且面试官非常expect我给出并查集的解法，我当时没有复习到，所以凉了。不过这也给了我第二次冲击更核心部门的机会。

二战：

这一次第三轮面试完之后，我问HR能否校招，于是很开心地被加了两轮面试呵呵...不过最后一面应该是为了评sp，正常情况应该面不到5轮技术。

一面：Reverse List + Find Kth Largest Num

第一题真的太常见了，建议练到滚瓜烂熟；
第二题用了快排Quick Sort，一般面试官应该不接受Priority Queue的解法；

二面：迷宫走到终点最少步数 + Implement Queue，using mutex

第一题BFS
第二题没什么好说的；

三面：二叉树最大路径和 + Find Kth num in two sorted array

第一题递归，返回值是该子节点的解；
第二题是真的难，应该是寻找中位数的follow up。我给了two pointers的On，要求logn，最后在提示下写出用k / 2 - 1作为边界的二分法；

四面：Trapped Rain + 迷宫中到达终点的路径数量，只能右or下，1代表墙（follow up限制拐弯次数）

第一题用了左右两个指针；
第二题一开始是用了动态规划，加了额外条件以后用dfs，传参记录拐弯次数。还被问了在dfs情况下如何进一步提升，答用空间换时间，memo数组用来剪枝。

五面：聊项目 + 教室里座位

这一面没手撕，聊了非常多，深挖了项目中很多细节，然后面试官非常喜欢拓展，比如“那如果有xxx的限制应该怎么实现”这种问题，所以没有参考价值，纯看技术积累 + 反应，思维能力；
聊得非常愉快，最后还有一点时间就问了一道题口述：教室里n个座位，排队进教室随便坐，求每个同学都不在自己座位上的概率。用了dp，分奇数偶数情况（因为如果第n个人和第n - 1个人互换了位置，那么可以分解子问题）。但是最后面试官提示到可以用二维dp，第二维0和1分别代表有没有发生互换。

字节总结

很看重手撕算法，题目也偏难，这上面很多题都是hard。想面试顺利的话就多刷Leetcode吧。

百度三面

百度的三面约等于没有，聊天环节

一面：判断链表有无环 + Three Sum

很简单；

二面：找到两个相交链表的相交节点 + LRU

第一题的做法是模拟两个链表接到一起，一个A在前，一个B在前，分别前进，在某一时刻会到达相同的节点；

百度的题不难，但是基础知识问的很难，尤其是并发情况（OS相关），二面面试官想让我手写线程池来着，我说我不会才换的LRU...
感觉表现的不怎么样，不知道是三面面试官觉得合适还是缺人，转校招不需要加面。这也是我人生中拿到的第一个offer，感谢百度。

猿辅导

一面：Tree层序遍历 + Matrix找最长连续1 + 用辅助栈给一个栈排序

第一和三题很简单不说了，第二题dfs；

二面：First missing positive num + Find num in sorted array

第一题用swap，把每个数放到对应的下标处，然后遍历找到第一个不符合nums[i] != i + 1的数；
第二题用二分法，讨论每一次二分以后，哪边是顺序排列的，再往下讨论；
面试通过之后，因为别的两家全职offer都拿到了，就没有要求走校招加面。

我是如何复习的？

基础知识

首先基础知识需要因人而异，因为我知道很多出国党是转码的，OS、计网可能都没学过。对于这类同学，不要想着2个月之内找到大厂后端开发实习了，老老实实看网课，啥时候能学完再开始找 or 找非大厂 or 找非后端开发。
对于科班同学，如果没好好学习专业课，同上。如果基础不错，完全不同回去看课本复习。牛客网上的面经足够了，能看多少看多少。不过需要注意的一点是，根据投递的部门不同，有的会要求Linux，有的会要求数据库，建议准备得全面一点。

虽然基础知识很多，常问的也就那些：

C++：多态、vector，hashtable，set/map的实现、智能指针、C++11；
OS：进程线程区别、进程/线程通信、fork、死锁、select/poll/epoll、虚拟内存、用户态内核态；
计网：tcp三握四挥、拥塞控制、time_wait、DDOS攻击原理、http/https协议，cookie/session、输入url发生了什么；
数据库：事务、隔离级别、锁、索引...；
Linux：top/ps、awk/grep、inode、ln...；
总之记住一句话：不会的，就说不会，别瞎说，或者可以这样说：“不好意思这个我之前没有过多地了解，但以我的猜测是这样的xxxxx”
当时字节五面的时候问到了fork中的一些细节，我之前不知道，面试官说没事儿你猜猜，然后我就想了想，按自己的理解说了出来。然后面试官很高兴说我是对的，这个技术叫copy on write，然后夸了我一会儿...哈哈哈...可能这里的思维能力很加分，帮助我拿到了宝贵的sp

算法题

图片说明
如图，我先用一个月的时间高速刷了180道题，然后反复做前面高频题（根据提交次数，我大概刷了3遍）同时再做一些新题保持手感。收获也非常满意——所有的技术面试，只有并查集那一道题我没有写出来，别的都是秒解。

我推荐的做法是这样：

刚开始刷Leetcode的时候，一定会非常困难，但只能硬着头皮刷，因为面试必考。我非常推荐按Tag去刷，效率比较高。Leetcode的explore板块中有分类的入门章节，Tree、String、Array啥的，每个分类刷10道高频题入门，然后根据你想去的公司中出题频率高到低刷就完事儿了。
为了看到出题频率，以及各公司常见题，需要开会员，所以我推荐使用Leetcode国内站，比较便宜...主站的会员我开不起...其实题都是一样的，唯一不同的是讨论区。不过完全可以刷中文站，看英文站的评论区...
前期遇到hard题，跳过。根据我的经验，如果你想找实习，遇到Hard的几率几乎为0
就算是全职，前期去尝试解决hard也不是一个明智的决定。
或者说，入门阶段只做easy都行，达到30题以后再开始Medium。不过Medium绝对是重中之重，高频Medium一定要多刷。
看完题思考的时候，一定要动手，不能空想，效率会差很多...下面是我的草稿纸
图片说明