面试官很友好，自己太菜了。意识到了自己对计算机的认知有多么浅薄 orz
一共75分钟，讲的口干舌燥
不知道哪些是答得不对或者不全的地方，也请懂的同学不要藏着掖着，可以在讨论区聊聊呀~
一个小厂面试难度竟然已经如此可怕了
感觉分布式已经是后端的必要技术栈了。卷成这样也是离谱。也许该好好考虑考虑 #互联网没坑了，还能去哪里# 这个话题了。
等我毕业了，银行等国企的坑也该填满了，感觉自己每多上一天学，就业就恶化一天。鉴定为：寄
回想起20年字节的实习门槛，回想起那时某些双非本科一个班能秋招4个进字节。努力在时代面前不值一提~
项目
HTTP/TCP的相关知识：三次握手，Long connection的含义、半连接的作用
socket操作，socket操作与三次握手之间的对应关系。
Session、Cookie、Token
Mysql为什么选择B+树（开始吟唱），答了支持范围查询（不能用哈希）+减少IO次数（B树、二叉树、红黑树、跳表都有更多次IO的问题）
Mysql有哪些优化措施：“先说这是一个很大的话题”，答了建立恰当的索引（以及避免索引失效）、低NF以空间换时间、改用适合业务场景的其他执行引擎(MyIASM, RocksDB）、分库分表（水平垂直分库分表）、建立主从集群（讲了一主多从、主从分离）。
操作系统：Page Cache的作用，操作系统进程的状态（答得不好，状态的名称记不太清了）、操作系统的进程调度算法（没看过，看过也忘了，寄）。
用过哪些命令。
磁盘IO有哪些优化？只想到了减少访存次数+顺序读写，面试官说之前提到的Cache也可以（傻了，竟然没想到），讲讲磁盘的Cache（说了mmap这种direct IO和缓冲IO，感觉说的不太好，可能没扣题）。
内存满了之后怎么办？答了通过页面淘汰算法淘汰页面，比如FIFO, LRU, LFU。
Go：协程切换VS线程切换，讲讲协程切换的细节（说了恢复上下文，包括保存的寄存器信息和pc指针，懂的同学可以讲讲）
容器：讲了讲docker的大体实现，docker是做什么的。
知道K8S这种容器编排吗？是做什么的？不会K8S，直接寄，听面试官大概讲了讲K8S用于万规模以
https://article.itxueyuan.com/O0Pg3
参考类似二分查找的方法，每次选择按照二进制位统计，“更少”的那一堆。
当然了，这种方法要借助文件。每次，按照二进制位是0还是1，将其分为两部分。分好的结果可以append到文件中。
另一种方法：直接使用bitmap来统计，每个元素是否出现。复杂度O(N)，需要大约512M内存空间。
给你一个整型数组 nums，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
https://leetcode.cn/problems/maximum-product-of-three-numbers/
分类讨论：三个正数|一个正数两个负数|两个正数一个负数|整个数组没有正数。
- 三个正数：排序后最大的三个；
- 一个正数两个负数：最小的两个负数*最大的正数；
- 没有正数：最大的三个数；
- 两正一负：如果只有这三个数，则就是最大三个数，如果还有一个正数或者负数，都能凑出更大的正数，因此不考虑。
因此，需要找出最大的三个数和最小的两个数。
寻找方法：一次扫描，然后暴力记录。
int min1=INT_MAX, min2=INT_MAX;int max1=INT_MIN, max2=INT_MIN, max3=INT_MIN;for(int num:nums){//先更新最小值if(num<min1){min2=min1;min1=num;}else if(num<min2){min2=num;}//更新最大值if(num>max1){max3=max2;max2=max1;max1=num;}else if(num>max2){max3=max2;max2=num;}else if(num>max3){max3=num;}}return max(max1*max2*max3, min1*min2*max1);
基本概念
滑动窗口是一种基于双指针的一种思想，两个指针指向的元素之间形成一个窗口。
分类：窗口有两类，一种是固定大小类的窗口，一类是大小动态变化的窗口。
应用：什么情况可以用滑动窗口来解决实际问题呢？
- 一般给出的数据结构是数组或者字符串
- 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
- 该问题本身可以通过暴力求解
固定窗口大小：通常直接固定下窗口的长度，for循环只用关注最左边的点l，每次进入l+window.size，出栈l即可。
非固定窗口大小：扩张r, 直到符合要求，然后收缩l。
leetcode类型题目：
https://leetcode.cn/problems/minimum-window-substring
https://leetcode.cn/problems/find-all-anagrams-in-a-string/
剑指 Offer 52. 两个链表的第一个公共节点
https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
虽然标为【简单】，但其实进阶做法较有技巧。其和链表成环一样，都能想到双指针。但是本题双指针的取巧性更强。
具体而言，假设链表A的私有部分长为a，链表B的私有部分长为b，二者的公共部分（如有）长度为c。
在aPtr走到尽头时，走了长度为a+c,此时只要将其接到B上继续往下走，走长度b时，总步数为a+c+b。而bPtr走到尽头时，接到A上继续往下走长度为a时，总步数也为a+c+b，即二者重合时【而且】此时二者都在第一个公共节点上。
class Solution {public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA == nullptr || headB == nullptr) {return nullptr;}ListNode *pA = headA, *pB = headB;while (pA != pB) {pA = pA == nullptr ? headB : pA->next;pB = pB == nullptr ? headA : pB->next;}return pA;}};
不允许使用任何比较运算符（例如>，<，?:等），判断语句，maxmin等函数，判断a和b的大小？
解法1：绝对值法：
return a+b+abs(a-b)/2
如果a比较大，返回a，如果b比较大，返回b
解法2：
计算a-b，取出最高位的元素，即r=(a-b)&0x8000_0000
res=r==1?a:n
难度：leetcode hard
给定 n 个非负整数表示每个宽度为 1的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
原文地址：
https://leetcode.cn/problems/trapping-rain-water/
这道题的算法原理较好想到，其实就是确定任何一点的左右最大值，就可以得知这个点能够装到的最高的水。难在如果先做一遍遍历再将最大值存在数组中，无法做到从O(N)空间到O(1)的优化。
实际使用的方法是难点【双指针】。其实就是，维护left指针和right指针，如果当前left点的高度比right更低，那么left点的储水量就已知了（因为right向左移动，新值一定比right更大，因此，限制当前left点储水高度的，一定是left点的高度。）在求出left点的储水量后，向右边移动left即可。如此继续这个步骤，直到left==right。
这道题其实和leetcode medium中的盛水最多的容器很相似，从两端开始贪心，在找到当前限制条件（短板）后，提高短板到下一个极值点。
原始题目:
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/
第一次学习KMP算法，参考的是改进版的动态规划算法。
https://zhuanlan.zhihu.com/p/83334559
其本质为一个有限状态机，通过needle构造出一个状态机，状态个数为needle的长度，然后不断输入heystack中的字符，处理状态机的改变。
状态机构造时的核心思路为：当无法继续向下匹配时，向影子状态，即代码中的X，即当前最长前缀所在的位置（X始终比当前遍历到的位置慢一步）询问下一个应该到达的状态。
本算法为了便于理解，在每个位置状态，多用了255个空间，但总的空间复杂度依旧保持不变。
class Solution {public:int strStr(string haystack, string needle) {//字符串匹配？似乎有什么kmp算法？暴力匹配的话，最大复杂度为O(mn)//直接使用kmp，首先构建next数组，本文选择二维的数组//从haystack中查找needlevector<vector<int>> dp(needle.length(), vector<int>(255, 0)); //char a的取值范围就是0-255//初始状态为0int X = 0; //标记上一个状态dp[0][needle[0]] = 1; //只有这种情况下，才转移到1，其余情况都保留在0for (int i = 1; i < needle.size(); i++) {for (int c = 0; c < 255; c++) {
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
来源：https://leetcode.cn/problems/remove-duplicate-letters/
去掉一部分，使得字典序最大（最小），是一种很著名的单调栈题型。
其解法相对较为固定的部分是：保证单调栈是单调增加的。如果不单调增，则要删掉栈顶的那个“太大”的元素（往往有一定条件）
在本题中，其条件为：该字符在后面至少还有一次出现（否则就删没了）
此外，还需要考虑删除少了的情况。在本题中的方法为：如果前面已经出现过了这个元素，那么无条件删除后续要加进去的元素（相当于做了从后往前的删除）。有些时候，也可能是诸如“直接截断出前xxx个元素”
有一个对这类题型的很好归纳，见：https://leetcode.cn/problems/remove-duplicate-letters/solution/yi-zhao-chi-bian-li-kou-si-dao-ti-ma-ma-zai-ye-b-4/
此外，有一点python上的技巧，例如末尾数组用stack[-1]。
from functools import reducefrom operator import addclass Solution:# //去掉一部分，使得字典序最大（最小），是一种很著名的单调栈题型。# //其解法相对较为固定的部分是：保证单调栈是单调增加的。如果不单调增，则要删掉栈顶的那个“太大”的元素（往往有一定条件）# //在本题中，其条件为：该字符在后面至少还有一次出现（否则就删没了）# //此外，还需要考虑删除少了的情况。方法为：如果前面已经出现过了这个元素，那么无条件删除后续要加进去的元素（相当于做了从后往前的删除）def removeDuplicateLetters(self, s: str) -> str:stack = []hasadd = set()ccount = {} # 到了当前位置后，“后面”还剩下