推荐一个面试算法题

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

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

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

[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 我记得谭浩强刚学循环的练习题里面就有这个。。

[MoYi123]

@cooltechbs 排序后二分查找.

[wnpllrzodiac]

最大矩形面积，求直方图包围的最大面积的二维版。

上次去面试，hr 直接给我出了这道题，我说这道是 hard ，以前看过，没做出来。她说你试试吧。
我觉得 hr 都懒得让我去技术面，直接拿到难的题目把我打发了。借口说如果如果下次有意向，会再约去技术面试。
我心想，过来现场面试，第一面还是 hr 面试，前面已经给做了套题了。又来道 leetcode 题目。
真是 活久见。

虽然我也尝试做了半个小时。
这种题目，感觉除了背出来，应试。不可能随便找个人，随便想一下，就能做出来。

[jamesjammy061]

🤣 前端: (new Set(a)).difference(new Set(b))

[cooltechbs]

@MoYi123 如果输入是个数组，应该不能改变数组元素的相对顺序吧，原有顺序可能对用户很重要（我不懂 Erlang ，不知道 Erlang 库作者是怎么考虑的）。。。
如果输入是个集合那就没问题了

[yh7gdiaYW]

@cooltechbs 外包能用任意方法做出 OP 这道题目的，我都可以算他算法这关过了。按去年的经验，这道题至少能拦住 70%的外包

[lixiaolin123]

@sagaxu T(n) = 2T(n/2)+n => 式子中的 2 最后推导为 2 的 k 次方，加号后面的 n 推导为 k*n ，当 k=log 以 2 为底 n 的对数时，T(n)=nT(1)+n*log 以 2 为底 n 的对数，于是 T(n)= O(n*log n)

[rihkddd]

@pursuit 百度排不到前三了，还有腾讯啊

[kkkbbb]

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