大疆秋招笔试第二套

选择：红黑树什么时候会反转、哪个页面置换算法会触发belady
多选：（分值最高），inode、进程优先级会影响调度的什么、有关分库的场景方案哪个是正确的、排序是否稳定

整体来说，这里笔试算有意义的一些题目了，不过还是有几个比较偏的。

规则特性：编程题可以返回重复改，可以用本地ide

编程题，比上一次简单很多多，一个飞机走一个 01数组，初始朝右遇到1或者边界顺时针转90，最终能遍历到多少个块。
我直接模拟，不知道为什么只过了三个答案用例。一个小时都在想这个了，选择题根本没挣扎余地
希望有大佬做出来的说下可能的原因

--
每次这种编程题只能过一半就特别痛苦，基本能过的情况十几分钟就写出来，找后面的情况浪费很多没用的时间，不重要的笔试这种情况还是直接放弃性价比更高一点。
我自己有反思过，一般就是分边界情况和逻辑不完全正确。后者一般我就多清空一下思路，多重新看看题，但是很多时候还是没办法发现问题。有经验的牛佬也希望能分享下

--
然后我平常确实非常不喜欢过笔试题，所以还是应该抓住机会现场学习好。这次应该快结束再看一遍前面选择题的。

下面直接过一下笔试内容：

红黑树：完全不想学原理，直接记结论
插入节点时的反转情况 —— 插入节点的父节点和叔叔节点都是红色
删除节点时的反转情况 —— 删除节点导致的双重黑色

 稳定排序
- ologn 里边只有归并是稳定的，因为归并合并子问题用的是合并两个有序数组那种算法，是能保证相对顺序的
- on 插入选择冒泡，只有选择是不稳定的
（艹这个我选错了。我当时不知道为什么跟插入搞混了）
插入稳定是因为你是按顺序去从后面找元素插入的，插入的时候也保证相对顺序就行；
而选择是每次都选择最值，假如你有多个最值，你原来的顺序，和你应该要插入的顺序容易出现矛盾
具体我们看一个例子：[4, 3, 2, 3, 1]
操作的时候，第二个2会因为最小值的规则跑道前面来
- 其他排序，希尔不稳定，别的都稳定

 页面置换
- belady：增加页框命中率反而降低的异常现象
- 结论：fifo是会触发的

 一个inode可能对应多个文件吗？
我理解应该是不能对应多个文件，但是能对应多个文件名

复习linux文件系统
- 文件：文件实际是硬盘上的区域
- inode：存储文件元信息，主要就是文件是怎么存在磁盘上
- 目录和文件名：文件名是我们直接看到的东西，目录用来组织文件名的，多个文件名对应同一inode就是硬连接

 进程优先级具体有哪些影响？
方面：调度算法选择权重、响应时间 / 饥饿老化可能性、资源时间片、抢占优先级
具体选项：
- 会影响调度队列中的顺序
- 在抢占起作用，但是不仅在
- 在某些调度算法中，会获得更长cpu时间，但是不一定

扩展：sre 相关操作
- `$ ps -eo pid,comm,pri,nice` 查看优先级
- `nice 设置进程优先级`

--

#大疆#