3/19 通过之前实习的leader直接内推，没有笔试，直接通知面试。
3/26 一二面连面：面完第一面，一面面试官说：之后会有二面的面试官来，你稍等一下。我才知道，这次在线面是一面二面连面。
3/28 HR打电话约了 3/30 上午进行三面。
4/7 HR面（和之后对接的HR xjj 不是同一个，所以这个HR面应该是部门HR）
4/13 HR xjj 加了微信，发了 offer，填了信息。

一面 2021.3.26 周五 10.30~11.17

1. 首先自我介绍，然后这位面试官之前在西瓜视频实习的时候遇到过，所以也没那么紧张了

2. 问了一下二面的实习具体情况，我的负责内容之类的。我讲完，他说：“我给你复述一下你的工作，你看对不对”，然后聊得比较开心

3. 然后基础问题略过不问了，出两道算法题：

算法题1：

• 输入描述：

  1. 第一行输入 n；
  2. 第二行输入 n 个数，表示一个列表；
  3. 第三行输入 m，表示接下来的 operation 次数
  4. 接下来输入 m 行，每行 2 个数：x y，要求输出第 x 个数到第 y 个数的和
  5. n m 很大，要求整体输出时间 < 1s

• 示例如下：

5 ～ 500w
2 3 1 0 -2
3 ～ 500w
2 4  ｜  3+1+0=4
1 4 ｜2+3+1+0=6
2 5 ｜ 3+1+0+-2=2

time < 1s
----
4
6
2

• 我的代码：

class Solution:
    
    def __init__(self, n, l):
        self.n = n
        self.l = l
        self.generate_sum()
        
    def generate_sum(self):
        self.s = [0]
        for i in self.l:
            self.s.append(self.s[-1] + i)
        print(self.s)
        
    def A(self, start, end):
        if end > len(self.s) or start < 1 or start > end:
            return -1
        return self.s[end] - self.s[start-1]


if __name__ == "__main__":
    n = 5
    l = [2, 3, 1, 0, -2]
    
    op = [[2, 4], [1, 4], [2, 5]]
    s = Solution(n, l)
    for p in op:    
        print(s.A(p[0], p[1]))

算法题2：

• 输入描述：

  1. 算法1的加强版，输入的不是一个列表，而是一个矩阵
  2. 每次输入的操作不是两个值，而是四个值，表示 x1 y1 x2 y2 两个坐标点
  3. 要求输出 x1 y1 到 x2 y2 之间的子矩阵的和
  4. 写出计算公式即可，不需要代码实现

• 示例如下：

1 2 3 4
5 6 7 8
9 1 2 3

2 2 3 3 ｜ 6+7+1+2=16

q(x1,y1,x2,y2) = ???

• 我的代码：

    x1, y1, x2, y2 = 2, 2, 3, 3
    q(x1, y1, x2, y2) = s[x1-1, y1-1] - s[x1-1, y2] - s[x2, y1-1] + s[x2, y2]
    
    m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 1, 2, 3]]
    s = {}
    s[x1-1] = {}
    s[x2-1] = {}
    s[x2] = {}
    
    s[x1-1][y1-1] = 1
    s[x1-1][y2] = 1 + 2 + 3
    s[x2][y1-1] = 1 + 5 + 9
    s[x2][y2] = 1 + 2 + 3 + 5 + 6 + 7 + 9 + 1 + 2
    
    print(s[x1-1][y1-1] - s[x1-1][y2] - s[x2-1][y1] + s[x2][y2])
    
    然后继续问：你的 s 怎么计算得到，同样写出公式
    s[x, y] = -s[x-1, y-1] + s[x, y-1] + s[x-1, y] + m[x, y]

• 算法题总结
  第一题很简单，做出来的也很快
  第二题边界很麻烦，写错了两次。还是需要自己写出来验算一下的。

4. 然后问了一道系统设计：

问题描述：
- 我们是电商方向嘛，问你一道电商题吧，PM的一句话需求：我想要你做出来一个消费排行榜，要前100名的用户排行榜，并能实时更新。
- 考虑的几个点：你怎么生成这个排行榜；你的技术选型；对于排行榜数据，用户请求量是多大；在高并发下你如何提供稳定的服务；后续你的排行榜如何更新。
- 你拥有的数据：历史订单信息（包含 user id，timestamp, cost, state 比如待支付，已支付）

我的思路：

• 分为在线的信息统计、离线历史信息的统计和提供查询服务三部分。
  • 在线：
    采用在线计数器（类似公司内部的 counter service 服务）进行在线的用户 cost 计算更新，每次订单支付，都通过过滤规则从上报的订单信息中挑选出来，并累加到计数器内。（面试官问：你知道 CS 怎么实现的么？我说当时只是用了一下，具体实现没细看，但是大概知道流程，然后讲了一下）
    定一个时间节点开启计数器，比如2021.3.27零点，然后在线数据就维护起来了，其次需要计算历史数据，并将每个用户的历史cost之和加到计数器上面
  • 离线：
    假设用户量 1000w，历史订单 10亿 条（截止到 2021.3.27 零点）
    将用户所有的 user id 进行 hash 分发到 100(或者更多) 个服务器上面，每个服务器扫描历史订单计算 10w 用户的历史数据，然后利用 100 节点的最小根堆来统计前 100 的用户，同时每个用户的计算结果保存，发送更新到计数器内，实现计数器的历史值初始化
    100 个服务器跑完之后，搜集 100 个 前100 排行榜，然后统计 1w 用户的排行榜前100，得出初始化的排行榜，并保存。
  • 提供查询服务
    将排行榜保存（比如数据库内做备份，redis 做缓存），然后计数器每次增加都去查询一下是否超过排行榜的第100名（也需要判断自己是否在排行榜内），超过了就去更新排行榜。
    服务器集群通过查询 redis 进行排行榜的数据提供。（请求量可能特别大，导致 redis 扛不住，所以需要 local cache 存到本机，先查询 local cache，失效了再去请求 redis）。
    （单用户信息不一致问题）：如果利用了 local cache，会因为更新时间不同，导致不同的服务器上面内存信息不一致的现象，从而导致用户每次刷新看到的排行榜不一致。需要在排行榜上面添加一个 timestamp，表示当前排行榜生成的时刻，从而在客户端能够通过 timestamp 实现展示最新的排行榜的能力。
    （多用户信息不一致问题）：尽量缩短 local cache 的缓存时间（比如3s 或者 5s，这样 redis 能 hold 住请求量）

5. 后续简单聊了聊

面试官是在西瓜视频，然后转到了番茄小说，然后转到了电商。
让我继续等等，二面面试官马上来（啊！！！连面！！！好累~~~）

二面 2021.3.26 周五 11.20~12.13

1. 首先自我介绍

2. 没问基础，大概了解了一下实习内容，然后问了一下常见的debug方式

• 发现 goroutine 过多怎么办？怎么排查？
  几种情况：首先去看看是不是请求量激增，导致 goroutine 创建过多；然后可能是 goroutine 积攒，一般情况是数据读取部分阻塞了 goroutine，导致积攒过多；再去排查一下是不是代码里面循环创建 goroutine，排查一下循环条件是不是合法。

• 发现自己的代码 gc 过多，导致服务不稳定，怎么排查
  打点看看，比如接入公司内部的 grafana，看下对象数是不是过多，如果不是，那么查一下 go 的环境，是不是 gc 时间设置的太短了，导致频繁 gc；其次如果对象过多，那么考虑是不是可以复用对象，利用 go 的 pool 库来实现对象复用。

• 怎么查看日志
  跳板机跳到相关的服务器上面，然后用 linux 的 shell 语言去提取一下日志，看看是不是能看出一些问题。或者添加降级 debug 日志，打开降级开关，再去服务器上面看日志。公司也有动态日志的网页可以查看。

• 如果自己的服务频繁超时怎么办
  这会触发熔断机制，就是 grpc 框架的一个机制，当一个服务请求另一个服务，发现超时过多，就会阻断请求，返回默认值，让下游恢复一下。
  首先看下是不是自己的服务确实不稳定，然后排查一下耗时的操作，去看看能不能优化；还有就是如果自己的服务确实需要的时间比较长，比如 200ms，但是上游限制超时时间是 150ms，那就得沟通一下，让上游放宽超时限制。

• 火焰图知道么，简单说一下？
  火焰图展示的就是每个函数的调用延时，以及每个调用的函数的延时，从上到下，中间的空隙有可能就是操作系统层面的函数脱栈以及调度的耗时。如果发现了某个函数耗费时间比较大，就可以去相关的函数内部去优化对应的逻辑。

3. 然后问了一道系统设计

• 问题描述
  设计一个限流器，满足100w QPS 的限流。

• 我的思路
  令牌桶。100w的计数器，然后每次请求去获取令牌，拿到就请求，拿不到就丢弃或者等待，等待超时就丢弃。
  然后面试官问怎么实现？我回答了，然后不满足他的要求，让我继续优化。
  然后我说在代理层面做，他说不一定能抗住这么大的请求量，你的处理延时怎么处理。
  然后我说分发在每个服务器上面做，每个服务器限小流，然后如果负载均衡就可以实现整体限流满足要求。
  面试官说，你这得业务去写相关的逻辑？你不是在架构端实习了嘛
  我说，在 grpc 中间件中做，这样在业务生成代码的时候，grpc 中间层就生成好了。
  然后面试官说，那你还有别的设计方案么？
  我想不出来了，然后他的意思是我没满足他的要求（我也不太清楚他要我实现什么样子的要求。）

2. 突然思路回到了第二问

• 你不是用了 local cache 啊 redis 啊 abase 啊 mysql 啊，公司还有 ByteDB等，你说一下它们的区别？什么场景下用什么缓存？
  简单说了一下 mysql，分库分表 mysql，提升了查询能力，但是分库分表会导致 primary id 重复，因此 python 或者 go 操作的时候需要利用 sql 读取而不能用对象映射（否则同 id 会覆盖，导致读取的条数少）。
  他问：能不能解决这个问题？（能，说了一下第二个实习经历中的 SnowFlake 算法来生成 id，写入的时候指定 id，这样就不会重复了）
  继续问： redis 和 abase 呢？
  我说，redis 全在缓存内，所以支持的场景是请求量多，时延要求高，但是数据可丢失的情况，即便是公司内部有一种持久化 redis，它的持久化也是有延迟的，并不是 set 完就能落地，所以不能信任其落地措施。而 abase 则是可以实现 set 即落地，底层是通过分布式文件实现的，一个大文件分成很多小文件，查询的时候减少读取的io次数，从而提高并发量。
  问：那 abase 底层是怎么实现的？ 我说是通过 HDFS，但是具体我也没了解
  然后我继续说 local cache，local cache 的话，当时也调研了一些 go 的开源库实现方法（面试官打断了，不听了）

4. 然后出了一道算法题：

算法题1：

• 输入描述：
  输入一个列表 l，列表元素不重复；输入一个 s 值，表示所需和是 7
  输出一个列表 r，该列表包含所有的可能的列表情况（要求每个列表和为 s，元素从 l 获取，l 中的列表元素可以重复使用）

• 示例如下：

输入：[7, 3, 6, 2], 7
输出：[[7], [2, 2, 3]]

• 思路：
  先写了一段时间，但是在 debug 的时候，发现输出没有消重，然后在 debug 期间花了一点时间，面试官直接问我的思路是啥，我说我用的是回溯法，balabala 怎么实现，但是输出还没消重。
  面试官继续问：你是怎么剪枝的？我说通过排序剪枝。
  面试官：那你继续完成你的代码吧，实现出来

• 我的代码：

class Solution:
    def __init__(self):
        self.res = []
        
    def out(self, A, s):
        A.sort()
        self.A = A
        for i, a in enumerate(A):
            # 消重最终是在这里，未消重版本 for j in range(s//a, -1, -1)。
            # j 表示当前元素获取的个数，`-1`允许取 0 个 A[i] 元素，`0`表示必须至少一个 A[i] 元素，从而达到消重
            for j in range(s//a, 0, -1):
                pre = [a for _ in range(j)]
                self.get_list(pre, i+1, s-a*j)
        return list(self.res)
    
    def get_list(self, pre, i, s):
        if s == 0:
            self.res.append(pre)
            return
        if i >= len(self.A):
            return
        # print(pre, i, s)
        A = self.A
        if A[i] > s:
            return
        a = A[i]
        for j in range(s//a, -1, -1):
            r = pre.copy()
            r.extend([a for _ in range(j)])
            self.get_list(r, i+1, s-a*j)

if __name__ == "__main__":
    s = Solution()
    print(s.out([7, 3, 6, 2], 7))
    s = Solution()
    print(s.out([7, 3, 6, 2, 1], 7))

5. 终于结束了

面试官说看你对字节也蛮了解的，我们这边电商也发展很快，挺缺人手。balabala

6. 总结一下

系统设计题整体的开放性蛮大的，需要整体考虑，也费脑子，题目一上来觉得不好下手，不知道从哪儿切入，
而且面试官通常希望你能设计出来的方案考虑到业务需求和现实情况，所以会不断追问细节，
这种情况下，如果真的不会了，就应该多跟面试官交流，如果能聊得来，最好问问他，自己的方案还有哪儿没考虑到。

三面 2021.3.30 周二 10.30~11.08

1. 首先简单自我介绍，然后介绍了一下第二次实习的内容和情况

2. 问了一些基础知识（八股文背吧，我 TCP 相关的一些没背出来）

• 进程和线程的区别。

【面经】字节跳动-后台开发-2020.4.7

• 虚拟内存和共享内存是什么。

【面经】字节跳动-后台开发-2020.4.7

• 信号量是什么。

CSDN:操作系统之信号量
信号量简单理解就是锁，不过是计数器形式的锁。

• 原子操作是什么。

原子操作的实现原理
原子操作的原理其实就是通过锁进行的，锁寄存器，锁总线等。

• Http 和 Https 的区别。

【面经】字节跳动-后台开发-2020.4.7
讲了整个的协商流程以及加密原理

• TCP IP 四次挥手。

【面经】字节跳动-后端开发-2019秋招
连着三次握手流程一起讲了

• TCP 的 close wait 和 time wait 是什么，有啥区别

TIME_WAIT和CLOSE_WAIT状态区别
这个我讲错了，我以为是函数调用，结果是状态，自己balabala了半天。

• TCP IP 的拥塞控制是怎么实现的。

【面经】字节跳动-后端开发-2019秋招
知乎：TCP 拥塞控制算法

这个我讲了 1 2 3 的流程，但是不知道这是属于四个算法的。面试官问我，刚刚讲了几个算法了，我说。。我们不是一直在问基础知识嘛，有讲算法么？然后我说我不知道了。

• 解答：
  TCP拥塞控制主要有四种方法,滑动窗口机制、慢启动机制、拥塞避免机制、快速重传与恢复。
  • 滑动窗口机制
    在发送数据的时候，将发送窗口内的数据全部发送，才会停下来等待ACK，如果接收到对方的ACK信息，则滑动窗口前移。
  • 慢启动机制
    在刚开始发送数据的时候，发送窗口取一个较小的值，来防止网络拥塞，同时探测对方的接收能力。如果收到了对方的ACK回应，则按照对方要求的窗口大小来调整发送窗口，否则进行窗口的扩大。窗口大小一开始是1，之后进行指数级别扩大，其中ssthresh为估算的一个发送窗口阈值，当窗口大小超过这个阈值，则之后的窗口每次扩大1，不再是指数级别的扩大。
    还有一个概念是 AIMD（加法增大乘法减小）：无论在慢启动阶段还是在拥塞控制阶段，只要网络出现超时，就是将发送端的拥塞窗口（cwnd）置为1，ssthresh置为cwnd的一半，然后开始执行慢启动算法；当网络频发出现超时情况时，ssthresh就下降的很快，为了减少注入到网络当中的分组数，而加法增大是执行拥塞避免算法后，使拥塞窗口缓慢的增大，以防止网络过早出现拥塞。
  • 快速重传
    快重传算法要求首先接收方收到一个失序的报文段后立刻发出重复确认，而不要等待自己发送数据时才进行捎带确认。当发送方收到ACK之后，进行相应的报文重传。
  • 快速恢复
    当发送方连续收到三个重复确认时（代表丢了三个包），执行“乘法减小”算法，慢启动门限减半，从而预防网络发生阻塞。由于发送方现在认为网络很可能没有发生阻塞（因为没有超时），因此现在不执行慢启动算法，而是把拥塞窗口（cwnd）值设置为慢启动门限减半后的值，然后开始执行拥塞避免算法，拥塞窗口cwnd值线性增大

TCP和UDP是传输层协议（物理层、数据链路层、网络层、传输层、会话层、表示层、应用层）

UDP没有拥塞解决措施，当网络拥塞时，直接丢掉UDP的包。解决方式：在传输层之上，利用UDP并改造：如RUDP(传输层)、RTP(应用层和传输层之间)、UDT(应用层)等

3. 做了一道动态规划算法

环节点的走法数

动态规划了，设计了一下，然后讲了思路，面试官说思路没啥问题，就是你的 dp 得二维的，我跟他确认了一下。然后开始写。

最后的代码如下：

class Solution:
    def __init__(self):
        pass
        # dp[n][i]  i = dp[n-1][i-1] + dp[n-1][i+1]
        
    def A(self, N):
        dp = [[0 for _ in range(10)] for _ in range(N+1)]
        dp[1][9] = 1
        dp[1][1] = 1
        for n in range(2, N+1):
            for i in range(10):
                l, r = (i-1)%10, (i+1)%10
                dp[n][i] = dp[n-1][l] + dp[n-1][r]
            # print(dp)
        return dp[N][0]
                

if __name__ == "__main__":
    s = Solution()
    n = 6
    print(s.A(n))
    n = 10
    print(s.A(n))

    # 验证 6 10 的输出
    # 20
    # 254

4 你了解数据库么？估计想问点基础知识。

我说我了解，不过学校内学的是比较简单基础的，在第一次实习的时候也用了 mysql abase 和 redis。然后面试官也没继续问了。

5 常规结束，你有啥问题没？

简单问了一下面试官的具体业务：负责交易，涉及订单之类的。

HR 面 2021.4.07 周三 17.14~17.37

1. 基本上是简单聊了聊，问了一下之前的经历感悟，还有为什么想来这里，有没有其他的offer之类的。

我说我有美团 offer，那边是做大数据的，主要负责实时计算，他们催的急，我上午的时候已经拒绝了，准备来字节。
面试官说，我看你第一段实习的时候，是有过说想学大数据的，那怎么没考虑美团那边呢？
我说，当时是业务需求，需要跟大数据的 Hive 那边的分析师对接，所以想学习，这样能够减少业务沟通成本，不过后来自己也陆陆续续了解了一些了，所以作为实习，还是更愿意到自己完全不熟悉的环境来学习。之后工作了，可能就没有这样的机会了。

2. 然后聊了一下两次美赛的情况，面试官知道美赛是组队的，他问我我担任了什么角色呢？起到了什么作用？

美赛是三人组队，第一次和第二次都是同班的，所以一方面是都很熟悉，另一方面是都是计算机出身。
在第一段美赛，有一个出国的同学，她主负责英文论文撰写，我和另一个同学负责算法实现，当时选题 B，做新泽西的收费站数量预估，我们采用了元胞自动机。一开始我俩一起学习并编写算法，后续我脱离出来一部分精力去跟另一个队员沟通，来完成论文的撰写，所以最终我属于算法和论文都参与，同时架起了算法和论文的桥梁的作用。
在第二段美赛，我们选题是 C 题，主要做美国的石油产业走向的数据分析预测，组队的三个人不仅仅这次组队，在任何本科的大作业我们三个人都是优先组队的。因为三个人都具有挑战性，同时愿意把大作业弄得复杂一点，一起想办法实现，关系也很融洽，不会推脱事情。在我们队内部虽然名义上有队长，但是更多的是三个人分别都是队长，都会互相督促，互助互补。所以当时第二段美赛我们是三个人负责了所有流程，都是在一起互相分配任务，互相验收，互相吐槽，互相改进。

3. 然后聊了一下能实习几个月

我说之前都是4-6个月，这次也基本上能保证实习时长，后续如果能转正的话，也会考虑。因为第一段实习其实已经能转正来着，但是当时考虑到保研成功了，就先回学校上研究生了。

4. 结语

面试官说后续会有另一个HR同事联系我，给我发Offer。
这次聊完，我的 leader 很快跟我联系说，看见我的 offer 在审批了，如果可以的话可以先入职，在学校工作。（我也想早点实习，奈何现在在弄论文，没有别的精力了，o(╥﹏╥)o）

HR Offer 发放 2021.4.13

HR 小姐姐终于加我的微信了，说给我发了 offer，问我，是不是很熟悉流程了，就不多说了，我说好的，然后十分钟填完信息，回复实习确认。暂定 6.14 入职。