推荐一个面试算法题

[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 的过程，修复的速度。

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

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

[kkkbbb]

@chanlk
其它情况里，对于排序的，“那么先进行排序然后取第一个元素查看是否一致，不一致则直接返回空集合”，这个还得继续判断吧

[chanlk]

@kkkbbb #41 是的，你是对的。这里思考得不到位，不能直接返回的，还是要遍历完所有元素。