推荐搭配 面试相关知识 食用。

2020冬 字节跳动北京 电商后端 日常实习

职位链接 (opens new window)

第一面

面试官因为开会迟到了十分钟（没敢问是不是因为 ByteDance 会议太多了 hhhh），然后他电脑不正常，再重启直接黑屏了（太惨了）。
HR 跟我打电话约下次再面，半个小时以后又说电脑修好了可以面了 hhh 这就是我的人生第一面吗

1. 自我介绍

常规题。一定提前写稿子/写提纲。

2. 介绍项目和一个最难的部分

了解到我学过计网、数据库、操作系统以后，就考了这三科的知识（看来实习面试还是挺有弹性的）

3. 操作系统中，用户态和内核态的区别、这样有什么好处

4. 操作系统中，线程和进程的区别

话说这一问还可以多答一点，比如：进程会创建进程控制块 (PCB)，而线程是线程控制块 (TCB)。由于线程没有父子进程、资源控制等结构，所以 TCB 比 PCB 简单得多，这也导致线程的创建比进程的创建快得多，大概有一个数量级的区别。这也是平时开发中，为了利用 CPU 多线程，我们常使用多线程开发，而不是多进程开发的原因。

1. 计算机网络部分：用户从输入 url 到获取到信息过程中发生了什么（越详细越好） a. DNS 解析的过程：计算机先检查 DNS 缓存，如果没有缓存则向 DNS 服务器查询域名对应的 IP，查询的过程分为迭代和递归两种方式；面试官接着问了 DNS 基于什么协议，答案是 UDP，服务器一般使用 53 端口 b. 获取到 IP 以后向路由器发包、路由器根据路由表和选路算法进行转发的过程；面试官又问了有那些选路算法（分为域内和域间路由算法，域内有链路状态 LS 和距离向量 DV，域间有 OSPF 和 RIP）；以及路由表的最长前缀匹配原则； c. 再往上就是 TCP 和 UDP 协议了；经典一问：TCP 和 UDP 的区别（TCP 面向连接、拥塞控制、流量控制），顺便还简单问了一下拥塞控制； d. 然后就是 tls 协议； e. 再往上就是最后的 HTTP 协议了。

2. 对 HTTP 状态码的了解

我答了 200、301、302（追问了一下 301 和 302 的区别，以及 301 的实现 我答的是浏览器的实现，复盘的时候觉得他可能是问的 Nginx 的实现？不太明白）、400、403、404、500（追问了一下 502 和 504，但是不大了解，复盘的时候才知道 502 就是 Bad Gateway，504 就是本地代理挂了然而 V2Ray 就是返回 500）

复盘的时候就系统的了解了一下，写了一篇博客

7. 数据库部分，先问了复合索引的知识：若有索引 a, b, c，查询 WHERE a > x AND b = y 能否命中

答案是不能，因为 a, b, c 的含义是先按 a 排序，a 相同的再按 b 排序，这只能命中 a = x AND b > y 的情况。

8. MySQL 数据库中的事务隔离性如何保证

哇这部分没咋学，考前三天学了，现在早忘了（）

事务需要提交也忘得差不多了，脏读、不可重复读、幻读、丢失更新只记得个名字了。

解决办法也是只记得二段锁的名字，还有一个严格二段锁和强二段锁的名字了。不过由于时间关系，面试官就没有深入追问了。

9. 在一个圆里随机取n个点，它们在同一个半圆的概率是多少？ (opens new window)

想到了第一个点定下来以后，之后的所有点选到同一边的概率是 $\frac{1}{2^{n-1}}$，但是一看 $n=2$ 时就不对，就凉了。

复盘的时候一看知乎，原来每个点都可以成为第一个点，再乘一个 $n$ 就可以了，答案是 $\frac{n}{2^{n-1}}$。

10. 缺失的第一个正数 (opens new window)：给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。要求时间复杂度 $O(n)$，空间复杂度 $O(1)$。

这题一看就是套路题，我印象中好像做过，但是忘了 GG。

最后还是想起来了（又或者是我自己想出来的呢哈哈哈），不过写了个错误的置换算法，应该 while 的地方我写的是 if。不过样例过了，而面试官似乎也没看出来有问题。

11. 你对我有没有什么想问的

问了问他们部门是干什么的，没想到面试官就开始跟我侃侃而谈，了解到了抖音原来在为直播带货打造电商平台，不然就只能引流到淘宝京东了。也是，我投简历的时候也觉得很奇怪，为什么字节跳动要搞电商，还以为有新的 pdd 呢。

顺便问了一下为什么只要求 PHP、Go、Java、Python、C/C++ 等任意一门编程语言，难道部门里这些语言都会用吗。面试官说，组里一般是用 Go 开发，但是允许进了以后现学，所以不要求有 Go 基础。

总结

第一次面试，没想到都是问的一些多多少少有学过或了解过的专业知识，所以也没有那种问一些完全没听说过的东西。

总的看来，对于本科实习生/应届生应聘后端岗，除了数据结构和算法以外，计网、数据库、操作系统很重要，还得好好复习。（计组、汇编什么的偏硬件了，就不用了 2333）

这次的面试一面就没过，看来还是太菜了（也可能是概率题、编程题都没做对叭）。有时间最好把计网、数据库、操作系统补一下。

2020冬 腾讯深圳 后台开发 日常实习

职位链接 (opens new window)

第一面

1. 自我介绍

2. 给定数组，除了一个数出现一次外，所有数都出现两次，并且所有出现两次的数都挨着（不过面试官并没有明说题面，只是给了一堆数）。请找出找出那个出现一次的数。

我以为是 落单的数 I (opens new window)，兴奋到没有观察到“所有出现两次的数都挨着”，即答异或，$O(n)$ 空间复杂度。

面试官问我时间复杂度能不能再低一点，我直接懵掉。面试官就让我直接看下一题了。

然后面试结束以后五分钟就想到了 GG

可参考落单的数 IV -LintCode (opens new window)，不过这题似乎 LintCode 删掉了，LeetCode 也正好没有这题。可能是版权问题？

3. 最大子矩阵 (opens new window)。这题目很眼熟，但是我复杂度一直算不对，面试官一直在纠正我（太菜了

面试官先让我说暴力的时间复杂度，我即答“枚举左上角和右下角，共$O(n^4)$”。面试官反问那计算矩阵值呢？我忘算了，应该是$O(n^6)$。

然后说优化，我想到了二维前缀和。前缀和的过程是 $O(n^2)$，所以我又即答时间复杂度 $O(n^2)$。后来面试官问算完前缀和然后呢，我一想还是得枚举左上角和右下角，是 $O(n^4)$ 的。啊这

面试官让我写一下由二维前缀和求矩阵的表达式，大概就是 ans[x1][y1][x2][y2] = cumsum[x2][y2] + cumsum[x1][y1] - cumsum[x1][y2] - cumsum[x2][y1]。这个没问题。

然后面试官说能不能再优化时间复杂度。我想了一下，应该是类似于最大子序列和 (opens new window)的思想，把枚举遍历变成最大子序列和的 dp 方法。在一个方向上用这个思想优化应该挺容易，在另一个方向上还能优化吗？我边说边想，面试官说不用了，优化到 $O(n^3)$ 已经可以了。

感情我之前答错时间复杂度成 n 方的时候，他以为我发现了一个什么 nb 的算法啊，怪不得还让我详细讲讲

4. [LeetCode] 505. The Maze II 迷宫之二；现在 LeetCode 上已经要收费了，看看别人的博客凑合吧。就是非常基础的 BFS/DFS。面试官让我实现了一下。虽然没有一遍过样例，但还是靠 cout 调试法调试过了。

5. C++ 特性 shared_ptr 不了解（我 C++ 学完类以后就一直在用 MATLAB 和 Python 了）

6. C++ 特性 vector 前面那个我就没听清，这个我也没听清是什么，干脆直接回答不知道得了，后来复盘的时候突然发现原来他写了。。。而且我还真会。。。

7. 线程和进程的区别 经 典 复 现（见 2020冬 字节跳动 电商后端 一面）

8. 然后就是问了一下之前的项目经历，有的会问的比较细节，比如五子棋 AI 的决策树一共写了几层。看来有时间还得得复盘项目。

---

总的来说，

1. 得找时间复盘一下之前写的项目了
2. C++ 特性也得学，之前学完 C++ 课以后，就滚去搞算法和数模了，都没有深入 C++ 了（诶我不是面的后端吗 为什么要问这么多 C++ 特性）

第二面

1. 自我介绍

2. vector 变长数组的实现？

大概就是涉及到动态扩容到一个新的区域，然后将原来的东西拷贝过去。然后接着问，能不能自己设计一个不需要反复拷贝的变长数组。emmm 我答了一个类似于二级页表的结构，不过第二层是元素的数组而不是指针的数组。

没有写代码，但是面试官问能不能释放空间呢？我说不大能删。不过复盘的时候突然想到，可以完全使用页表那样的指针实现。需要释放空间就可以释放掉了。

3. 148. 排序链表 (opens new window)。

对链表进行排序，其实就是归并排序嘛。之前大概知道是用归并，不过没有写，之前也没有写过。

实现上，要从链表结点的结构定义开始写，所以写了一会。索性花了整整 45 分钟，借助 cout 调试法（牛客的网页 IDE 不允许断点调试），最后写出来了。第一次就写出来了，还是蛮有成就感的。

4. 50. Pow(x, n) (opens new window)。其中保证 $n$ 是整数。注意，如果出现溢出，就输出最接近的一个 double 值。

原题我做的很顺，但是判定溢出以及最接近值我真不会。于是问能不能搜，说可以。于是在 power 函数中 return ans; 改为了：

return isinf(ans) ? (std::numeric_limits<double>::max()) : ans;

不过由于时间关系就没有写 min 的情况了。

另外就是，我本来是用一层递归搞定了负次幂的情况，但是他说最好不要递归。未免太严格了吧。

最后就是 testcases 的问题，让我自己写一堆 testcases，自动判断正确与否。虽然当时想的是简单测一下就交，没想到这里。确实，学到了学到了。

5. 谈谈你对自己优点、缺点的看法。

啊这，套路题了。但是我没准备，只随便答了一点。下次一定准备。

6. 你有没有什么想问的

---

这次下来全是算法题，没有考计算机专业的其他东西。不过 testcases 确实受益匪浅。下次一定用。

总结

最后还是通过面试啦~有点开心，毕竟是第一次通过面试。不过因为是在深圳（我投递的时候专门写了工作在成都并且不接受调配，没想到还是分配到深圳了），最近新冠疫情，不敢乱窜，于是就算啦。

这次面试的经验，一是和字节不同，腾讯更多考的是算法，所以刷 LeetCode 还是很有用的。二是 C++ 语法糖尽量还是要会（可我上完 C++ 课以后，主要就是用 MATLAB 和 Python 了，C++ 应该不是必须的吧）不过要是需要的话，还是可以去把 C++ Primer Plus 重新看一遍的。

2020冬 腾讯成都 WXG 后台开发 日常实习

接上文，正好前几天参加腾讯成都 Openday 加了腾讯成都 HR 的微信，就问了一下能不能转岗或者重新面试。HR 告诉我还有一点 HC，于是就重新面试啦~

第一面

这次问的东西有点多，可能没记全

1. 自我介绍
2. 下为 C++ 的方面：描述一下 static
3. 用过哪些 STL 库

C++ 其实最近都没咋用了，数模那段时间用 MATLAB、微信小程序用 JavaScript。

我就答了几个 ACM 常用的模板：vector、map、set、unordered_map(unordered_set)、list、sort。看来有时间一定把 C++ Primer Plus 刷一遍。

4. map 和 unordered_map 的区别。前者是红黑树实现，后者是 HashMap，二者在时间复杂度上有差异。
5. map 和 multimap 的区别。前者每个 key 只能在 map 中出现一次，后者可以出现多次。所以前者可以使用 m[key] 的形式访问 value，后者只能 m.find(key) 访问任意一个 iterator，或使用 m.equal_range(key) 返回该值的范围（左闭右开）。
6. C++11 C++14 的特性了解过哪些。

啊这 不用 C++ 真不了解。我就答了一个 lambda 表达式，面试官追问了一下 lambda 捕获的含义。

7. 数据库方面：用过哪些数据库
8. 操作系统的方面：描述一下进程间消息传递

虽然在 OS 课上学了消息传递，但我们的消息传递是为互斥服务的，也没有作为重点讲，所以当时没意识到他问的消息传递就是我学的为互斥服务的那个。

9. Linux 系统的方面：用过哪些命令

这个问没答好，一是没准备，二是紧张所以只说了基础的几个。其实应该让他举一个场景，让我我写相关命令。

10. 计网方面：描述一下从浏览器输入网址后回车，到接收到服务器响应之间的过程（经典复现，见 2020 冬字节跳动）
11. TCP 和 UDP 有什么区别
12. 描述一下自己写的某个项目
13. 编程题：进制转换 (opens new window) 将一个长度最多 30 位数字的十进制非负整数转换为二进制数并输出。

第一反应就是反复进行高精度除法，但是高精度做的话时间复杂度是 $O(n^2)$，感觉会有 $O(n)$ 的算法，想了半天没想出来，跟面试官说了，最后面试官也没让我写。最后复盘发现就是原题！噔噔咚

面试官没让我写这个正确的算法，可能他也没听说过高精度除法，也不知道题解的正确复杂度相比之下，腾讯深圳的面试官还会让我算复杂度，还告诉我没有更简单的复杂度了hhhh

14. 编程题：打印N个数组整体最大的Top K (opens new window) 给定 N 个有序数组，要求从大到小打印这 N 个数组整体最大的前 K 个数，要求时间复杂度是 $O(k \log k)O(klogk)$，空间复杂度为 $O(k \log k)O(klogk)$

第一反应也是堆排序，类似于归并链表 (opens new window)，对每个数组最大的元素维护堆，pop 出最大的数后，将来源数组的接下来的数加入堆。

问题就在于，原题中没保证 $N \leq K$。当 $N>K$ 时，该算法的时间复杂度变为 $O(N\log N)$，和题目不符。面试的时候，写完了以后纠结了好一会，但是感觉题目不会这么难，于是就直接跟面试官说写完了。后来去牛客网交，过了。

只能说，牛客 OJ 这次给我的体验就是，题目质量有点不行。

总结

计网数据库 OS 都考的话，基本又是啥都能答一点，但是又答不对。算法题也有一个题没写，感觉很像是字节跳动的一面。感觉会凉。

最后果然是凉了，只能说太菜了。也是，因为不是必须实习，加上寒假还有学习计划、下学期还有课，所以没有太准备面试。

正式秋招的时候一定认真复习计网、数据库、操作系统，有时间的话还可以看看 C++11、C++14 的特性。