标题：又是面试题？对，合并有序序列。 出处：Felix021 时间：Sat, 01 Aug 2020 22:31:41 +0000 作者：felix021 地址：https://www.felix021.com/blog/read.php?2229 内容： - 鹅厂 - 在遥远的2009年，那时候“呵呵”还没有奇怪的意思，我笑呵呵地去参加了鹅厂的实习招聘。 面试被安排在面试官下榻酒店的房间里，校门口的**王朝大酒店，可能一晚上能顶我一个月生活费那种。 点击在新窗口中浏览此图片 https://www.felix021.com/blog/attachment.php?fid=575 过程聊得应该还可以，不过大部分细节都忘了，只记得最后那道代码题，一张纸，一支笔。 题面很简单：写一个 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，比如一个候选人就反问：系统自带的函数效率最高啊，为什么要自己实现？ 点击在新窗口中浏览此图片 https://www.felix021.com/blog/attachment.php?fid=576 - 字节 - 到了字节跳动后，我发现这道题有点不够用了，撑死只能算 LeetCode Easy，对于有勇气来面试字节的候选人，通常都不在话下。 为了把它升级到 Medium，我想到了两个改动： 1. 两个不够，m个来凑 2. 数组太简单，得换成链表 然后一看，诶，这 tm 不就是 LeetCode 23 原题吗？ 点击在新窗口中浏览此图片 https://www.felix021.com/blog/attachment.php?fid=577 话说回来，这题就变成了：请把 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 的开销。 点击在新窗口中浏览此图片 https://www.felix021.com/blog/attachment.php?fid=578 - 最小堆 - 对常见数据结构比较熟悉的候选人则会提出使用最小堆，这样可以将每次查找最小值的时间复杂度降为 log(m) ，于是总的时间复杂度也可以降为 O(m * k * log(m))。 既然提到了堆，那就可以顺便问一下，最小元素从堆顶被摘掉以后，如何调整堆？ 于是那些只知道可以用最小堆、不知道如何实现堆的候选人就暴露出来了。 不过也不打紧，大部分语言的库里都实现了 PriorityQueue 这个数据结构，让候选人直接用语言提供的版本来编码就好。 具体的代码主要有两个坑，一是循环中要注意对摘空链表的处理，二是对链表头结点的处理（前面提到了）。 - 没完 - 面试到上面的程度就足够了，不然 45 分钟实在是不够用。 但其实还有些值得思考的问题没讲完。 比如说，这两种算法，平均时间复杂度都是 O(m * k * log(m))，到底哪一个更好呢？ 分治算法的优势是，两两合并时，当一个链表为空，可以直接将另一个链表的剩余节点串起来，相比于堆算法可以节约一些时间。 另一方面，对于这样一个经典的多路归并问题，实际使用场景可能是要合并外存上的多个排好序的文件，这时候堆算法可以节约磁盘IO（只需要一次遍历），相比于分治算法就有了压倒性的优势。 所以具体还是要看场景。 再比如，在这个场景下，堆并不是最高效的数据结构。 实际上，堆算法只是多路归并的早期实现，由于每一层的调整都需要两次比较（先取出两个子节点的较小者，然后再和当前节点比较），其效率还有优化空间。 点击在新窗口中浏览此图片 https://www.felix021.com/blog/attachment.php?fid=579 （堆的调整） 如果我们将用于比较的节点作为叶子节点构建一棵完全二叉树，从叶子节点往上只保存获胜的节点： 点击在新窗口中浏览此图片 https://www.felix021.com/blog/attachment.php?fid=580 这样每一层只需要和其兄弟节点做比较即可。这就是所谓“胜者树”，说起来还是空间换时间的套路(多一倍的节点数）。 还没完 —— 这个方案对每一层的更新仍然需要访问3个节点（自己、兄弟节点，父节点），换个思路，如果我们在路径上只保存失败的值，再用一个额外的变量保存在根节点比较的获胜者： 点击在新窗口中浏览此图片 https://www.felix021.com/blog/attachment.php?fid=581 于是我们对每一层的更新只需要访问当前节点和其父节点就好了。 由于每次保存的是失败者，这个方案又被称为“败者树”。 - 小结 - 这篇没有贴具体的代码，没试过的同学，正好可以用 LeetCode 23 来练手（传送门）。 照例小结一下： * 笔试/面试题的区分度很重要； * 归并排序是基础，bottom-up 和 top-down 都要熟； * 多路归并可以用分治和堆来解决，时间复杂度最优； * 通过败者树可以进一步优化堆的解法。 喜欢本文的小伙伴，别忘了分享给你的小伙伴，感谢~ --- 推荐阅读： * 程序员面试指北：面试官视角 * 踩坑记：go服务内存暴涨 * TCP：学得越多越不懂 * UTF-8：一些好像没什么用的冷知识 * (译) Ｃ程序员该知道的内存知识 (1) Generated by Bo-blog 2.1.0