V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
felix021
V2EX  ›  程序员

又是面试题?对,合并有序序列。

  •  1
     
  •   felix021 ·
    felix021 · 2020-08-01 15:25:14 +08:00 · 2903 次点击
    这是一个创建于 1335 天前的主题,其中的信息可能已经有所发展或是发生改变。

    - 鹅厂 -

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

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

    你从我脸上看到了什么-穷.jpg

    过程聊得应该还可以,不过大部分细节都忘了,只记得最后那道代码题,一张纸,一支笔。

    题面很简单:写一个 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 ),程序员在编码前得想清楚;涂改较多也说明一些问题。

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

    反正我信了.png

    但至少每个人都能想到将两个数组合并,然后进行排序。

    有些特别直接的小伙伴,就用了 PHP 自带的 sort 函数,后来我们不得不加个说明:“避免使用库函数”。

    至于排序算法,有人写冒泡,也有人写快排;快排的实现,又可以考察是不是在数组里做原地划分(大部分是拆到两个数组里再合并)。

    并且,我们在题面上特地对 有序 两个字加粗、加下划线,引导候选人使用最优解法。

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

    这样层层递进,能够较好地帮助我们判断候选人的编码能力。

    不过机关算尽,还是遇到了比较挫败的 case,比如一个候选人就反问:系统自带的函数效率最高啊,为什么要自己实现?

    很有道理无法反驳 s.jpg

    - 字节 -

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

    为了把它升级到 Medium,我想到了两个改动:

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

    然后一看,诶,这 tm 不就是 LeetCode 23 原题吗?

    送分题 s.jpg

    话说回来,这题就变成了:请把 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 的开销。

    sigh.png

    - 最小堆 -

    对常见数据结构比较熟悉的候选人则会提出使用最小堆,这样可以将每次查找最小值的时间复杂度降为 log(m) ,于是总的时间复杂度也可以降为 O(m * k * log(m))。

    既然提到了堆,那就可以顺便问一下,最小元素从堆顶被摘掉以后,如何调整堆?

    于是那些只知道可以用最小堆、不知道如何实现堆的候选人就暴露出来了。

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

    具体的代码主要有两个坑,一是循环中要注意对摘空链表的处理,二是对链表头结点的处理(前面提到了)。

    - 没完 -

    面试到上面的程度就足够了,不然 45 分钟实在是不够用。

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

    比如说,这两种算法,平均时间复杂度都是 O(m * k * log(m)),到底哪一个更好呢?

    分治算法的优势是,两两合并时,当一个链表为空,可以直接将另一个链表的剩余节点串起来,相比于堆算法可以节约一些时间。

    另一方面,对于这样一个经典的多路归并问题,实际使用场景可能是要合并外存上的多个排好序的文件,这时候堆算法可以节约磁盘 IO (只需要一次遍历),相比于分治算法就有了压倒性的优势。

    所以具体还是要看场景。

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

    实际上,堆算法只是多路归并的早期实现,由于每一层的调整都需要两次比较(先取出两个子节点的较小者,然后再和当前节点比较),其效率还有优化空间。

    heap.png

    (堆的调整)

    如果我们将用于比较的节点作为叶子节点构建一棵完全二叉树,从叶子节点往上只保存获胜的节点:

    胜者树.png

    这样每一层只需要和其兄弟节点做比较即可。这就是所谓“胜者树”,说起来还是空间换时间的套路(多一倍的节点数)。

    还没完 —— 这个方案对每一层的更新仍然需要访问 3 个节点(自己、兄弟节点,父节点),换个思路,如果我们在路径上只保存失败的值,再用一个额外的变量保存在根节点比较的获胜者:

    败者树.png

    于是我们对每一层的更新只需要访问当前节点和其父节点就好了。

    由于每次保存的是失败者,这个方案又被称为“败者树”。

    - 小结 -

    这篇没有贴具体的代码,没试过的同学,正好可以用 LeetCode 23 来练手(传送门)。

    照例小结一下:

    • 笔试 /面试题的区分度很重要;
    • 归并排序是基础,bottom-up 和 top-down 都要熟;
    • 多路归并可以用分治和堆来解决,时间复杂度最优;
    • 通过败者树可以进一步优化堆的解法。

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


    推荐阅读:


    欢迎关注

    weixin1.png

       ▄▄▄▄▄▄▄   ▄      ▄▄▄▄ ▄▄▄▄▄▄▄  
       █ ▄▄▄ █ ▄▀ ▄ ▀██▄ ▀█▄ █ ▄▄▄ █  
       █ ███ █  █  █  █▀▀▀█▀ █ ███ █  
       █▄▄▄▄▄█ ▄ █▀█ █▀█ ▄▀█ █▄▄▄▄▄█  
       ▄▄▄ ▄▄▄▄█  ▀▄█▀▀▀█ ▄█▄▄   ▄    
       ▄█▄▄▄▄▄▀▄▀▄██   ▀ ▄  █▀▄▄▀▄▄█  
       █ █▀▄▀▄▄▀▀█▄▀█▄▀█████▀█▀▀█ █▄  
        ▀▀  █▄██▄█▀  █ ▀█▀ ▀█▀ ▄▀▀▄█  
       █▀ ▀ ▄▄▄▄▄▄▀▄██  █ ▄████▀▀ █▄  
       ▄▀▄▄▄ ▄ ▀▀▄████▀█▀  ▀ █▄▄▄▀▄█  
       ▄▀▀██▄▄  █▀▄▀█▀▀ █▀ ▄▄▄██▀ ▀   
       ▄▄▄▄▄▄▄ █ █▀ ▀▀   ▄██ ▄ █▄▀██  
       █ ▄▄▄ █ █▄ ▀▄▀ ▀██  █▄▄▄█▄  ▀  
       █ ███ █ ▄ ███▀▀▀█▄ █▀▄ ██▄ ▀█  
       █▄▄▄▄▄█ ██ ▄█▀█  █ ▀██▄▄▄  █▄  
    
    第 1 条附言  ·  2020-08-01 18:06:16 +08:00
    [勘误] 败者树的根节点 value 应该是 2 而不是 5 。
    14 条回复    2020-08-01 22:48:55 +08:00
    msg7086
        1
    msg7086  
       2020-08-01 16:00:32 +08:00
    之前刚面了一家公司,起手问的就是合并 k 个有序链表。
    直接报的小顶堆归并,排堆不需要自己写,开个循环直接拿小顶项接链表,完事。
    yuruizhe
        2
    yuruizhe  
       2020-08-01 17:32:49 +08:00
    直接调用 m-1 次“2 个链表合并”,好像还有问题,如果贪心优先合并两个最短的链表,无法确保合并次数最少;得靠石子合并问题的动归,才能确定合并的顺序。。。。
    yuruizhe
        3
    yuruizhe  
       2020-08-01 17:42:39 +08:00
    @yuruizhe 不对,这个合并与石子合并不一样,应该可以贪心选择最短的两个 list 进行合并,类似哈夫曼树思想
    felix021
        4
    felix021  
    OP
       2020-08-01 18:06:30 +08:00
    [勘误] 败者树的根节点 value 应该是 2 而不是 5 。
    felix021
        5
    felix021  
    OP
       2020-08-01 18:07:29 +08:00
    @yuruizhe 看起来好像可以在常数上做一点优化,但是别忘了算上每次选择最短的两个 list 带来的额外开销。
    Actrace
        6
    Actrace  
       2020-08-01 18:19:02 +08:00
    笑死我了,PHP 又被嘲讽了。
    此贴要火。
    顺路问一下,老哥,库函数不能用的话,我还用 PHP 干做啥子?不限制语言是个摆设咯。
    PHP 真的适合吊打算法玩家。
    felix021
        7
    felix021  
    OP
       2020-08-01 18:49:25 +08:00
    @Actrace
    1. 嘲讽的不是 php,虽然我确实不喜欢 php,但毕竟也用了好多年,用不着嘲讽。
    2. “面试中不能用”和“工作中不能用”,你品品这差别。
    liuxingdeyu
        8
    liuxingdeyu  
       2020-08-01 18:58:30 +08:00
    我看到首先想到的居然是双指针,先用插入的数组的首尾找到位置,然后在这区间之内找剩下数的位置,但是这样的做法用的时间实在是抽奖。。。
    zgzb
        9
    zgzb  
       2020-08-01 19:31:09 +08:00 via Android
    看的一头雾水,还好没学编程
    knowckx
        10
    knowckx  
       2020-08-01 20:06:05 +08:00   ❤️ 2
    看完了,文章里浓浓的字节味。
    ajinwu
        11
    ajinwu  
       2020-08-01 21:03:42 +08:00
    寻思字节面试全是算法就完了, 45 分钟就做做题
    sampeng
        12
    sampeng  
       2020-08-01 21:12:18 +08:00 via iPhone
    第一反应是最小堆…但没细想…
    felix021
        13
    felix021  
    OP
       2020-08-01 21:51:18 +08:00 via Android
    @sampeng 嗯,很多人都能想到最小堆,但是落地写代码更重要
    sampeng
        14
    sampeng  
       2020-08-01 22:48:55 +08:00 via iPhone
    @felix021 嗯,很多时候知其然也知其所以然,但是没实际用过…你说到底算是会还是不会呢?说不会吧,花点时间也能搞出来,毕竟思路在那,说会吧,直接写不出来就是不会。其实我个人倾向后者,你有一句说得好,手写代码最大的好处不是看一个人编码能力,而是在写之前就一定要想清楚再下笔…当然我这种写两行就要调试一下就没法玩了。但意思是这么个意思嘛…
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3229 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 38ms · UTC 11:40 · PVG 19:40 · LAX 04:40 · JFK 07:40
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.