[讨论]当面试官出了一道2SUM，他到底在考察什么

美国西海岸有一个著名的传说 ："有人2SUM进了狗家..."


LZ好像还没遇到运气这么好的人。:)

今天在LC看到了一个哥们，讲他昂赛遇到了2SUM，两分钟做完，但是挂了。哥们表示迷茫，不知道面试官想要什么。
https://leetcode.com/discuss/int ... te-or-2020-Rejected

LZ在地里也看到过另外一家面2SUM，不过那个更像是一个代码风格的测试，考察写test case

所以LZ很想讨论一下，如果遇到了出2SUM的面试官，到底他想问什么？
LZ如果会面试官，能想到的方向有：
1.
2SUM ->3 SUM ->N SUM

2.
2SUM -> 分布式2SUM

大家经验或者想法的，希望可以讨论一下。

这种“简单题”最忌一上来就认为它是某道 LeetCode 上做的原题，直接开始写代码。就 2 sum 来说，有很多东西需要和面试官确认，比如
- 输出是什么？是符合条件的组合数量，还是符合条件的组合本身，还是符合条件的 index 组合，还是 true/false 等等，这些看似都是小问题，但是实际上会影响你解法选择和函数接口
- 输入有没有已经 sorted
- 输入有没有 duplicate？比如有 duplicate 且要求你返回 index、输入没有 sorted 的话，那你就不能提前 sort，如果不是这样，你需要讨论 sort 造成怎样的时间、空间复杂度影响
- 输入是多大规模，是不是一个数组能装得下？
- 如果有多种解法，需要提前了解面试官对于时间、空间的要求，选择合适的解法
- 这个函数后续有没有什么别的用，如果有的话，怎么选择优化的方向？

合格的面试官不光是看你能不能想出算法，更要关注你的解决问题的步骤，他们会看你是否确认上面这些问题，然后在自己的 checklist 上打勾，如果你不确认好，而最后被他的 test case 问住了再回过头来改函数的接口或算法，显示了你将来实际工作可能会出类似的流程问题，这就是为什么有的人"觉得"自己秒杀了 2 sum 结果没过的原因

亲自在微软AA面碰到过全程就做了一道2sum，具体可以参考我的微软VO过经帖。
follow up考察了很多内容，corner case，大数据，多线程，分布式，内存不足，file sort等等

2SUM的标准答案memory的usage是很高的，有O(n)。所以抛开别的不说，并行，大数据啥的。首先问题是有多少memory，算法复杂度的要求是什么。
第二个可能的考点是hash，这个就可以水很深了，复杂度，如何解决hash collision。

关键一点是，首先要和面试官聊开了，问清楚他想问什么，不要上来就一通写。作为一个面试官，非常不希望看到你不顾他的意思，按自己的方法来解。

ajing 发表于 2020-11-6 07:15
2SUM的标准答案memory的usage是很高的，有O(n)。所以抛开别的不说，并行，大数据啥的。首先问题是有多少mem ...

我也觉得是
这题目太刁钻，最简单也最困难 :)
我查了一下LC，其实 Two Sum III就挺有意思的，可以有很多follow up
https://leetcode.com/problems/two-sum-iii-data-structure-design/

我觉得问这种问题得面试官一般很弱。 就像在炫耀 茴字有几种写法一样。无法明显体现出 面试者得智商。

考的是你的诚实，正确答案是“这条题我以前刷/做过了，要不要换一道题”。

有一种考察方向是并行，往系统设计的角度考察。
还有一种可能性是你之前的的问题答的不好/踩了红线，这轮你已经挂了，随便出个题大家开心开心。

可能考标准答案是: 这题我原题做过建议面试官换题.

并没有什么卵用