2022/03/10 字节后端实习面试复盘
字节视频面
数据结构
-
哈希表的实现方式
一开始以为是问STL里面map和unordered_map的底层数据结构，后来面试官追问了一下才明白是在问哈希表这个数据结构的底层实现，其实就是数组+链表，但是一开始没有说对，面试官问了一下哈希碰撞的解决，然后想起来是用数组+链表来搞定。 -
追问：链表过长时如何解决？
把链表换成二叉树，这样可以降低搜索的时间复杂度 -
追问：应该用哪种二叉树？
这里答成二叉搜索树了，其实应该是红黑树，我把二叉搜索树的性质记错了，以为有左右子树的平衡 -
追问：二叉搜索树的性质？查找时间复杂度是多少？二叉搜索树最坏情况下查找时间复杂度是多少？
左子树节点值比根节点的值小，根节点比右子树节点值小，然后左右子树都是二叉搜索树；复杂度O(logN)，但是我以为二叉搜索树一定是完全二叉树，以为不会出现最坏情况；实际上如果二叉搜索树是有可能退化成单枝树的，这时查找复杂度会编程O(N)。
算法
-
快排的实现？
这个没啥问题。 -
追问：快排会出现性能退化的情况吗？什么情况下会发生？
会，如果快排每次选的基准数都是最小或者最大的数，这时候时间复杂度会退化成O(n2)。 -
追问：如果数组里有很多重复的元素，快排的性能会变差吗？
以前没考虑过这个问题，想了一下应该是会变差，每次递归划分区间如果非常不平衡就会导致快排性能下降。 -
追问：那么面对这种情况，应该用哪种排序算法比较合适？
回答了堆排序、桶排序，查了一下发现可以用哈希表来记录重复数字的个数，就是所谓的哈希排序。 -
追问：怎么针对含有大量重复元素的情况优化快排？
这个问题从来没考虑过，想了一下没想出来，放弃了。查了一下发现在算法研究里针对快排有过专门应对这种情况的改进，就是所谓的双路快排，用i和j分别指向小于基准数的下一个数和大于基准数的前一个数，i向后遍历直到遇到比基准数大的元素，j向前遍历直到遇到比基准数小的元素，这时如果i < j就直接交换i和j指向的元素，然后继续之前的操作。这样做好处在于两边遇到等于基准数的元素不会处理，这样两个区间内包含的等于基准数的元素个数也大致差不多，避免了出现左右区间长度不平衡的情况。在双路快排的基础上又可以优化出三路快排，就是在划分区间的时候分成3个区间，把等于基准数的元素保存到中间的区间，这样递归到下一层的时候减少了对重复元素的比较。
计算机网络
-
讲一下TCP三次握手
说了一下流程 -
为什么不能是两次握手？
这个问题有点没答到点子上，我说的是服务器没有收到客户端对建立连接的确认信号时，会重复发送建立连接的请求，应该是两次握手时，如果出现消息滞留，客户端可能会多次发送连接建立请求，而没有第三次握手服务器无法确定客户端是不是收到了自己发送的建立连接的确认信号，就会每收到一个连接建立请求就主动建立一个连接，造成资源浪费。 -
TCP连接中的半连接状态是什么？
说混了，把半连接说成半关闭了，以为是四次挥手里面的客户端收到服务器对FIN请求回应的ACK之后的状态，其实半连接是三次挥手中，服务器响应客户端发起连接请求后的状态，这时如果客户端不进行第三次握手，服务器就一直处于半连接状态，这样会导致服务器的内存被浪费。
还有一个半打开状态，是TCP连接中有一方突然异常关闭之后，另一方不知情的状态。 -
TCP泛洪攻击是什么？
这个之前看过，大致讲出来了，就是攻击方向服务器发送大量的SYN连接请求但是又不进行第三次握手,这样服务器要不停地发送ACK确认，使服务器资源被耗尽无法服务其他用户。 -
怎么应对泛洪攻击？
这个就凭印象说了一下设置一个时间来丢弃不进行第三次握手的连接（其实本身就有这个设定，叫SYN timeout，应该是缩短它），或者标记一下发送过很多建立连接请求最终又不建立起连接的IP地址把其屏蔽（过滤思路),但是这个方法其实不太能应对伪装地址或者分布式攻击,目前的解决方法还是用到防火墙,有这么几种思路(参考了博客: ):- 防火墙收到客户端的SYN包时，直接转发给服务器：防火墙收到服务器的SYN/ACK包后，一方面将SYN/ACK包转发给客户端，另一方面以客户端的名义给服务器回送一个ACK包．完成TCP的三次握手，让服务器端由半连接状态进入连接状态。服务器能承受连接状态的能力比承受半连接状态的能力强得多,所以可以降低攻击的影响.
- 设置防火墙的SYN请求超时参数，让它远小于服务器的超时期限．防火墙负责转发客户端发往服务器的SYN包，服务器发往客户端的SYN/ACK包、以及客户端发往服务器的ACK包。这样，如果客户端在防火墙计时器到期时还没发送ACK包，防火墙则往服务器发送RST包，以使服务器从队列中删去该半连接。由于防火墙的超时参数远小于服务器的超时期限，这样能有效防止泛洪攻击.
- SYN中继防火墙在收到客户端的SYN包后．并不向服务器转发而是记录该状态信息后主动给客户端回送SYN/ACK包，如果收到客户端的ACK包。表明是正常访问，由防火墙向服务器发送SYN包并完成三次握手。这样由防火墙作为代理来实现客户端和服务器端的连接，可以完全过滤不可用连接发往服务器。
-
TCP和UDP的区别
应该都答上来了 -
TCP为什么可靠？或者是TCP用什么机制来实现可靠性的？
没有细致思考过这个问题，凭直觉讲了一下和建立连接、超时重传、流量控制以及拥塞控制有关。查了一下，应该从乱序重排、应答确认、报文重传和流量控制四种机制来讲，比较有条理。 -
提到了流量控制，TCP的流量控制是怎么实现的？
我记得是靠滑动窗口来实现的，接收方会给发送方发的确认报文里提供自己的缓冲window值，发送方会根据这个值来改变滑动窗口的大小。 -
UDP的应用场景
从UDP的特点出发,UDP不是可靠的,同时没有流量控制和拥塞控制,所以很直观的应用场景就是对准确性要求不高而对速度要求高的场景,像是在线视频这一类的(网络语音,直播等等). -
HTTP和HTTPS的区别?
忘了其实...印象里HTTPS是基于HTTP的安全协议,好像是和加密算法有关,但是我只把加密算法说成了RSA,其实准确得说应该是基于TLS/SSL协议.不过TLS/SSL的功能实现依赖的加密算法确实包含RSA算法，总共有三类：散列算法、对称加密和非对称加密,RSA属于非对称加密算法而且是很常用的算法. -
RSA是对称加密算法还是非对称加密算法?
当时忘了,是非对称的,就是说加密和解密可以使用不同的密钥.
操作系统
- 进程间通信有哪些方式？
不会，很尴尬，操作系统真是软肋。面试官后面也没有问其他操作系统相关的问题了。
代码题
做完查了一下，是LeetCode1004原题，把题目贴过来：
给定一个二进制数组 nums 和一个整数 k ，如果可以翻转最多k 个 0 ，则返回 数组中连续 1 的最大个数 。
示例 1：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
提示：
1 <= nums.length <= 20000
0 <= k <= nums.length
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-consecutive-ones-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我一开始的思路是先计算出数组的前缀和数组，这样能在O(1)的时间里算出任意子数组内0和1的个数，如果0的个数小于k就可以将子数组的长度与当前计算得到的最长值比较，但是这样要遍历所有的子数组，时间复杂度是O(n2)。这题里面数组的长度可以达到20000，显然这个思路不太对，后来面试官提醒了一下用滑动窗口，很快就反应过来了，维护滑动窗口的左右边界和窗口内0的值，右边界向右移动，遇到1不处理继续右移，遇到0判断现在窗口内0的值有没有超过k，没有的话也不处理继续移动右边界，如果超过k，更新一次最大子数组长度，开始右移左边界直到遇到0，直到右边界到达数组结尾，结束循环后再比较一下窗口长度和最大子数组长度。代码如下：
class Solution {
public:
int longestOnes(vector& nums, int k) {
int n = nums.size();
int left = 0, right = 0, cnt = 0;
int ans = 0;
while(right < n){
if(nums[right] == 1){
++right;
}
else{
++cnt;
if(cnt <= k){
++right;
}
else{
ans = max(ans, right - left);
while(left < right && nums[left] == 1){
++left;
}
++left;
--cnt;
++right;
}
}
}
ans = max(ans, right - left);
return ans;
}
};
总结
感觉字节的这场面试会针对一个问题问得特别深入,一直到我回答不上来为止,还是对一些问题的思考有点不够深入了,需要加深理解.