Wildcard Matching这题，如果面试只答出DP而非贪心

请问大家一个问题，
以力抠 四十四题的Wildcard Matching为例子。
如果我答出了dp 复杂度是O(MN) space O(MN)
但是我无法再继续用greedy优化到O(n), space O(1).

答出dp是不是不够被hire
想拿strong hire的话。

因为很多人说，如果要strong hire 那就必须答出所有的follow up并且至少有个思路才行。
希望面试官大佬们 能够解答 感激不尽 回复加米加米

那这家公司也没必要去了

妈呀，我才知道这题有O(n)解法

majia1024 发表于 2021-01-16 19:35:59
作为一个大厂面试官，我和小伙伴们的共识是，除非easy题，一上来就DP的都默认见过原题，这时候有几种情况1. 这题表现可以不作为参考了。赶紧过了换题
2. 我把题目改改看你还dp 不dp

现在面试的人基本都刷过题，为什么自己写出dp就是见过原题？

是的。他们要求的算法不是dp.所以写出dp不可以。

这题还能O(n)啊。。

说句实话，人压根就没想要你，要想要你的话，就不会这么鸡蛋挑骨头。哪怕你用贪婪算法解了，别人还是会挑出其他问题。

啥公司啊 confluent???

作为一个大厂面试官，我和小伙伴们的共识是，除非easy题，一上来就DP的都默认见过原题，这时候有几种情况1. 这题表现可以不作为参考了。赶紧过了换题
2. 我把题目改改看你还dp 不dp


如果这种题一上来搞出贪心，兄dei，我们的共识是，你搞什么啊这么卷干嘛，这样一出手就王炸，如果你没什么ACM背景，我们会在之后的evaluation里把这事说明白，让HC自己去判断你这人的interview ethics。






为什么你们还在纠结最优解？？？？我们考察的是你这人面试过程交流怎么样，有没有把思路说清楚。。。如果你写出O(MN)还挂了，一定不是因为没给出最优解。


补充内容 (2021-1-18 02:32):
你们就继续钻牛角尖吧。不好好练习表达交流沟通，最后又回来地理说怎么搞的LC都刷了1000题好几遍还不能上岸。

补充内容 (2021-1-18 02:44):
楼下也有人说了 - “主要看coding还有交流，只要比brute force好点的算法都差不多”

不懂就问，答出的dp是啥意思？