（加米）面试时最优解和通常解如何取舍？

虽然刷题的时候最优解和普通解都会写一遍 但是在面试的时候是写最优解好还是普通解好呢

看到有的人因为面试官不了解最优解 而影响了面试。所以是不是面试的时候应该直接Bruce Force呢

真心求解 给各位加大米~

直接brute force感觉也不太好。可以提一下brute force，然后提出一个容易想到，比较general的次优解，不停和面试官互动，什么时候面试官满意什么时候开始码就行了。举几个例子，最长递增子序列，LIS那道题。如果你会二分，但是讲不明白的话，还不如用DP来做。因为二分会乱，而且可能你只是记忆了这个解法，但是讲不清楚。直接暴力肯定是不行的。而且DP也考验你的基本功。
再比如，subset那道题目，最优解肯定是位掩码，但是也不太容易理解，而且容易翻车。还不如老老实实用dfs/backtracking，这个正好也是考验基本功。
再比如，path Sum III那道题，最优解是hashMap，但是你也不一定讲得清楚。可能直接了当的recursion更好一些。不过这个你要是讲得很清楚肯定是加分项。
举这几个例子的意思就是说，很多时候，面试官想要考察的是基本功，所以，一些通用的套路和写法一定要会写。当然，一些好的算法和最优解肯定是加分项，前提是你理解清楚。
然后就是说，一些偏门的奇技淫巧可能没有那么大意义，稍微一点follow up很可能就答不上来。
所以，面试的时候，不停沟通，要展示出自己会写通用的解法，了解基本的套路。然后，码完之后你可以跟面试官提，你有更好的解法，但是一定要解释得清楚。

在写代码之前， 你会把所有你知道的解全部说出来， solution 1: ....  Solution 2: .... Solution 3: ....   然后说 Time / space complexity for each solution.  然后你就会发现有的solution 是有trade off 的 有的时间快了 但是用了额外的空间等等， 你需要和面试官讨论 他想让你 implement 哪一种方法， 这样不但展示了你知道很多种不同的解 然后 还显示出你会分析 trade off  （是一个很好的工程师）。 最后 他想让你写哪一种你就写哪一种（不过通常是比较优化的解）， 他也会比较满意。   

我的观点是，可以先写通常解如果面试官问你改进再说最优解，如果没有追问就表示对你回答满意就没必要再多回答了吧

luyh2016 发表于 2020-4-9 12:40
我的观点是，可以先写通常解如果面试官问你改进再说最优解，如果没有追问就表示对你回答满意就没必要再多回 ...

谢谢辣 给你加米啦

我的意思是说，很多最优解在编码难度，细节掌握上并不容易。你如果掌握得非常好，怎么问也解释得清楚，当然是一个加分项。
你可以看一下我举的这几个例子，最优解在一定意义上没有那么容易。而且面试官看重的一是你的基本功，二是你的思维能力和敏捷性。
如果只是记住了某些特定的奇技淫巧，那不会是面试官想要的。

尽量写基本解。因为最优解只是一个取舍

先寫一個基本姐 面試官有反應再說可以用最佳解改進

先想好思路，如果几分钟内没有最优解，一般面试官就会提示了，根据提示再构思，如果提示都解不了的话，只能选择自己能想出的最好方法了，但是基本这轮就算挂掉了。有些公司可以接受一轮没面好但是其他的都面的还不错的情况。

luyh2016 发表于 2020-4-9 12:40
我的观点是，可以先写通常解如果面试官问你改进再说最优解，如果没有追问就表示对你回答满意就没必要再多回 ...

面试官通常既然能出这一道题，他肯定早把这道题吃透了，没有追问，也可能是面试官心情不好，不想给hint。