Aug 1

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

felix021 @ 2020-8-1 22:31 [IT » 程序设计] 评论(0) , 引用(0) , 阅读(1872) | Via 本站原创 | |
- 鹅厂 -

在遥远的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)




欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]