依图一面二面三面面经(已拿Offer)

2019年03月19日 晚上突然收到 hr 电话要发offer，本来以为都凉了

感觉依图大部分都是算法题，一二面都写出来了，三面来了一个看起来很厉害的大佬，有自己的办公室，用后面的白板给我出了道物理题还是数学题让我做。

隔了两周了，问题忘得差不多了，把能记住的写下来。

一面

1. 自我介绍
2. 打一段自己熟悉的算法代码，并讲解
3. 堆和栈的区别
4. 手撕代码，两个有序数组中找第k大
5. 手撕代码，一个矩阵填数的模拟题
6. 剩下的好像问了一些网络和操作系统相关的，忘了，毕竟一周前了

二面

1. 说一下什么是 I/O 复用
2. 说一下select 和 epoll
3. 写题，一个dfs,大意是有一个 n*m 的图，上下左右的值相差 1 可以连成一个块，让你输出一个新图，把每个块用0 1 2 3...标记。
4. 一个 1-n 的数组丢了 1 个数，找出来
5. 一个 1-n 的数组丢了 2 个数，找出来
6. 一个 1-n 的数组丢了 3 个数，找出来
7. 还手撕了两个编程题，忘了是啥了
8. 然后就谈人生，谈一下打比赛的经历

三面

看起来是个大佬，有自己独立办公室

1. 分析一下最小生成树复杂度。不是两个算法的复杂度，是最小生成树这个问题本身的复杂度
2. 分析一下排序这个问题本身的复杂度（不是算法复杂度）

这俩题我都蒙了，不让我扯算法，让我说这个问题本身，我最后扯了扯决策树，然后大概就完了

还出了一道数学题

1. 光滑的长为 L 的轨道上，有 n 个无摩擦的小球，每个小球的速度的值一样，但是方向不一样（方向只有左右两个方向），给出每个小球的位置，以及每个小球的方向，问你最后一个小球离开轨道的时间是多少？

然后大概扯了扯其他的方面，聊一聊人生。