大厂面试题偷偷改革?这类题几乎必考...

原创
2020/11/21 01:05
阅读数 8

今年的疫情以及后续的反扑导致国内外就业形势严峻,大厂layoff频出,大家都在“被迫找工作”也间接拔高了面试门槛。往年这个时间是一片跳槽成功的欢乐,而今年充斥着求职没坑、面试屡跪的哀嚎!


不止如此,包括谷歌、亚麻、脸书在内的大厂还默默提升了面试难度。比方说,往年用暴力枚举就能通过的题目,现在面试官会直接要求用动态规划(DP),解不出就直接挂了,简直无情!  









面试难度增加,DP成高频考点


由于DP题目类型多,且区别于一些固定形式的算法(DFS、二分法、KMP等),DP便成了大厂面试中的高频题,相信许多小伙伴都已经被折磨过了。


来看看大厂爱考的经典DP原题,体验一下被支配的恐惧。  





Google:经典的扔鸡蛋问题

有2个鸡蛋,从100层的大楼里从上往下扔,以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎,在第10层摔碎了,那么鸡蛋不会摔碎的临界点就是9层。那么要如何用最少的尝试次数,测试出鸡蛋不会摔碎的临界点?

领扣刷题链接:

https://www.lintcode.com/problem/drop-eggs


Amazon:超级洗衣机

有n台超级洗衣机。最初,每台洗衣机都有一些衣服或是空的。现在可以选择的m台(1≤m≤n)洗衣机,将这m台洗衣机的一件衣服同时传递给相邻的洗衣机。请求出一个移动次数的最小值,使得所有的洗衣机中的衣服数量都是一样的。

领扣刷题链接:

https://www.lintcode.com/problem/super-washing-machines












做出一道动规,当场定offer


在实战面试里,大部分人都不会做DP。可一旦你祭出这道“利器”,那你将会与其他面试者拉开明显的差距,可以说offer就稳了!


之前我们一位学员在算法面试解出了一道动规题,成功俘获亚麻面试官的“芳心”,当场定下了offer!

              

如果你也想像他一样在面试中脱颖而出,成功上岸,推荐来免费试听体验九章算法的《动态规划专题,在这里你可以学到一套完整的DP解题思路,轻松攻克所有DP类型题!








如何判断是否为DP题?

 

在面试的时候,最让人发愁的就是难以判面试题是否为动规题,其实判断动规题是有一定技巧的,如果题目的问法有以下任意特点,那这道题90%是一道DP题。


1. 求最大值/最小值

2. 求可不可行

3. 求方案总数

相反,如果面试题让你求出“所有的”方案和结果,则这道题肯定不是使用动态规划来解答。







面试官最爱考哪些类型的DP题?


常见动规类型分为如下几种:

               

其中,矩阵型、序列型和双序列型在技术面试中经常会出现,划分型、区间型和背包型偶尔出现,状态压缩和树型基本不会出现(一般在算法竞赛中才会出现)。


这些类型的DP题在我们的《动态规划专题班》中都有详细的讲解和配套练习,并且follow up常考的动态规划时间空间优化、打印路径等内容也有所涉及。


除此之外,FLAG工程师侯卫东老师还总结了一套完整且通用的动态规划解题思路,只需4步,即可轻松入门动态规划。


1. 确定状态是什么

2. 状态转移方程是什么

3. 状态的初始值是什么

4. 问题要求的最后答案是什么







谁来讲

            

上完这门课,你可以做到:  


对于面试中常见动态规划题目能迅速判断并找到解题要领

对于动态规划变种题能找到解题的突破口并轻松解决

可以对动态规划算法进行时间和空间上的优化 

面试中将不再有你不会做的动态规划题







如何试听体验?

长按二维码报名免费试听

         

        

或点击文末左下“阅读原文

本文分享自微信公众号 - 九章算法(ninechapter)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部