推荐一个面试算法题

[rihkddd]

经常看到面试写红黑树、LRU 、接雨水之类的讨论，很多人认为这种题目不合理，那么有什么真的适合面试的代码题吗？我推荐一个：两个列表求交集。

说一下为什么推荐这个题目：

1. 描述简单，对于没有完善的面试系统情况，你十秒钟内基本上就能让面试者明白题目意思。
2. 实现简单，大部分人至少会写 n^2 的双循环，跟语言特性相关性低。
3. 可以追问优化，有很多的优化方式，比如 set/hash ，对应不同的计算复杂度，常见的数据结构实现。
4. 最重要的是，工作真的能用到。
5. 容易写测试用例，考察面试者写单测。

可能会有人觉得这题太简单，说一下我的面试经验：

1. 大部分人能快速的理解题目，然后就开始用自己熟悉的语言写，这一部分可以改进的是要进一步沟通确认题目，到底是什么类型的两个列表，元素是什么样的，重复元素输出，列表长度规模等，计算/内存要求等，能不能用标准库函数。
2. 用自己熟悉的语言，写一个 n^2 的双循环。这种可能不是科班的，如果能 bug free 的写出来，就问一下优化思路。
3. 能用自己熟悉的语言的标准库函数/内置数据结构（ hash/set ）实现，bug free ，就准问这些结构的细节实现了解情况。
4. 当然也有厉害的上来自己从头写一个不错的 hash 实现，这种就不用问原理了。
5. 能 bug free 或者有少许错误的完成，就让他写单测，看测试覆盖是否完善，能否发现代码里面的问题，debug 的过程，修复的速度。

能走到第五步的人，基本上至少是正经学过计算机，认真听了计算机里面比较重要的基础课，日常工作编码习惯不错，能写出可用生产代码的中、高级程序员了。

不管你信不信，我曾在不同的公司工作的时候，都遇到过实际生产代码中，两个列表求交集是用双循环实现的，都是大厂，其中一个还是国内前三的广告平台精排代码，因为那次变更引起了严重的性能问题导致回滚。

[aloxaf]

我印象最深的是编程随想的关于打印前 N 个质数的题目，很有启发性：任何人都能做出来，但是又有足够的优化空间来考察水平。

[iintothewind]

其实 intersect operation 有直接的 util 的，工作也不用自己写😂

[nomagick]

你知道实战中比这个效率更高更狠的是什么吗，过滤英语四六级，能干活的四级，好点的六级

[sagaxu]

证明快排的时间复杂度，宝典肯定没这题

[rihkddd]

@aloxaf 这个说实话有点偏了，很多人连基础的筛法都不知道，绝大部分人实际工作上用不到。可以给出一个基础的筛法，然后让面试者优化，这种适合对效率有较高要求的团队。

[rihkddd]

@iintothewind 是这样，上面提到过面试的时候用标准库的可以追问实现细节，能说清楚就行。实际工作能用的话当然用已有实现最好，最怕就是这种常见需求有些人基础不行还自己写。

[chanlk]

尝试解答一下

1. 我会先问列表是否会出现重复元素

1.1 假设是不会重复
那么创建 HashMap ，分别遍历两个列表，入 map 时进行计数，最后遍历 map ，取值等于 2 的。
- 扩展，如果取多个列表的交集，则在最后遍历 map 时取值等于列表数量。
1.2 假设会重复
上述 1.1 的做法会出现错误，如[1,1,2] 和 [2,3]的结果中 1 的计数也会等于 2 ，需要改进。
- 选择其中一个列表进行去重，创建 hashset 将列表 1 装入，然后遍历列表 2 ，如果元素 hashset 中存在，
则可以装入结果集的 list 中。
1.3 重复且要取最大交集
对于列表[1,2,2,3]与[2,2,3]，如果需要将重复元素的体现出来，即结果需要是[2,2,3]，1.2 的做法则不满足该需求。
方法 1: 分别对列表 1 和列表 2 进行 hashmap 的计数，然后遍历 map1 ，如果 map2 中存在，则对 map1 和 map2 取最小值，放入结果中(放入结果时要正确写对元素及其个数)。
- 方法 1 应该可以优化省略掉一个 map ，比如在遍历列表 2 时进行一些操作，暂时没想到。

其他：
1. 元素是否有序或可否排序，如果可以排序可能有一些优化方法，如经过长时间运行发现列表大概率无交集，那么先进行排序然后取第一个元素查看是否一致，不一致则直接返回空集合；还可以结合双指针遍历优化性能。
2. 比较列表大小，一个列表远大于另一个时，优先遍历较小的列表构建 HashMap ，节省内存。

[pkoukk]

斐波那契数列
翻转链表
打印二叉树

[newtype0092]

我也用过这个问题，理由也和你差不多，面试题难易不重要，区分度尽可能大才是好问题。

[mooyo]

我来推荐一个，排序奇升偶降列表，给几个 corner case 。这个题好处在
1. 同时考察链表拆分，链表反转，合并有序链表。
2. 需要仔细地处理边界情况。

[yesterdaysun]

同意, 我经常用这个题目, 实际情况是 10 个有 9 个只能到双重循环, 剩下一个能进一步到使用集合之类的数据结构.

大多数人对算法复杂度都没有概念, 经常提出一些奇奇怪怪的优化方案, 比如使用 Steam 流, 用 ForEach, 两个列表先排序等等, 当然这里是小公司, 对于大厂人员, 素质想来会高一点吧

[InkStone]

这个问题还挺有扩展性的。往下可以延伸到数据库 JOIN ，往上可以提升到 PSI

[yh7gdiaYW]

好问题，正好又要招外包了可以用上

[binxin]

但是，这道题目难道不是在考：你知道 hash 么？。
1. 知道 hash 的人，大概率可以短时间直接写出 o （ m+n ）的方案，并且可能调用现成的库，很简单。
1.1 如果此时进一步考核他手挫 hash ，或者细节，个人觉得会引人反感，得到面试者的「面试造飞机，上班开飞机」，已经是最好评价了吧。毕竟上班更多是工程，而不是科研。
2. 不知道 hash 的人，就算写出了 o （ m*n ），然后呢？几十分钟他能创造性的学会/掌握/手搓一个 hash ？有这水平应该知道 hash 。

所以是我哪里没理解 op 的意思么？

[yh7gdiaYW]

我最近也准备了一道比较接地气也不太难的新题，分享下：
使用 ai 开发了一个文本补全功能，但 ai 返回的结果有时不是输入文本的直接续写，希望开发一个工具函数移除输入末尾与输出开头的重叠部分。示例：
输入： "2.打开物品栏\n3."
AI 输出： "3.打开物品栏"
期望结果： "打开物品栏"

[chanlk]

@binxin 这个问题太简洁，其实有很多隐含的内容没展开，敏锐的面试者应该主动追问细节。
比如：
是否需要保留重复元素？（例如 [1,2,2,3] 和 [2,2,4] 的交集是 [2] 还是 [2,2]？）
元素是否有序，顺序是否需要保持？
输入规模的大小？（决定是否需要优化时间复杂度）

这样方向就不仅仅是 hash 了，能够发现这些问题的面试者在实际工作中也能更好的避坑。
当然这是我想的，不知道 op 是不是和我想的雷同。

[yh7gdiaYW]

@yh7gdiaYW 输出例子写错了...改成
输入： "2.打开物品栏\n3."
AI 输出： "3.使用道具"
期望结果： "使用道具"

[me1onsoda]

pa+pb-pa∪b=pab

[stiangao]

@mooyo 想当然了，真实的工作中你用过链表么？说个场景来瞅瞅

[edcopclub]

递归类型的题应该不错，比较考验编码能力。

[stiangao]

线程跟进程你知道多少？有多少说多少。
浏览器里输入一个 url ，到页面全部出来中间经历了哪些？

[rihkddd]

@binxin 你没理解错，因为 hash 很重要，在实际工作真的会用到（原文中有举例），也不是十分复杂。真的不知道 hash 的，大概率是培训出来的，如果能很好的沟通，写出 m*n 的代码，测试完整的，也可以考虑，只是这种情况概率很小。

[rihkddd]

@chanlk 是的，原主题整体说的偏技术，其实一开始能清晰的交流需求这个也很重要，对面试结果很加分。

[kandaakihito]

@rihkddd 不要尬黑，现在培训班视频都会提哈希的(

[MoYi123]

想起来一个类似的问题, erlang 里有这样一个删数组元素的方法 [1,3,2,2,3] -- [2,3] ==> [1,2,3]

erlang 的编译器团队在前 20 个大版本上面的算法都是 n^2 的, 近几年才改成 nlogn, 我也是服了.

[KimiArthur]

对我来说，考察写不写的出来成型算法是没什么意思的，工作你查就是了。给问题建模找到合适的办法才是更重要的能力

[cooltechbs]

@yh7gdiaYW 23333 ，你招外包的时候感觉候选人整体质量如何？我在小厂招正岗都觉得没几个明白人……

[cooltechbs]

LZ 这个思路，在北美叫做 low-level design ，属于介于算法和系统设计之间的一个单独考察点，目前还只有少部分公司考到
但是我相当赞成这种考法！换句话说，开放性强+能客观评判的题，我觉得多半是好题。

[iOCZS]

两层循环可以解决。每个列表排序一下，然后双指针再比较一下也可以。不在乎空间成本，那就哈希表做。

[pursuit]

国内前三的广告平台是凤巢、阿里妈妈 and ？

[cooltechbs]

@MoYi123 这个方法怎么做才是 O(nlogn)？我想了下，不用额外空间只能 O(n^2)，如果用了额外空间就可以 O(n) 了啊。

[Donaldo]

@rihkddd #5 我记得谭浩强刚学循环的练习题里面就有这个。。