闲鱼面试复盘

上周五有一场闲鱼的面试，预定的晚上七点开始，我在六点五十就连上了视频会议，然后面试官隔了一两分钟也连上来了，这打了我一个措手不及，因为我觉得他应该会掐点上线，他没让我自我介绍，给了我一道算法题——用O(n)的时间复杂度查找一个无序数组中第k大的元素。

我当时的第一想法是用小顶堆来做，但这个时间复杂度应该是O(nlogn)，第二想法是直接调用Arrays.sort()，但是这个时间复杂度同样也是O(nlogn)，都不满足要求。我向面试官说了我的想法，请他给我一点提示，最后还是没有想出来，第一道题就pass掉了。面试结束之后我上网去查，发现可以用快排的思路来做这道题，但是我快排没有仔细学过（捂脸）……然后就是补学快排，最后成功做出了这道题。

来到第二题——210. 课程表II，给出课程之间的依赖关系，要求输出一个课程的修读顺序。当时我第一感觉这有点像我之前做过的一道二分图的题，我感到一阵惊喜，于是我喜滋滋地跟面试官说这道题可以用二分图来做。我当时隐约感觉二分图算法有点不对劲，但是由于先入为主的思想，最后我还是在二分图的框架上做了这道题，导致方向从一开始就错了，最后40多分钟没做出来，面试官说由于时间问题，今天就面试到这了……尴尬。事后一想，二分图解决的是能否把一些节点分为两个部分，其中一个部分依赖另一个部分，这道题其实应该用环检测和拓扑排序来做。但是，由于我当时学这两个算法的时候没有学的很熟，只是草草看了一遍教学视频，没有自己写代码，导致最终没有想到这个上面。

总结：

• 学习的时候不能马虎，哪种问题用哪种解决方案要理解清楚，这样在面试的时候才不会搞混。出现误判本质上还是熟练度不够。
• 在学算法的时候，每个辅助变量的作用要理解清楚，还有它们的更新过程，这样掌握得更牢固，具体运用得时候也不容易忘记。
• 前面两个是技术问题，第三个就纯是面试经验问题了。在做不出来题的时候，不应该闷着头继续做，不应该把面试官晾在一边，需要跟他保持交流，让他提供一点思路，也让他了解我的思路。而且还要主动关注时间，如果实在做不出来，应该跟他说明当前的思路是什么，可能哪哪有点问题，请他让我下来再思考一下，然后申请进入下一个环节。如果就卡在算法题环节，那指定是没戏了。
• 面试出现问题不要怕，积极寻求解决之道，就算最后解决不了，但是也向面试官展示了解决问题的能力。说不定就祸兮福所倚了。