这是一个创建于 32 天前的主题，其中的信息可能已经有所发展或是发生改变。
经常看到面试写红黑树、LRU 、接雨水之类的讨论，很多人认为这种题目不合理，那么有什么真的适合面试的代码题吗？我推荐一个：两个列表求交集。
说一下为什么推荐这个题目：
- 描述简单，对于没有完善的面试系统情况，你十秒钟内基本上就能让面试者明白题目意思。
- 实现简单，大部分人至少会写 n^2 的双循环，跟语言特性相关性低。
- 可以追问优化，有很多的优化方式，比如 set/hash ，对应不同的计算复杂度，常见的数据结构实现。
- 最重要的是，工作真的能用到。
- 容易写测试用例，考察面试者写单测。
可能会有人觉得这题太简单，说一下我的面试经验：
- 大部分人能快速的理解题目，然后就开始用自己熟悉的语言写，这一部分可以改进的是要进一步沟通确认题目，到底是什么类型的两个列表，元素是什么样的，重复元素输出，列表长度规模等，计算/内存要求等，能不能用标准库函数。
- 用自己熟悉的语言，写一个 n^2 的双循环。这种可能不是科班的，如果能 bug free 的写出来，就问一下优化思路。
- 能用自己熟悉的语言的标准库函数/内置数据结构（ hash/set ）实现，bug free ，就准问这些结构的细节实现了解情况。
- 当然也有厉害的上来自己从头写一个不错的 hash 实现，这种就不用问原理了。
- 能 bug free 或者有少许错误的完成，就让他写单测，看测试覆盖是否完善，能否发现代码里面的问题，debug 的过程，修复的速度。
能走到第五步的人，基本上至少是正经学过计算机，认真听了计算机里面比较重要的基础课，日常工作编码习惯不错，能写出可用生产代码的中、高级程序员了。
不管你信不信，我曾在不同的公司工作的时候，都遇到过实际生产代码中，两个列表求交集是用双循环实现的，都是大厂，其中一个还是国内前三的广告平台精排代码，因为那次变更引起了严重的性能问题导致回滚。
 |
1
aloxaf 32 天前
我印象最深的是编程随想的关于打印前 N 个质数的题目，很有启发性：任何人都能做出来，但是又有足够的优化空间来考察水平。
|
 |
2
iintothewind 32 天前
其实 intersect operation 有直接的 util 的，工作也不用自己写😂
|
 |
3
nomagick 32 天前  1
你知道实战中比这个效率更高更狠的是什么吗，过滤英语四六级，能干活的四级，好点的六级
|
 |
4
sagaxu 32 天前
证明快排的时间复杂度，宝典肯定没这题
|
 |
5
rihkddd OP 1
@aloxaf 这个说实话有点偏了，很多人连基础的筛法都不知道，绝大部分人实际工作上用不到。可以给出一个基础的筛法，然后让面试者优化，这种适合对效率有较高要求的团队。
|
|
6
rihkddd OP @iintothewind 是这样，上面提到过面试的时候用标准库的可以追问实现细节，能说清楚就行。实际工作能用的话当然用已有实现最好，最怕就是这种常见需求有些人基础不行还自己写。
|
 |
7
chanlk 32 天前 1
尝试解答一下
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 ，节省内存。 |
 |
8
pkoukk 32 天前
斐波那契数列
翻转链表 打印二叉树 |
 |
9
newtype0092 32 天前
我也用过这个问题，理由也和你差不多，面试题难易不重要，区分度尽可能大才是好问题。
|
 |
10
mooyo 32 天前
我来推荐一个，排序奇升偶降列表，给几个 corner case 。这个题好处在
1. 同时考察链表拆分，链表反转，合并有序链表。 2. 需要仔细地处理边界情况。 |
 |
11
yesterdaysun 32 天前
同意, 我经常用这个题目, 实际情况是 10 个有 9 个只能到双重循环, 剩下一个能进一步到使用集合之类的数据结构.
大多数人对算法复杂度都没有概念, 经常提出一些奇奇怪怪的优化方案, 比如使用 Steam 流, 用 ForEach, 两个列表先排序等等, 当然这里是小公司, 对于大厂人员, 素质想来会高一点吧 |
 |
12
InkStone 32 天前
这个问题还挺有扩展性的。往下可以延伸到数据库 JOIN ，往上可以提升到 PSI
|
 |
13
yh7gdiaYW 32 天前
好问题，正好又要招外包了可以用上
|
 |
14
binxin 32 天前
但是，这道题目难道不是在考：你知道 hash 么？。
1. 知道 hash 的人，大概率可以短时间直接写出 o （ m+n ）的方案，并且可能调用现成的库，很简单。 1.1 如果此时进一步考核他手挫 hash ，或者细节，个人觉得会引人反感，得到面试者的「面试造飞机，上班开飞机」，已经是最好评价了吧。毕竟上班更多是工程，而不是科研。 2. 不知道 hash 的人，就算写出了 o （ m*n ），然后呢？几十分钟他能创造性的学会/掌握/手搓一个 hash ？有这水平应该知道 hash 。 所以是我哪里没理解 op 的意思么？ |
|
15
yh7gdiaYW 32 天前 1
我最近也准备了一道比较接地气也不太难的新题，分享下：
使用 ai 开发了一个文本补全功能，但 ai 返回的结果有时不是输入文本的直接续写，希望开发一个工具函数移除输入末尾与输出开头的重叠部分。示例： 输入： "2.打开物品栏\n3." AI 输出： "3.打开物品栏" 期望结果： "打开物品栏" |
|
16
chanlk 32 天前
@binxin 这个问题太简洁，其实有很多隐含的内容没展开，敏锐的面试者应该主动追问细节。
比如： 是否需要保留重复元素？（例如 [1,2,2,3] 和 [2,2,4] 的交集是 [2] 还是 [2,2]？） 元素是否有序，顺序是否需要保持？ 输入规模的大小？（决定是否需要优化时间复杂度） 这样方向就不仅仅是 hash 了，能够发现这些问题的面试者在实际工作中也能更好的避坑。 当然这是我想的，不知道 op 是不是和我想的雷同。 |
 |
18
me1onsoda 32 天前
pa+pb-pa∪b=pab
|
 |
20
edcopclub 32 天前 via Android
递归类型的题应该不错，比较考验编码能力。
|
 |
21
stiangao 32 天前
线程跟进程你知道多少？有多少说多少。
浏览器里输入一个 url ，到页面全部出来中间经历了哪些？ |
|
22
rihkddd OP @binxin 你没理解错，因为 hash 很重要，在实际工作真的会用到（原文中有举例），也不是十分复杂。真的不知道 hash 的，大概率是培训出来的，如果能很好的沟通，写出 m*n 的代码，测试完整的，也可以考虑，只是这种情况概率很小。
|
 |
24
kandaakihito 32 天前 via Android
@rihkddd 不要尬黑，现在培训班视频都会提哈希的(
|
 |
25
MoYi123 32 天前
想起来一个类似的问题, erlang 里有这样一个删数组元素的方法 [1,3,2,2,3] -- [2,3] ==> [1,2,3]
erlang 的编译器团队在前 20 个大版本上面的算法都是 n^2 的, 近几年才改成 nlogn, 我也是服了. |
 |
26
KimiArthur 32 天前 via Android
对我来说，考察写不写的出来成型算法是没什么意思的，工作你查就是了。给问题建模找到合适的办法才是更重要的能力
|
 |
27
cooltechbs 32 天前
@yh7gdiaYW 23333 ，你招外包的时候感觉候选人整体质量如何？我在小厂招正岗都觉得没几个明白人……
|
|
28
cooltechbs 32 天前 2
LZ 这个思路，在北美叫做 low-level design ，属于介于算法和系统设计之间的一个单独考察点，目前还只有少部分公司考到
但是我相当赞成这种考法！换句话说，开放性强+能客观评判的题，我觉得多半是好题。 |
 |
29
iOCZS 31 天前
两层循环可以解决。每个列表排序一下，然后双指针再比较一下也可以。不在乎空间成本，那就哈希表做。
|
 |
30
pursuit 31 天前 via iPhone
国内前三的广告平台是凤巢、阿里妈妈 and ？
|
|
31
cooltechbs 31 天前
@MoYi123 这个方法怎么做才是 O(nlogn)？我想了下，不用额外空间只能 O(n^2)，如果用了额外空间就可以 O(n) 了啊。
|
|
33
MoYi123 31 天前
@cooltechbs 排序后二分查找.
|
 |
34
wnpllrzodiac 31 天前
最大矩形面积，求直方图包围的最大面积的二维版。
上次去面试，hr 直接给我出了这道题，我说这道是 hard ，以前看过，没做出来。她说你试试吧。 我觉得 hr 都懒得让我去技术面，直接拿到难的题目把我打发了。借口说如果如果下次有意向，会再约去技术面试。 我心想，过来现场面试，第一面还是 hr 面试，前面已经给做了套题了。又来道 leetcode 题目。 真是 活久见。 虽然我也尝试做了半个小时。 这种题目，感觉除了背出来，应试。不可能随便找个人，随便想一下，就能做出来。 |
 |
35
jamesjammy061 31 天前
🤣 前端: (new Set(a)).difference(new Set(b))
|
|
36
cooltechbs 31 天前
@MoYi123 如果输入是个数组，应该不能改变数组元素的相对顺序吧，原有顺序可能对用户很重要（我不懂 Erlang ，不知道 Erlang 库作者是怎么考虑的）。。。
如果输入是个集合那就没问题了 |
|
37
yh7gdiaYW 29 天前
@cooltechbs 外包能用任意方法做出 OP 这道题目的，我都可以算他算法这关过了。按去年的经验，这道题至少能拦住 70%的外包
|
 |
38
lixiaolin123 29 天前
@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)
|
Select Language