2020年大厂敲门砖--巧刷算法题

纵观这么多年，今年的技术面试是真的麻烦，不知道被哪家公司带坏了，所有的公司都开始考算法题。 我不排斥算法，它可以考察思维、考察编码习惯、考察基础能力；

但是比较排斥那些心理扭曲的面试官，不报有任何目的，单纯为了体现他的优越感，那变态的优越感 而出的那些变态的题，没有任何卵用。。。然而主动权不在我们。

包括我，应该有不少同学在看算法题的时候不知道该从和下手，万物皆可盘，今天就来盘下常见的那些敲门砖。

一、从数据结构上看

本质上基本都是 数组 和 链表

有人说，不对啊 还有树啊，栈啊等等。不过，我们仔细一想就会发现，更高级的数据结构，也逃不开这两种，就拿树来说，其实就是一个链表，只不过，之前只有一个next，现在变成了两个，为了区分，就叫成了left和right。

所以，数组和链表的特性和基本操作，是基本大部分算法题的基础，是一定要掌握牢靠的。像数组的二分、链表的双指针之类都是由其对应的特性演化而来。

比如，本人最近被问过好几次的LRU缓存算法，就是一个比较典型的链表操作的运用。

一般可以用链表+hashMap的方式来实现：当查询时缓存中有，则从链表中找到该值，并移动到头部(从原位置删除并插入头部)；如果缓存中没有则考虑插入，如果空间未满，则直接插入到头部，如果空间已满，则需要将尾部的元素删除。

类似这种比较简单的题，主要考察的其实是对整个结果设计的细节把控，比如触发缓存变动的时机，节点的插入和删除等等，脱离了强大的 intellij idea ,能较少问题的快速编译成功，还是要一点功夫的。

二、从考察角度来看

2.1 编码细节考察

可能算法本身不难，主要是得关注在实现过程中细节的把控，比如异常判断、边界值的选择、编码风格的简洁规范。这种题一般都要求编译成功并实例跑通。

题 ：实现大整数加法

写法一：

写法二：

相比之下，第二种在风格、写法上可能更优些，Java语法本身相比python这些就已经很冗余了，我们更应该注意尽量把程序写的简洁易懂些才好。

这个题很多同学会直接用到StringBuilder的反转功能，面试官可能会要求不能使用现有反转功能，那可能需要考虑采用额外的存储来存放我们的结果，最后再进行反转，可能链表是一个不错的选择。

2.2 思维能力考查

从分析问题到给出解法到逐步优化的逻辑思维，这类题一般只需要给出思路，分析出时间和空间复杂度，最多写出类似伪代码的逻辑框架我理解就可以了；

题：回溯问题

给N个递增数组，每个数组中只取一个数，要求选出的这N个数的方差最小。

千万别被方差这个有点生疏的概念吓到，无非就是选值最接近的N个数，即使你真的忘了啥是方差，直接问问也不妨事，除非面试官是为了装逼他也不会，那可能场面就有点尴尬了。。。

说实话这道题至今还是没有想到一个特别优的解法，也在脉脉放出来和大家交流了下，无非是用N个指针初始化到每个数组的第0位，然后通过计算均值，来选择离均值最远的一个进行移动，和算K-means的那种感觉似的，直接稳定；有个号称微软员工的大佬给出了一个叫KDTree的思路，咱也不懂，有懂的朋友可以留言交流下。

重新反过来看上面这道题，是不是感觉有点像八皇后，都是每行选一个，从8皇后的不同列的限制，变成了本题的方差最小的限制

对于8皇后经典的回溯问题，大致解法如下

回溯，其实就是一个带现场维护的一个递归（记录现场，递归，恢复现场），所以，我们可以从这个经典问题中看到什么？

全是套路！

把8皇后的解法抽象一下，一个解决递归类问题的模板出来了。。。

那么，我们上面描述的那个方差最小的问题，是不是可以按这个套路来搞呢。

题：动态规划问题

给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法

//定义状态dp ,dp[i] 标示的是组装成i分钱的方法个数
int[] dp = newint[n + 1]; 
//dp[0] 是最初的状态，可以当成终止条件或基础条件
dp[0] = 1;
//状态转移方式，当前的方法数，依赖于不选当前硬币的前一个状态
dp[k] += dp[k - coin];
//最终实现
for(int coin : coins) {
    for(int i = coin; i <= n; i++) {
        dp[i] = dp[i] + dp[i - coin]
    }
}

动态规划或者说是最优化问题，不管是生产开发还是算法绕不开的主题。此类问题最重要的两个问题是状态的定义和状态转移，所以，我们是不是又可以总结一个动态规划的模板：

当然，dp状态推导还是要通过练来找找感觉了。

三、‘脑筋急转弯’ 猪撞树上了

当然，能考出来的还是有点绕的，直观感受上应该是要比行测题要绕一些的

题：36匹马，6条跑道，最少跑几次可以找到最快的前三匹马？

还有，是开水团的一大爷问，怎么知道当前北京上空，有几架飞机？

第一个还有点谱，起码是在考思维，第二个这个就太那个了，网上搜了下，曾经某国外的信息咨询公司在招聘时问过此类问题，主要考察的是候选人的信息收集能力，我就想问，这个和技术、思维有个啥关系。。。

林子大了 ，什么鸟也能遇的到。

总结：

算法是个好东西，多练对思维 对编程习惯都有些好处，当前在刷题的时候也要善于总结，比如文中提到的回溯，我们可以从经典的问题中提取出一套通用的模板，甚至，我们再细研究就会发现，他实际上是树的遍历，只不过是把二叉树扩展到了N叉树上。

就算不找工作，时不时的刷刷，提前防下老年痴呆也是很不错的~