题图无关，因为想到鹅厂，就想到企鹅，而后就想到打企鹅（非洲版），而后就裸露年龄了[doge]

– 鹅厂 –

在边远的 2009 年，那时候“呵呵”还没有奇怪的意思，我笑呵呵地去加入了鹅厂的实习招聘。

面试被安顿在面试官下榻酒店的房间里，校门口的 ** 王朝大酒店，可能一早晨能顶我一个月生活费那种。

过程聊得应该还能够，不过大部分细节都忘了，只记得最初那道代码题，一张纸，一支笔。

题面很简略：写一个 C 函数，合并两个 有序 数组。

–“最好能通用一点”，面试官补充说。

–“能够用 C++ 模板吗？”

–“最好还是用 C。”

好多年当前，当我开始面试他人了，发现这道题的确很好用。

– 解 –

学过归并排序的同学应该都会感觉这个题目并不难，只不过是其中的一次归并环节。

其基本思路是，用两个指针，别离从数组的第一个元素开始，顺次比拟，每次找到最小的元素存入新数组，而后将指针挪动到下一位。

须要留神的是当一个数组被取完当前，还得解决另一个数组的残余元素。

而所谓“通用”，是指数组的元素能够是任意类型，因而须要把数组元素的大小、用于比拟的函数也作为参数传进去。

大略就是要实现这样的一个函数：

typedef int cmpfunc(void *x, void *y);
void* merge(void *A, int m, void *B, int n, int size, cmpfunc f);

其中 m、n 别离示意 A、B 这两个数组的长度，size 示意数组元素的大小。

具体实现的 C 代码比拟琐碎，就不在这里贴出来了，感兴趣的同学能够本人试着写一下。

– WHY –

我在上一家公司，通常用这道题当口试的压轴题，但不限度语言，以及去掉了对“通用”的要求。

为什么选它呢？

首先 ，它很 容易了解，不会产生歧义，不须要额定解释。

其次 ，在纸面上编码（至多是脱离 IDE），程序员在 编码前得想分明；涂改较多也阐明一些问题。

最重要的是 ，它有很好的 区分度，因为真的有很多程序猿没认真学过归并排序。

但至多每个人都能想到将两个数组合并，而后进行排序。

有些特地间接的小伙伴，就用了 PHP 自带的 sort 函数，起初咱们不得不加个阐明：“防止应用库函数”。

至于排序算法，有人写冒泡，也有人写快排；快排的实现，又能够考查是不是在数组里做原地划分（大部分是拆到两个数组里再合并）。

并且，咱们在题面上顺便对 有序 两个字加粗、加下划线，疏导候选人应用最优解法。

如果候选人最终依然实现了排序解法，在面试中还能够再提醒，是否能用上“有序”这个条件，进一步提高性能。

这样层层递进，可能较好地帮忙咱们判断候选人的编码能力。

不过机关算尽，还是遇到了比拟挫败的 case，比方一个候选人就反诘：零碎自带的函数效率最高啊，为什么要本人实现？

– 字节 –

到了字节跳动后，我发现这道题有点不够用了，撑死只能算 LeetCode Easy，对于有勇气来面试字节的候选人，通常都不在话下。

为了把它降级到 Medium，我想到了两个改变：

1. 两个不够，m 个来凑
2. 数组太简略，得换成链表

而后一看，诶，这 tm 不就是 LeetCode 23 原题吗？

话说回来，这题就变成了：请把 m 个有序链表合并成一个新的有序链表；均匀每个链表有 k 个节点。

– 解² –

不用说，所有候选人都能想到每次遍历所有链表、找到最小值退出新的链表。

对于抉择这个思路的候选人，接下来的问题是：

Q1：这个计划的工夫复杂度是多少呢？

有不少候选人答复 O(m * k)，大略是感觉两个链表合并是 O(2 * k)，m 个链表合并天然是 O(m * k) 了。

实际上，应用这种思路，每次找到最小值须要一一比拟 m 个链表，这个操作须要执行 m * k 次（节点总数），因而总的工夫复杂度应该是 O(m^2 * k)。

Q2：还有优化空间吗？

有些候选人的确想不到更优的解法，但只有能按这思路实现 bug free 的代码，综合面试中的其余体现，也能够通过咱们的考查（详见 程序员面试指北：面试官视角）。

毕竟 LeetCode 23 原题可是 Hard 级别。

– 分治 –

对分治算法比拟相熟的候选人会想到，能够先两两合并，失去的 m / 2 个链表再两两合并，循环这个过程，直到只剩下一个链表。

而后又回到 Q1：这个计划的工夫复杂度是多少呢？

这答复就千奇百怪了，O(m * log(k))，O(k * log(m)), O(m * k * log(k))……

这个计算其实不难：

• 第一轮须要 m/2 次两两合并，每次两两合并是 2k 次比拟，共计 m*k
• 第二轮须要 m/4 次两两合并，每次两两合并是 4k 次比拟（每个链表均匀长度变成 2k 了），共计还是 m*k
• ……
• 对 m 个元素做二分，总共须要 log(m) 轮

所以正当的答案应该是 O(m * k * log(m))。

具体实现又能够分成高低两局部。

上层应该实现一个合并俩链表的逻辑，比拟常见的谬误是没能正确处理链表的头结点（比方间接当成尾节点用，或者遗记初始化，以及 C++ 小伙伴用了 new 当前经常忘了 delete），还有后面说到的，一个链表摘空了后，须要解决另一个链表剩下的节点。

下层的实现其实和归并排序长得一毛一样，能够 bottom-up，也能够 top-down。bottom-up 的实现常见的谬误是没解决好落单的那一个，而 top-down 则须要留神递归的终止条件。

另外有点意外的是，不少 Java 小伙伴被 List 这个 Interface 荼毒还挺深，在编码的时候棘手就用 List.get(i)，齐全不思考这个 API 的开销。

– 最小堆 –

对常见数据结构比拟相熟的候选人则会提出应用最小堆，这样能够将每次查找最小值的工夫复杂度降为 log(m)，于是总的工夫复杂度也能够降为 O(m * k * log(m))。

既然提到了堆，那就能够顺便问一下，最小元素从堆顶被摘掉当前，如何调整堆？

于是那些只晓得能够用最小堆、不晓得如何实现堆的候选人就裸露进去了。

不过也不打紧，大部分语言的库里都实现了 PriorityQueue 这个数据结构，让候选人间接用语言提供的版本来编码就好。

具体的代码次要有两个坑，一是循环中要留神对摘空链表的解决，二是对链表头结点的解决（后面提到了）。

– 没完 –

面试到下面的水平就足够了，不然 45 分钟切实是不够用。

但其实还有些值得思考的问题没讲完。

比如说，这两种算法，均匀工夫复杂度都是 O(m * k * log(m))，到底哪一个更好呢？

分治算法的劣势是，两两合并时，当一个链表为空，能够间接将另一个链表的残余节点串起来，相比于堆算法能够节约一些工夫。

另一方面，对于这样一个经典的多路归并问题，理论应用场景可能是要合并外存上的多个排好序的文件，这时候堆算法能够节约磁盘 IO（只须要一次遍历），相比于分治算法就有了压倒性的劣势。

所以具体还是要看场景。

再比方，在这个场景下，堆并不是最高效的数据结构。

实际上，堆算法只是多路归并的晚期实现，因为每一层的调整都须要两次比拟（先取出两个子节点的较小者，而后再和以后节点比拟），其效率还有优化空间。

（堆的调整）

如果咱们将用于比拟的节点作为叶子节点构建一棵齐全二叉树，从叶子节点往上只保留获胜的节点：

这样每一层只须要和其兄弟节点做比拟即可。这就是所谓“胜者树”，说起来还是空间换工夫的套路(多一倍的节点数）。

还没完 —— 这个计划对每一层的更新依然须要拜访 3 个节点（本人、兄弟节点，父节点），换个思路，如果咱们在门路上只保留失败的值，再用一个额定的变量保留在根节点比拟的获胜者：

于是咱们对每一层的更新只须要拜访以后节点和其父节点就好了。

因为每次保留的是失败者，这个计划又被称为“败者树”。

– 小结 –

这篇没有贴具体的代码，没试过的同学，正好能够用 LeetCode 23 来练手（传送门）。

照例小结一下：

• 口试 / 面试题的区分度很重要；
• 归并排序是根底，bottom-up 和 top-down 都要熟；
• 多路归并能够用分治和堆来解决，工夫复杂度最优；
• 通过败者树能够进一步优化堆的解法。

创作不易，喜爱本文的小伙伴，别忘了点赞以及分享给你的小伙伴，感激~

举荐浏览：

• 程序员面试指北：面试官视角
• 踩坑记：go 服务内存暴涨
• TCP：学得越多越不懂
• UTF-8：一些如同没什么用的冷常识
• (译) C程序员该晓得的内存常识 (1)

欢送关注