byte跳动一面

引言

故事发生在一个平淡的早上，一本正经的小潘正端坐在自己的电脑桌前，眼神有些迷茫，因为今天早上要和byte公司进行视频一面，昨天晚上紧张的有些失眠，现在小潘内心在为自己祈祷，毕竟她很想加入这家公司。

时间一分一秒的过去了，小潘呼吸越来越紧促，因为马上就要到约定的面试时间了，5，4，3，2，1，叮铃铃，对方发起了视频邀请，小潘接受了邀请，“你好，我是今天的面试官”，“您好，您好”小潘连忙应答到。

面试官：你先做个自我介绍吧。
小潘：您好，我叫小潘，来自湖南长沙，是一名应届生，毕业于...

Java基础篇

面试官：你简历上面说你熟悉Java基础，那我就先问问你Java基础相关知识吧
小潘：好的

面试官：能说一下HashMap的数据结构吗？
小潘：（小潘一听，心想HashMap面试题都看了n遍了，这下稳了呀）好的，JDK1.7HashMap的数据结构是数组+链表，JDK1.8HashMap的数据结构是数组+链表+红黑树，其中，数组是用来存储数据元素，链表是用来解决冲突，红黑树是用来提升效率的，如果链表长度>8&数组大小>=64，链表转为红黑树，如果红黑树节点个数<6 ，转为链表。

面试官：（这题答得还行，我继续问问看）为什么HashMap数据结构不用二叉树或者平衡二叉树而是用红黑树？
小潘：红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度；平衡二叉树是比红黑树更严格的平衡树，为了保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低（这下应该不会在问HashMap了吧）。

面试官：（我在来问问底层设计吧，继续炸一下她）那为什么HashMap的容量是2的倍数？
小潘：（看样子这面试官是死磕HashMap了）迅速在脑海中回忆这个知识点，整理了一下，开始回答：
第一个原因是为了方便哈希取余：
将元素放在table数组上面，是用hash值%数组大小定位位置，而HashMap是用hash值&(数组大小-1)，却能和前面达到一样的效果，这就得益于HashMap的大小是2的倍数，2的倍数意味着该数的二进制位只有一位为1，而该数-1就可以得到二进制位上1变成0，后面的0变成1，再通过&运算，就可以得到和%一样的效果，并且位运算比%的效率高得多。
HashMap的容量是2的n次幂时，(n-1)的2进制也就是1111111***111这样形式的，这样与添加元素的hash值进行位运算时，能够充分的散列，使得添加的元素均匀分布在HashMap的每个位置上，减少hash碰撞。

第二个方面是在扩容时，利用扩容后的大小也是2的倍数，将已经产生hash碰撞的元素完美的转移到新的table中去。

面试官：（不错不错，在来考一个实践吧）你能自己设计一个HashMap吗？
小潘：（这下有点慌了呀，难道是要我手写HashMap吗）我的设计思路是：
散列函数：hashCode()+除留余数法
冲突解决：链地址法
扩容：节点重新hash获取位置
现场写可能短时间写不出
面试官：没事没事，你的这个思路是对的（HashMap就问这么多吧）

面试官：线程池有用过吗？可以说一下线程池的工作流程吗？
小潘：用过呀，它的流程是：
程池刚创建时，里面没有一个线程。任务队列是作为参数传进来的。不过，就算队列里面有任务，线程池也不会马上执行它们。
当调用 execute() 方法添加一个任务时，线程池会做如下判断：
如果正在运行的线程数量小于 corePoolSize，那么马上创建线程运行这个任务；
如果正在运行的线程数量大于或等于 corePoolSize，那么将这个任务放入队列；
如果这时候队列满了，而且正在运行的线程数量小于 maximumPoolSize，那么还是要创建非核心线程立刻运行这个任务；
如果队列满了，而且正在运行的线程数量大于或等于 maximumPoolSize，那么线程池会根据拒绝策略来对应处理。

面试官：（在来问一下线程池实践）你在项目中有用到过线程池吗？
小潘：有用过，之前我在项目中用了一个多线程来推送数据，用线程池来管理线程。

面试官:线程池的线程数应该怎么配置呢？
小潘：（面试官不会又要问到底了吧）这个要分具体场景，任务分为计算密集型、IO密集型、混合型。
计算密集型：大部分都在用CPU跟内存，加密，逻辑操作业务处理等。
IO密集型：数据库链接，网络通讯传输等。
计算密集型一般推荐线程池不要过大，一般是CPU数 + 1，+1是因为可能存在页缺失(就是可能存在有些数据在硬盘中需要多来一个线程将数据读入内存)。如果线程池数太大，可能会频繁的 进行线程上下文切换跟任务调度。
IO密集型：线程数适当大一点，机器的Cpu核心数*2。
混合型：可以考虑根据情况将它拆分成CPU密集型和IO密集型任务，如果执行时间相差不大，拆分可以提升吞吐量，反之没有必要。

面试官：（这同学Java基础还可以，我在问问数据库相关的知识吧）

MySQL篇

面试官:先做一个SQL题吧
题目链接：https://leetcode.cn/problems/department-highest-salary/
小潘：（我去，一上来直接写sql）好的，小潘思考了一下（看来这题面试官想考我MAX和GROUP BY的用法，不过这简单，难不倒我），过了一会小潘写出以下sql。

SELECT
    DepartmentId, MAX(Salary)
FROM
    Employee
GROUP BY DepartmentId;

面试官：看了看sql，点了点头，然后又问你们平时用的什么引擎？
小潘：InnoDB存储引擎（我猜他要问我几种存储引擎的区别了）

面试官：那InndoDB和Myisam的区别是什么？
小潘：（果然不出所料，还好有所准备）
InndoDB是支持事务的，Myisam是不支持的
InnoDB支持外键，而Myisam不支持
InnoDB的数据是存储在B+树的叶子节点的，而Myisam的叶子节点只是存储指向数据的指针

面试官：InnoDB存储引擎底层数据结构是什么，有什么特点？
小潘：底层数据结构是B+树，它的特点是：非叶子节点不存储data,只存储索引，可以放更多的索引，叶子节点包含所有索引元素，叶子节点用指针连接，提高区间访问的性能，节点内还是节点之间数据是从左到右依次递增的，一个节点可以放16kb，1170个元素，1170117016 2千万，高度为3，高度是由非叶子节点能放多少个索引元素决定的。

面试官:那为什么不用B树呢？
小潘：B树的特点是叶节点具有相同的深度，叶节点的指针为空 所有索引元素不重复 ，节点中的数据索引从左到右递增排列，一块空间存储一个kv结构，节点中的数据从左到右递增排列，非叶子节点可以存储键和data，由于数据同时存在于叶子节点和非叶子结点中，无法简单完成按顺序遍历B树中的关键字，必须用中序遍历的方法。综上所述B+树更好一些。

面试官：我们来看一个sql吧，这个sql在InnoDB、Myisam的索引情况是怎样的？

select count(*) from xx where name=xx

小潘：对于InnoDB来说，上面这个sql是要进行全表扫描的，对于...
面试官：打断一下，是一定会进行全表扫描吗？
小潘：不一定，某些情况下，MySQL会选择走覆盖索引。
面试官：为什么会走覆盖索引呢？
小潘：覆盖索引话，只需要存索引字段本身和主键id值，因此对于同一页来说，可以存放更多的行，那么扫描的页就会少，速度就会更快。

面试官：嗯..继续回答上面的问题吧
小潘：好的，对于Mysiam来说，带where条件的，肯定是不会用到那个行变量的，这时得分情况，如果name没有索引，那么是要全表的扫的，如果name有索引，应该是会走name索引的。

面试官：MySQL有哪些索引？
小潘：（心里面窃喜，这还不简单）很快说出主键索引、唯一索引、普通索引、全文索引、联合索引

面试官：唯一索引和普通索引如何选择？
小潘：（这问题好奇怪呀，不应该直接就是唯一索引吗）对于唯一索引来说，找到满足条件的记录就不会在查下面的记录了，对于普通索引来说，查找到满足条件的第一个记录后，还会继续去查找下一个记录，直到碰到第一个不满足该条件的记录，感觉还是唯一索引效率高一点。

面试官：还有其他的区别吗？
小潘：（内心在嘀咕：难道还有其他原因吗）嗯，这个我还没了解过，您可以告诉我一下吗？
面试官：上面你说的这个也是一个原因，但是这个在效率上是差距是很小的，真正决定效率的是在于Insert Buffer / Change Buffer 的存在，因为它们只适用于非唯一的辅助索引，以 Insert Buffer 为例，当要插入的索引页不在缓冲池的时候，存储引擎并不会每插入一个新数据就去离散地访问一次磁盘页，而是先将这个操作存储到 Insert Buffer 中，在下次查询需要访问这个数据的时候，存储引擎才会将其合并（Merge）到真正的辅助索引中。这时，就相当于将多个叶子节点插入操作合并到一个操作中，这就大大提高了对于辅助索引的插入性能，所以选择普通索引效率会高一点。
小潘：（大佬牛逼）原来这个这么复杂呀， 学到了学到了。

面试官：大部分回答的都不错，数据库算你过关了，下面我在问问网络相关的知识

网络篇

面试官：问几个基础的吧，get和post有什么区别？
小潘：
1、url可见性：get，参数url可见；post，url参数不可见
2、数据传输上：get，通过拼接url进行传递参数；post，通过body体传输参数
3、缓存性：get请求是可以缓存的；post请求不可以缓存
4、后退页面的反应：get请求页面后退时，不产生影响；post请求页面后退时，会重新提交请求
5、安全性：因为get会在url携带参数，post参数是在请求体，所以post比get安全一点

面试官：get和post都是幂等的吗？
小潘：不是的，get方法是安全且幂等的，因为它是只读操作，无论操作多少次，服务器上的数据都是安全的，且每次的结果都是相同的。
post因为是新增或提交数据的操作，会修改服务器上的资源，所以是不安全的，且多次提交数据就会创建多个资源，所以不是幂等的。

面试官：HTTP和HTTPS有什么区别？
小潘：HTTP 是超文本传输协议，信息是明文传输，存在安全风险的问题。HTTPS 则解决 HTTP 不安全的缺陷，在 TCP 和 HTTP 网络层之间加入了 SSL/TLS 安全协议，使得报文能够加密传输。
HTTP 连接建立相对简单， TCP 三次握手之后便可进行 HTTP 的报文传输。而 HTTPS 在 TCP 三次握手之后，还需进行 SSL/TLS 的握手过程，才可进入加密报文传输。
HTTP 的端口号是 80，HTTPS 的端口号是 443。
HTTPS 协议需要向 CA（证书权威机构）申请数字证书，来保证服务器的身份是可信的。

面试官：（在问一个偏一点的）HTTPS里面的SSL/TLS协议的基本流程是怎样的？
小潘：（听完，有些蒙了，竟然问这么细）摇了摇头，低声说，不好意思，这个我没了解过。

面试官：大致流程是这样的：客户端向服务器索要并验证服务器的公钥；双方协商生产「会话秘钥」；双方采用「会话秘钥」进行加密通信。由于时间关系，详细的就不说了，后面你可以去了解一下。
小潘：（我才不去了解呢，也只有你会问这么无聊的问题）好的

面试官：HTTP2.0在HTTP1.0基础上做了那些优化？
小潘：1. 头部压缩：HTTP/2 会压缩头（Header）如果你同时发出多个请求，他们的头是一样的或是相似的，那么，协议会帮你消除重复的分。
2. 二进制格式：HTTP/2 不再像 HTTP/1.1 里的纯文本形式的报文，而是全面采用了二进制格式。
3. 多路复用：HTTP/2 是可以在一个连接中并发多个请求或回应，而不用按照顺序一一对应。

面试官：其实还有一个数据流的处理，这个可以去了解一下，你网络基础还不错，下面我在问一个操作系统的问题

操作系统篇

面试官：可以说一下进程之间通信机制吗？
小潘：（还好看了小林大佬的图解系统）好的
通信方式一共有七种：
匿名管道顾名思义，它没有名字标识，匿名管道是特殊文件只存在于内存，没有存在于文件系统中，匿名管道是只能用于存在父子关系的进程间通信，匿名管道的生命周期随着进程创建而建立，随着进程终止而消失。

命名管道突破了匿名管道只能在亲缘关系进程间的通信限制。

消息队列克服了管道通信的数据是无格式的字节流的问题，消息队列实际上是保存在内核的「消息链表」，消息队列的消息体是可以用户自定义的数据类型，发送数据时，会被分成一个一个独立的消息体，当然接收数据时，也要与发送方发送的消息体的数据类型保持一致，这样才能保证读取的数据是正确的。消息队列通信的速度不是最及时的，毕竟每次数据的写入和读取都需要经过用户态与内核态之间的拷贝过程。

共享内存可以解决消息队列通信中用户态与内核态之间数据拷贝过程带来的开销，它直接分配一个共享空间，每个进程都可以直接访问，就像访问进程自己的空间一样快捷方便，不需要陷入内核态或者系统调用，大大提高了通信的速度，享有最快的进程间通信方式之名。但是便捷高效的共享内存通信，带来新的问题，多进程竞争同个共享资源会造成数据的错乱。

那么，就需要信号量来保护共享资源，以确保任何时刻只能有一个进程访问共享资源，这种方式就是互斥访问。信号量不仅可以实现访问的互斥性，还可以实现进程间的同步，信号量其实是一个计数器，表示的是资源个数，其值可以通过两个原子操作来控制，分别是 P 操作和 V 操作。

与信号量名字很相似的叫信号，它俩名字虽然相似，但功能一点儿都不一样。信号是进程间通信机制中唯一的异步通信机制，信号可以在应用进程和内核之间直接交互，内核也可以利用信号来通知用户空间的进程发生了哪些系统事件，信号事件的来源主要有硬件来源（如键盘 Cltr+C ）和软件来源（如 kill 命令），一旦有信号发生，进程有三种方式响应信号 1. 执行默认操作、2. 捕捉信号、3. 忽略信号。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP，这是为了方便我们能在任何时候结束或停止某个进程。

前面说到的通信机制，都是工作于同一台主机，如果要与不同主机的进程间通信，那么就需要 Socket 通信了。Socket 实际上不仅用于不同的主机进程间通信，还可以用于本地主机进程间通信，可根据创建 Socket 的类型不同，分为三种常见的通信方式，一个是基于 TCP 协议的通信方式，一个是基于 UDP 协议的通信方式，一个是本地进程间通信方式。
面试官：不错不错，说的挺详细，然后看了一下时间，发现快到饭点了，那接下来做道算法题吧

算法篇

面试官：（小潘上面答得都还不错，就出个简单的算法题吧，早点做完，我也可以吃饭去了）
小潘：（激动人心的时刻终于来了，小潘深吸一口气，内心在祈祷面试官可以出一个简单的算法题）
面试官：来做一道买卖股票的题吧
题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/

小潘：（一听是买卖股票，这题我前天刚刷过，稳了稳了）小潘开始认真读题，发现这和她前天做的题目不一样呀，这题股票是可以买卖多次的，此刻的小潘使劲在脑海里回忆“这题该怎么写”，然而此时紧张的气氛让小潘无法集中注意力，况且面试官好像很焦急的样子让整个气氛更加紧张，看了看时间，已经面了70分钟了，估计留给我的时间不多了，我得赶快想”。

时间一分一秒的过去了，突然在3分钟后，面试官开口了。“给你个提示吧，买卖股票I你之前肯定有刷过吧，在买卖股票的最佳时机中，因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即dp[i][0]一定就是-prices[i]，而本题，因为一只股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润，那么第i天持有股票即dp[i][0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金减去今天的股票价格 即：dp[i - 1][1] - prices[i]。照着这个思路想想看”，面试官说道。听到了面试官的提示之后，小潘一下开了窍，思索了一下，开始编码。

五分钟后小潘写完了代码，然后自信的对面试官说：“面试官我写好了，您看看对不对”。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        vector<vector<int>> dp(len, vector<int>(2, 0));
        dp[0][0] -= prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < len; i++) {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); 
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }
};

面试官：看了看，是这样的，然后说到，今天就到这里吧，后面HR会和你联系的。

最后和大家提前透露一下，小潘一面已经通过，可以期待一下小潘的二面。