Aug
20
简单记一下：
或者
$ cat curl-format.txt
time_namelookup: %{time_namelookup}\n
time_connect: %{time_connect}\n
time_appconnect: %{time_appconnect}\n
time_pretransfer: %{time_pretransfer}\n
time_starttransfer: %{time_starttransfer}\n
$ curl -w '@curl-format.txt' -o /dev/null -s -L "https://www.baidu.com"
time_namelookup: 0.004
time_connect: 0.018
time_appconnect: 0.050
time_pretransfer: 0.050
time_starttransfer: 0.065
time_namelookup: %{time_namelookup}\n
time_connect: %{time_connect}\n
time_appconnect: %{time_appconnect}\n
time_pretransfer: %{time_pretransfer}\n
time_starttransfer: %{time_starttransfer}\n
$ curl -w '@curl-format.txt' -o /dev/null -s -L "https://www.baidu.com"
time_namelookup: 0.004
time_connect: 0.018
time_appconnect: 0.050
time_pretransfer: 0.050
time_starttransfer: 0.065
或者
$ go get github.com/davecheney/httpstat
$ httpstat https://www.baidu.com
...
DNS Lookup TCP Connection TLS Handshake Server Processing Content Transfer
[ 0ms | 9ms | 105ms | 10ms | 0ms ]
| | | | |
namelookup:0ms | | | |
connect:10ms | | |
pretransfer:116ms | |
starttransfer:126ms |
total:126ms
$ httpstat https://www.baidu.com
...
DNS Lookup TCP Connection TLS Handshake Server Processing Content Transfer
[ 0ms | 9ms | 105ms | 10ms | 0ms ]
| | | | |
namelookup:0ms | | | |
connect:10ms | | |
pretransfer:116ms | |
starttransfer:126ms |
total:126ms
Aug
8
最近老是想起陈芝麻烂谷子的事情，说明工龄所剩无几了。
- 1 -
又是在那遥远的 2009 年，那个“杯具”已经不是杯具的年头，度厂办个算法比赛，办出了点儿杯具的味道。
比赛的名字叫“百度之星”，那些年在校园里影响力还蛮大的（好像现在还是），大概赛制就是通过初赛、复赛、决赛这么几轮，选出几个社会主义四有青年瓜分奖金。值得一提的是，头两年（05、06）冠军都被楼教主承包了。
为什么说有点杯具的味道呢，因为那年的初赛结束以后，度厂搞了个骚操作，把所有参赛选手提交的代码导出来，打了个包，发在贴吧里。
于是贴吧突然就炸了。
- 2 -
要知道初赛是网络赛，各个学校的 ACM（或OI） 集训队的队员们很可能都是凑在机房一起参与，毕竟毛主席教导我们人多力量大嘛。
所以这就有点意思了：如果同一个题，两份代码长得很像，说明互相抄袭概率就很大。
问题是参赛人数有点多，两两对比这 O(n^2) 的时间复杂度，靠人肉有点儿吃不消；但这么大一个瓜，光看不吃又有点可惜了。
那么这瓜到底该怎么吃呢？
- 3 -
还好，作为一个竞赛战五渣的我，通过初赛的能力没有，搞事情的能力还是有一点的。
为了对比两份代码的相似度，那我首先得找到一个指标。
作为一个善于作弊 思考的社会主义三无青年，我估计作弊者在拿到弊友代码后不会直接提交，至少会做些更换变量名之类操作；但竞赛时间紧迫，大概率来不及修改整体框架。
那么，只要我能算出修改的程度，就能判断相似度了：假设两份代码长度分别是 m、n，修改了 x 个字符， 我们大致可以把 `100% - x / ((m + n) / 2)` 当成相似度（没被修改的字符占比）。
但如何计算这修改的程度呢？毕竟修改前后代码长度很可能不同，不适合通过逐字比较来找到差别。
- 4 -
既然直接处理两段代码有点棘手，那不妨先考虑一下简单的 case 。
比如说要将字符串 "a" 改成 "b"，这个简单，只要改一个字符就行。
又比如说要将字符串 "a" 改成 "ab"，这个也简单，只要添加一个字符就行。
再比如说要将字符串 "ab" 改成 "b"，这个依然简单，只要删除一个字符就行。
如果我能算出将一段字符串通过添加、删除、修改三种操作修改成另一个字符串的最少操作次数，应该就能把这瓜给吃了。
好像是找到了方向，但是要怎么实现呢？
- 5 -
既然直接处理两段代码还是有点棘手，那不妨再考虑一下稍微复杂一点的 case ，比如把字符串 X = "baidu" 变成 Y = "bytedance"。
首先，因为 X[0] 和 Y[0] 相同，我们可以把问题简化成：将 "aidu" 变成 "ytedance"，即 X[1..4] => Y[1..8]（后面简记为 X[1:] => Y[1:]）。
接着，X[1] = 'a', Y[1] = 'y'，如上一节所说，这时候我们有三种选择：
* 添加：给 X 添加 'y' ，当成 "byaidu"，于是问题简化为将 "aidu" 变成 "tedance"，即 X[1:] => Y[2:]；（注意，我们在这里把该操作当成一个思维实验就好，不需要真的修改 X ，所以这里 "aidu" 对应 X[1:] 而不是 X[2:]）
* 删除：从 X 中删掉 'a' ，当成 "bidu"，问题简化为将 "idu" 变成 ytedance"，即 X[2:] => Y[1:]；
* 修改：把 X 这个 'a' 改成 'y'，当成 '"byidu"，问题简化为将 "idu" 变成 "tedance"，即 X[2:] => Y[2:]；
这三种操作中，后续需要的修改次数最少的那个，再加上 1，就是我们把 X[1:] 改成 Y[1:] 所需的最少次数。
依此类推，如果我们将 X[i:] 变成 Y[j:] 需要 f(i, j) 次操作，由上可得到这样一个公式：
也就是说，我们可以用子问题的最优解来推导出问题的最优解，如果用不说人话的方式，就叫做该问题存在最优子结构。
这么一看，代码是不是呼之欲出了？
- 6 -
啰嗦了这么多，不能忘了大佬的教导：
说干就干，把上面推导的公式落地成代码，so easy：
然后跑起来一看：
- 7 -
"index out of range"，越界了 —— 显然，这里漏掉了递归的终止条件。
不过这个简单：如果 X 越界了，说明这时 i == len(X)，那么 Y 还剩几个字符，我们都加上就行，即还需要 len(Y) - j 次操作；或者 Y 越界了，说明 j == len(Y)，我们把 X 剩下的几个字符删掉，即 len(X) - i 次操作。
于是代码变成了：
跑起来效果杠杠的，马上就得到了 7，算得没毛病。
只可惜这代码还没法用 —— 别说跑那些参赛代码，就连长度为 16 的两个字符串都跑不出结果……
- 8 -
稍微分析一下我们就会发现，它竟然是指数时间复杂度的：
不过仔细观察上图（不仔细也没关系，我给红色高亮了），我们可以发现，为了计算 f(i, j)，我们需要计算 f(i + 1, j + 1)；而且它也被用于计算 f(i, j + 1) 和 f(i + 1, j) 。
这意味着这个问题存在重复子问题，类似于我们用 f(i) = f(i - 1) + f(i - 2) 计算飞波纳妾 fibonacci 数列。
因此我们完全可以将 f(i, j) 存下来、避免重复计算，就像这样：
注：实际上这里也可以直接用一个二维数组 f[i][j] 来保存 f(i, j)，对 C/C++ 来说实现会更容易，读写效率也更高。
优化以后，因为每个 f(i, j) 只需要计算 1 次、并且可以在常数时间里完成（因为子问题已经计算好了），我们将时间复杂度降到了 O(m * n) ，从而可以在短时间内计算出结果了。
- 9 -
在这个问题里，还有一个很重要的特性是，我们在计算 f(i, j) 的时候，并不关心从 f(0, 0) 到 f(i, j) 的推导过程，或者说从 f(0, 0) 推导到 f(i, j) 的过程对后续计算 f(i, j) 没有任何影响。用不说人话的方式，这就叫做无后效性。
注意，无后效性并不是对所有问题都成立的。
比如在一个 N * N 的迷宫里寻找从坐标 (1, 1) 走到 (N, N) 的一条路径，我们在使用 BFS 或 DFS 搜索时需要将路过的坐标做好标记，避免再次走到，因此从 (1, 1) 到 (x, y) 的路径是会影响从 (x, y) 到 (N, N) 的路径，不满足无后效性。
汇总一下前面提到的这个问题的几个特点：
* 最优子结构
* 重复子问题
* 无后效性
—— 这不就是标准的 动态规划 问题嘛！对应的，第 5 节我们推导出的公式，就是这个动态规划问题的状态转移方程了！
由于满足这几个特性，我们实际上可用迭代的方式，从 f(m, n) 倒推出 f(0, 0)，这样可以使用循环而不是递归，进一步提高代码的运行效率。
另外，对于同一个动态规划问题，状态转移方程也可以不止有一种写法，比如我们可以定义 g(i, j) 为将 X[1..i] 变为 Y[1..j] 的最小操作次数，于是：
基于这一版状态转移方程，我们就可以从 f(0, 0) 开始逐步计算出 f(m, n)。
具体代码就不在这里贴了，感兴趣的同学可以自己写写看，注意边界值的处理就好。
实际上，这个算法叫做编辑距离，英文名 Levenshtein distance，是一个和普京同名、姓 Levenshtein 的战斗民族大佬在 1965 年提出的算法；该算法经典到 php 的标准库里竟然包含了一个 levenshtein 函数（可见php的作者真是太闲了）。
- a -
还没完，在追求性能和效果的路上我们还能走得更远，根据代码本身的特性，我们还有一些优化可以做。
比如说代码的注释是可以先删掉再比较。
比如说代码里的字符串也可以删掉再比较。
比如说代码里的空格，貌似也不影响我们的相似度对比。
通过这样的操作，我们可以大幅缩短了需要对比的代码长度，对于 O(m*n) 的算法而言，这个改善是很可观的。
此外，当时下场切瓜的另一位瓜友将这个思路推到了极致：既然我们认为代码的整体框架不变、改变的只是变量名这些东西，那我们直接把所有字母、数字、空格等字符全删除，只留下标点符号来代表代码的框架，不是更香吗？
这样我们既提升了计算的效率，又进一步提升了计算的效果。
值得一提的是，该瓜友用的不是编辑距离，而是另一个经典的动态规划算法“最长公共子序列（LCS）”。
- b -
啰嗦了这么多，终于可以写总结了：
* 计算两个文本的相似度，可以使用编辑距离或者最长公共子序列算法；这两个都是典型的动态规划算法；
* 动态规划问题需要满足最优子结构、重复子问题、无后效性；
* 要解决动态规划问题，先定义状态，推导状态转义方程，再编码；可以用递归也可以用迭代，前者实现简单，后者运行更快；
* 搞事情要考虑后果，本不应该把参赛账号名也直接公开，结果是那次比赛有些人面子上有点不好看；不过年轻时谁没犯点错呢，除了自己谁又还记得呢？
最后，“编辑距离” 是个 LeetCode 的原题（No. 72，传送门），；“最长公共子序列” 也是个 LeetCode 的原题（No. 1143，传送门），感兴趣的同学也别错过。
都看到这儿了，帮忙点个 “赞” 或分享给你的小伙伴吧，感谢~
---
推荐阅读：
* 程序员面试指北：面试官视角
* 又是面试题？对，合并有序序列。
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* (译) Ｃ程序员该知道的内存知识 (1)
- 1 -
又是在那遥远的 2009 年，那个“杯具”已经不是杯具的年头，度厂办个算法比赛，办出了点儿杯具的味道。
比赛的名字叫“百度之星”，那些年在校园里影响力还蛮大的（好像现在还是），大概赛制就是通过初赛、复赛、决赛这么几轮，选出几个社会主义四有青年
为什么说有点杯具的味道呢，因为那年的初赛结束以后，度厂搞了个骚操作，把所有参赛选手提交的代码导出来，打了个包，发在贴吧里。
于是贴吧突然就炸了。
- 2 -
要知道初赛是网络赛，各个学校的 ACM（或OI） 集训队的队员们很可能都是凑在机房一起参与，毕竟毛主席教导我们人多力量大嘛。
所以这就有点意思了：如果同一个题，两份代码长得很像，说明互相抄袭概率就很大。
问题是参赛人数有点多，两两对比这 O(n^2) 的时间复杂度，靠人肉有点儿吃不消；但这么大一个瓜，光看不吃又有点可惜了。
那么这瓜到底该怎么吃呢？
- 3 -
还好，作为一个竞赛战五渣的我，通过初赛的能力没有，搞事情的能力还是有一点的。
为了对比两份代码的相似度，那我首先得找到一个指标。
作为一个善于
那么，只要我能算出修改的程度，就能判断相似度了：假设两份代码长度分别是 m、n，修改了 x 个字符， 我们大致可以把 `100% - x / ((m + n) / 2)` 当成相似度（没被修改的字符占比）。
但如何计算这修改的程度呢？毕竟修改前后代码长度很可能不同，不适合通过逐字比较来找到差别。
- 4 -
既然直接处理两段代码有点棘手，那不妨先考虑一下简单的 case 。
比如说要将字符串 "a" 改成 "b"，这个简单，只要改一个字符就行。
又比如说要将字符串 "a" 改成 "ab"，这个也简单，只要添加一个字符就行。
再比如说要将字符串 "ab" 改成 "b"，这个依然简单，只要删除一个字符就行。
如果我能算出将一段字符串通过添加、删除、修改三种操作修改成另一个字符串的最少操作次数，应该就能把这瓜给吃了。
好像是找到了方向，但是要怎么实现呢？
- 5 -
既然直接处理两段代码还是有点棘手，那不妨再考虑一下稍微复杂一点的 case ，比如把字符串 X = "baidu" 变成 Y = "bytedance"。
首先，因为 X[0] 和 Y[0] 相同，我们可以把问题简化成：将 "aidu" 变成 "ytedance"，即 X[1..4] => Y[1..8]（后面简记为 X[1:] => Y[1:]）。
接着，X[1] = 'a', Y[1] = 'y'，如上一节所说，这时候我们有三种选择：
* 添加：给 X 添加 'y' ，当成 "byaidu"，于是问题简化为将 "aidu" 变成 "tedance"，即 X[1:] => Y[2:]；（注意，我们在这里把该操作当成一个思维实验就好，不需要真的修改 X ，所以这里 "aidu" 对应 X[1:] 而不是 X[2:]）
* 删除：从 X 中删掉 'a' ，当成 "bidu"，问题简化为将 "idu" 变成 ytedance"，即 X[2:] => Y[1:]；
* 修改：把 X 这个 'a' 改成 'y'，当成 '"byidu"，问题简化为将 "idu" 变成 "tedance"，即 X[2:] => Y[2:]；
这三种操作中，后续需要的修改次数最少的那个，再加上 1，就是我们把 X[1:] 改成 Y[1:] 所需的最少次数。
依此类推，如果我们将 X[i:] 变成 Y[j:] 需要 f(i, j) 次操作，由上可得到这样一个公式：
if X[i] == Y[j]:
f(i, j) = f(i + 1, j + 1)
else:
f(i, j) = 1 + min(
f(i, j + 1), #添加
f(i + 1, j), #删除
f(i + 1, j + 1) #修改
)
f(i, j) = f(i + 1, j + 1)
else:
f(i, j) = 1 + min(
f(i, j + 1), #添加
f(i + 1, j), #删除
f(i + 1, j + 1) #修改
)
也就是说，我们可以用子问题的最优解来推导出问题的最优解，如果用不说人话的方式，就叫做该问题存在最优子结构。
这么一看，代码是不是呼之欲出了？
- 6 -
啰嗦了这么多，不能忘了大佬的教导：
说干就干，把上面推导的公式落地成代码，so easy：
def change(x, y):
def f(i, j):
if x[i] == y[j]:
return f(i + 1, j + 1)
else:
return 1 + min(
f(i, j + 1),
f(i + 1, j),
f(i + 1, j + 1)
)
return f(0, 0)
print change("baidu", "bytedance")
def f(i, j):
if x[i] == y[j]:
return f(i + 1, j + 1)
else:
return 1 + min(
f(i, j + 1),
f(i + 1, j),
f(i + 1, j + 1)
)
return f(0, 0)
print change("baidu", "bytedance")
然后跑起来一看：
$ python change.py
Traceback (most recent call last):
File "change.py", line 13, in <module>
print change("baidu", "bytedance")
... #省略一大段
File "change.py", line 3, in f
if x[i] == y[j]:
IndexError: string index out of range
Traceback (most recent call last):
File "change.py", line 13, in <module>
print change("baidu", "bytedance")
... #省略一大段
File "change.py", line 3, in f
if x[i] == y[j]:
IndexError: string index out of range
- 7 -
"index out of range"，越界了 —— 显然，这里漏掉了递归的终止条件。
不过这个简单：如果 X 越界了，说明这时 i == len(X)，那么 Y 还剩几个字符，我们都加上就行，即还需要 len(Y) - j 次操作；或者 Y 越界了，说明 j == len(Y)，我们把 X 剩下的几个字符删掉，即 len(X) - i 次操作。
于是代码变成了：
def change(x, y):
def f(i, j):
if i == len(x):
return len(y) - j
if j == len(y):
return len(x) - i
if x[i] == y[j]:
return f(i + 1, j + 1)
else:
return 1 + min(
f(i, j + 1),
f(i + 1, j),
f(i + 1, j + 1)
)
return f(0, 0)
print change("baidu", "bytedance")
def f(i, j):
if i == len(x):
return len(y) - j
if j == len(y):
return len(x) - i
if x[i] == y[j]:
return f(i + 1, j + 1)
else:
return 1 + min(
f(i, j + 1),
f(i + 1, j),
f(i + 1, j + 1)
)
return f(0, 0)
print change("baidu", "bytedance")
跑起来效果杠杠的，马上就得到了 7，算得没毛病。
只可惜这代码还没法用 —— 别说跑那些参赛代码，就连长度为 16 的两个字符串都跑不出结果……
- 8 -
稍微分析一下我们就会发现，它竟然是指数时间复杂度的：
不过仔细观察上图（不仔细也没关系，我给红色高亮了），我们可以发现，为了计算 f(i, j)，我们需要计算 f(i + 1, j + 1)；而且它也被用于计算 f(i, j + 1) 和 f(i + 1, j) 。
这意味着这个问题存在重复子问题，类似于我们用 f(i) = f(i - 1) + f(i - 2) 计算
因此我们完全可以将 f(i, j) 存下来、避免重复计算，就像这样：
def change(x, y):
cache = {}
def f(i, j):
if i == len(x):
return len(y) - j
if j == len(y):
return len(x) - i
if (i, j) not in cache:
if x[i] == y[j]:
ans = f(i + 1, j + 1)
else:
ans = 1 + min(
f(i, j + 1),
f(i + 1, j),
f(i + 1, j + 1)
)
cache[(i, j)] = ans
return cache[(i, j)]
return f(0, 0)
cache = {}
def f(i, j):
if i == len(x):
return len(y) - j
if j == len(y):
return len(x) - i
if (i, j) not in cache:
if x[i] == y[j]:
ans = f(i + 1, j + 1)
else:
ans = 1 + min(
f(i, j + 1),
f(i + 1, j),
f(i + 1, j + 1)
)
cache[(i, j)] = ans
return cache[(i, j)]
return f(0, 0)
注：实际上这里也可以直接用一个二维数组 f[i][j] 来保存 f(i, j)，对 C/C++ 来说实现会更容易，读写效率也更高。
优化以后，因为每个 f(i, j) 只需要计算 1 次、并且可以在常数时间里完成（因为子问题已经计算好了），我们将时间复杂度降到了 O(m * n) ，从而可以在短时间内计算出结果了。
- 9 -
在这个问题里，还有一个很重要的特性是，我们在计算 f(i, j) 的时候，并不关心从 f(0, 0) 到 f(i, j) 的推导过程，或者说从 f(0, 0) 推导到 f(i, j) 的过程对后续计算 f(i, j) 没有任何影响。用不说人话的方式，这就叫做无后效性。
注意，无后效性并不是对所有问题都成立的。
比如在一个 N * N 的迷宫里寻找从坐标 (1, 1) 走到 (N, N) 的一条路径，我们在使用 BFS 或 DFS 搜索时需要将路过的坐标做好标记，避免再次走到，因此从 (1, 1) 到 (x, y) 的路径是会影响从 (x, y) 到 (N, N) 的路径，不满足无后效性。
汇总一下前面提到的这个问题的几个特点：
* 最优子结构
* 重复子问题
* 无后效性
—— 这不就是标准的 动态规划 问题嘛！对应的，第 5 节我们推导出的公式，就是这个动态规划问题的状态转移方程了！
由于满足这几个特性，我们实际上可用迭代的方式，从 f(m, n) 倒推出 f(0, 0)，这样可以使用循环而不是递归，进一步提高代码的运行效率。
另外，对于同一个动态规划问题，状态转移方程也可以不止有一种写法，比如我们可以定义 g(i, j) 为将 X[1..i] 变为 Y[1..j] 的最小操作次数，于是：
if X[i] == Y[j]:
g(i, j) = g(i - 1, j - 1)
else:
g(i, j) = 1 + min(
g(i, j - 1),
g(i - 1, j),
g(i + 1, j + 1)
)
g(i, j) = g(i - 1, j - 1)
else:
g(i, j) = 1 + min(
g(i, j - 1),
g(i - 1, j),
g(i + 1, j + 1)
)
基于这一版状态转移方程，我们就可以从 f(0, 0) 开始逐步计算出 f(m, n)。
具体代码就不在这里贴了，感兴趣的同学可以自己写写看，注意边界值的处理就好。
实际上，这个算法叫做编辑距离，英文名 Levenshtein distance，是一个和普京同名、姓 Levenshtein 的战斗民族大佬在 1965 年提出的算法；该算法经典到 php 的标准库里竟然包含了一个 levenshtein 函数（
- a -
还没完，在追求性能和效果的路上我们还能走得更远，根据代码本身的特性，我们还有一些优化可以做。
比如说代码的注释是可以先删掉再比较。
比如说代码里的字符串也可以删掉再比较。
比如说代码里的空格，貌似也不影响我们的相似度对比。
通过这样的操作，我们可以大幅缩短了需要对比的代码长度，对于 O(m*n) 的算法而言，这个改善是很可观的。
此外，当时下场切瓜的另一位瓜友将这个思路推到了极致：既然我们认为代码的整体框架不变、改变的只是变量名这些东西，那我们直接把所有字母、数字、空格等字符全删除，只留下标点符号来代表代码的框架，不是更香吗？
这样我们既提升了计算的效率，又进一步提升了计算的效果。
值得一提的是，该瓜友用的不是编辑距离，而是另一个经典的动态规划算法“最长公共子序列（LCS）”。
- b -
啰嗦了这么多，终于可以写总结了：
* 计算两个文本的相似度，可以使用编辑距离或者最长公共子序列算法；这两个都是典型的动态规划算法；
* 动态规划问题需要满足最优子结构、重复子问题、无后效性；
* 要解决动态规划问题，先定义状态，推导状态转义方程，再编码；可以用递归也可以用迭代，前者实现简单，后者运行更快；
* 搞事情要考虑后果，本不应该把参赛账号名也直接公开，结果是那次比赛有些人面子上有点不好看；不过年轻时谁没犯点错呢，除了自己谁又还记得呢？
最后，“编辑距离” 是个 LeetCode 的原题（No. 72，传送门），；“最长公共子序列” 也是个 LeetCode 的原题（No. 1143，传送门），感兴趣的同学也别错过。
都看到这儿了，帮忙点个 “赞” 或分享给你的小伙伴吧，感谢~
---
推荐阅读：
* 程序员面试指北：面试官视角
* 又是面试题？对，合并有序序列。
* 踩坑记：go服务内存暴涨
* TCP：学得越多越不懂
* UTF-8：一些好像没什么用的冷知识
* (译) Ｃ程序员该知道的内存知识 (1)
Aug
1
- 鹅厂 -
在遥远的2009年，那时候“呵呵”还没有奇怪的意思，我笑呵呵地去参加了鹅厂的实习招聘。
面试被安排在面试官下榻酒店的房间里，校门口的**王朝大酒店，可能一晚上能顶我一个月生活费那种。
过程聊得应该还可以，不过大部分细节都忘了，只记得最后那道代码题，一张纸，一支笔。
题面很简单：写一个 C 函数，合并两个有序数组。
- “最好能通用一点”，面试官补充说。
- “可以用 C++ 模板吗？”
- “最好还是用 C 。”
好多年以后，当我开始面试别人了，发现这道题确实很好用。
- 解 -
学过归并排序的同学应该都会觉得这个题目并不难，只不过是其中的一次归并环节。
其基本思路是，用两个指针，分别从数组的第一个元素开始，依次比较，每次找到最小的元素存入新数组，然后将指针移动到下一位。
需要注意的是当一个数组被取完以后，还得处理另一个数组的剩余元素。
而所谓“通用”，是指数组的元素可以是任意类型，因此需要把数组元素的大小、用于比较的函数也作为参数传进去。
大概就是要实现这样的一个函数：
其中 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：一些好像没什么用的冷知识
* (译) Ｃ程序员该知道的内存知识 (1)
在遥远的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);
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：一些好像没什么用的冷知识
* (译) Ｃ程序员该知道的内存知识 (1)
