谈谈coding面试的种类与基本应对策略， 欢迎其他有面试经验的人一起讨论

magicsets 发表于 2018-7-28 12:48
我觉得复杂度意义上的“最优解”其实只是真正面试时面试官所期望的“最优解答”的一个组成部分。也就是说 ...

说的很有道理！感谢层主！

好贴。非常有用。

wzyath 发表于 2018-7-28 07:55
同问碰到skyline这种题该怎么办。如果直接说出最优解，一看就知道是背过的。。。

较难的hard题，最好在彻底理解答案的基础上背题。面试官比较看重的是得到这个解法的过程。
我们来以skyline的表演为例，抛砖引玉一下～

题目要求的是建筑的剪影，可以抽象为每个固定横坐标上的最高点（划重点：提取问题核心）。因此这个解法可以分成两部分：
（1）如何把input转换为线性，从而抽象成扫描线问题（甩名词：sweep line）
（2）扫描线的具体实现

第一部分，如果想要简单扫一遍，数据必须是按x轴排序的。假设我们 start_x 来对 building 排序，则end_x仍然是无序的，这样不好。（此时演技爆棚一拍脑袋想到）我们只需要知道skyline的线段是在哪里开始的，因此在building高度发生变化的X位置进行处理即可。building的开始和结束都算是高度变化，因此可以把 start 和 end 拆开处理，只需要标记 X 位置上的高度数据以及这个高度是开始还是结束。

至于每个X位置数据的具体结构，可以用一个tuple（int h 高度，bool start 表示是开始还是结束），也可以像高票解法一样用正数代表开始、负数代表结束。可以和面试官阐明。

第二部分，主要是如何维持一个高度的queue。
阐明在扫描过程中需要三个操作，插入（遇到start），删除（遇到end），获取最大值（高度更新），因此可能有：
1. 因为要取最大值嘛，所以很明显我们试试heap，插入O(logn)，max O(1)，但是删除是O(n)，不太好，我们试试别的；
2. balanced bst (c++ ordered map以及java treemap），全场O(logn)，通通O(logn)；
3. 有没有可能优化方法1呢？可以用 hashmap + heap的方式来实现，O(logn) insert, O(logn) remove, O(1) get_max。

第一部分稍微举例说明了一下如何展示思路。
第二部分我认为是装逼重点。能写方法3，就先列出1和2，指出他们的不足，然后提出3。如果懒得实现3，先提出1，再提出2，指出红黑树的时间优于heap，在面试官看来也是对数据结构足够熟练的应用了。

最后记得提出edge case，比如两个building高度相同怎么办（假装思考一下）如果先push start，再pop end，就不会有高度变化的问题了嘛，所以我们重写compare函数的时候注意一下就行了。

以上整个过程，在表演不崩的情况下用5-8分钟来解释，我认为都是可以的。


两年没刷题了，具体细节可能记得不太清楚。最近刚开始当面试官，在演技方面给大家举个栗子🌰。对于这种candidate，即使对方可能是在表演，如果能够把问题肢解得这么清楚、把多种实现细节的trade-off分析得这么明白，我也会给一个pass的。
（皮完就跑 #滑稽#

补充内容 (2018-7-29 05:14):
解释思路的时间扩展到10+分钟应该也可以吧，诸位要不要试试mock一下计个时？我们统计一下（笑）
总之只要思路连贯，有理有据令人信服，就不会演崩。但一定要有develop思路的过程，这也能体现对解法的充分理解

楼主能帮忙看下简历不， new grad 那种

非常有用的帖子，感谢分享！

真淘蛮 发表于 2018-7-29 13:02
楼主能帮忙看下简历不， new grad 那种

这个你最好找hr去看， 她们是真正筛查简历的， 我也不知道她们关注的是什么。 不误导你了。 不过你如果找不到hr, 去linked in多读读牛人的profile也会有很多帮助

楼主太给力了，必须加米。感觉可以出书了，至少可以是一个小型的类似于cc189的handbook

真诚感谢楼主的分享！

mark下回来复习

謝樓主分享，分人深省