一道大厂Python面试题，4种解法，从青铜到王者引发的“思考”！-技术圈

“菜鸟学Python”，第“518”篇原创

金九银十应该是校招的黄金时间，大家都知道去大厂面试，算法是一个必须要过的关，无论是笔试还是面试的环节都需要。而算法这个东西如果平时你就是调包侠或者做app的时候，根本用不到，所以很有必要提前磨枪准备的。

对于国外的大厂比如微软，谷歌这样的顶级互联网公司，无论是是面试SDE( 软件开发工程师),MLE(机器学习开发工程师),还是DS(数据科学家)，第一关都是考察你的coding能力。最近有同事去苏州微软面试，回来就感慨，算法真的太重要了，每一轮面试都需要，

下面菜鸟哥用一个非常非常简单的例子，来引出我们这次的讨论。

在国内大厂字节面试或者国外的facebook面试的时候经常会问动态规划的面试题目，这个题目看起来是很难，小白很不好理解，这次先从一个斐波那契额数列的题目来由浅入深的讲述，算是开胃菜，下一篇来讲动态规划。

题目1：

1，1，2，3，5，8，13，21，34 。。。

求数值N项的值？

题目2:

走楼梯问题：

如果有100阶台阶，一个人一次可以迈1-3阶，请问有多少种走法。

其实两个题目都是大同小异，都是用递归的解法，如果你吃透第一题，第二题迎刃而解。

1.屌丝的解法：

这个就是最简单的屌丝的解法，没有啥好说的，如果n是第0项或者是第1项直接返回本身，如果从第2项开始递归往前找。

2.青铜的解法

青铜战士觉得上面的代码写的有点不够Pythonic，于是就改成了一行代码来表达，这样可以给面试官秀一下你的肌肉

上面两种解法虽然能过关，但是肯定不满意，面试会问，你觉得这两个解法，你满意了吗，有没有啥问题呢？

菜鸟肯定会认为，我这不是优化了代码，3行变一行了嘛！其实差远了，一个好的代码不仅仅是漂亮，而且还有性能上快，内存占用少。这个时候就需要你对代码有深入的思考，上面的代码如果我们求fib(50),fib(100),这个时候会运行的非常慢，原因就是因为你的代码，里面重复计算的很多。

比如我们计算10的时候，我们需要计算9和8，而计算9的时候又需要计算8和7，这里面8被重复计算了，以此类推整个二叉树里面很多节点都被重复计算了，如果用上面的算法，我们的算法的复杂度是2的(n-1)次方。

所以你只考虑代码能运行，却没有考虑代码的性能和复杂度，这肯定是不行的额，这就是面试官会问你，上面的代码你觉得ok吗？

这就考察了，你平时写代码的时候有没有考虑过性能问题？

3.高手的解法

高手开始思考了，那么我是不是加一个缓存来存储各个节点的值，这样的话我们计算的时候先从缓存里面搜索，如果存在了就不用去计算了，节省的计算的次数，提高了程序的性能。

这里我们用了一个全局的cache字典作为缓存，来存储我们每一次的计算，计算开始先搜索缓存有咩有，没有的话再开始计算。做到这里面试官会微微一笑，算是小满意了。但是很明显对于微软，facebook这样的国外大厂还不够？

你有没有考虑过你的代码的扩展性，就是你这个算法用缓存，如果是题目2也是这样的问题，你是不是要重复造轮子，能否把你的代码进行封装作为一个通用的轮子，这样题目2或者有类似的这样的问题也能处理。

这就考察了你平时写代码的时候，有没有思考过扩展性。

4.王者解法

我们用Python里面的装饰器进行封装算法，把它做成一个底座，这样上面如果插入fib的业务逻辑函数，这个代码就是计算斐波那契数列，如果加上计算爬楼梯的业务逻辑函数，这个代码就变成计算爬楼梯了，非常有扩展性。

经过上面的几次的蜕变，化茧成蝶，虽然举例这个面试题很简单，但是道理是相同的，如果你平时写代码的时候缺乏思考，只是得过且过只能run能跑起来，这个是远远不够的，好的代码一定是要推敲的，而你平时写代码会去思考吗？

希望本篇对爱好Python的同学有启发和感悟，您细细品一下。

好了，欢迎大家在留言区留言吱一声，也欢迎给个三连，支持一下哈。

左手Python，右手Java，升职就业不愁啦！

年度爆款文案

点阅读原文,领AI全套资料