bobo老师，请问NP和近似算法这些概念会在面试中涉及吗
来源：1-3 如何准备算法面试
自编码簧风琴
2022-12-05
bobo老师好！我现在是一名在国外读书的学生，这学期选了算法设计与分析这门课，它主要介绍了分治算法、图、贪心算法、动态规划、NP、近似算法这些知识点，请问bobo老师，国外的面试会考察后两者吗？
另外一个问题是，由于我目前是博士一年级学生，所以对一些企业的 research scientist 或者 MLE 这种岗位比较有兴趣，请问老师，这种岗位除了在面试时对论文质量有要求之外，还会像 SWE 的面试一样考察大量算法知识吗？
谢谢bobo老师！
1回答
-
liuyubobobo
2022-12-06
这两个问题的答案基本都是： it depends.
整体，NP 问题和近似算法都不是大厂对 SWE 相关职位的算法考察的重点。尤其是近似算法，基本上已经脱离了传统的算法和数据结构领域了，可以看作是人工智能基础了。但是，很多经典问题确实属于 np 问题，比如背包问题，哈密尔路径，n 皇后问题等等。
我个人建议，从准备面试的角度，不需要对 np 相关的理论理解的特别深刻，但是这些经典问题的经典算法应该会。
至于近似算法，对于大厂的算法面试准备，近乎可以舍弃。（但是从学习的角度非常值得学，是全新的，且非常通用的，解决真实复杂问题的思路之一。）
关于 MLE 岗位是否需要面算法，主要看厂子。
据我所知，整体硅谷大厂还是有风气，不管是什么岗位，只要是需要写代码的岗位，就会面算法问题。至于深度和广度，可能会随着岗位的不同做调整。据我所知，这一点要求最严的是 Google，所有的技术岗，不管校招社招，不管什么 level，一律都要面算法（其实本质就是一定要有面试问题触及真正的代码，而不能只是泛泛而谈。）
但是因为你刚刚博一，所以等你毕业以后，行业是否会有一些变化，也不好说。所以我觉得你现在不需要太关注这个问题。整体以面试为导向的算法问题，在我看来范围是极其有限的，且真的不难。区分实力的，尤其是从看待博士生的角度来看，还是自己究竟做了一些什么有 impact 的事情。
继续加油！：）
012022-12-06
