干货| 算法工程师常见问题（基础算法篇）

前言
算法可以说是互联网行业当中差别最大的岗位了，推荐和搜索用到的技术和工作内容都完全不同。不仅如此，不同的公司对岗位匹配度的要求也完全不同。一般来说小公司的要求更加严苛一些，大公司则要宽泛许多。

这也是为什么很多转行想要从事算法或者是想要从事其他领域的候选人，小公司屡屡碰壁，大公司却能斩获offer的原因。

但是不管怎么说，各个岗位之间的问题还是有共性的。今天挑选其中基础算法的部分来给大家做一个分享。

类型
基础算法大家都不陌生，很多面经当中会建议，在面试之前多刷一刷LeetCode，准备一下算法题。

但是，在面试的时候，经常问到的问题主要有哪些呢？

我们把基础的算法和数据结构分开，今天先讲一讲基础算法的部分。说起来，基础的算法虽然很多，但是适合面试的时候提问的就不剩下多少了。

对算法做个总结，一般来说，面试会问到的算法，基本上以二分、dp、构造、递归、概率论为主，加上一些思维题，偶尔会问问字符串或者是图论的一些知识。

二分
二分是所有算法当中，最容易问到的，没有之一。

二分算法虽然简单，不说学过算法导论，哪怕是有所了解的人都能知道原理。但是知道原理是一回事，把题目想出来解法又是另外一回事了。

面试是为了考察思维，而不是送分，所以还是很考验思维的，如果不是专业受过算法训练的人，在面试的时候临场想出答案还是非常困难的。

这里有一个trick，一般听到面试官说一个有序数组，或者是有序的序列的时候，你就往二分上面想。这样即使你最后还是没能想出答案来，至少你也可以说你感觉是用二分来解，但是一下子没想到解法。

既然是面试，直接二分是肯定不可能的，都会留一个trick，让你去思考的。一般来说，突破点有两个，一个是更换二分的主体，另一个是更换二分的内容。我下面举两个例子。

sample 1：

一个n*m的矩阵，n和m非常大，矩阵的所有行和列有序。给定k，询问k是否在矩阵内。

既然知道了n和m非常大，并且矩阵的所有行列都是有序的，那么可以肯定一点，我们暴力枚举一定是行不通的了。通过有序性不难想到二分，但是该怎么二分呢？

想到了二分，很容易想到可以逐行二分搜索。一共n行，最多搜索n次，每一次二分是logm，所以总的复杂度是nlogm或者是mlogn。

这算是一种解法，能想到这个其实已经不错了。其实这道题的精髓在于二分的内容除了是序列之外，也可以是一个矩阵，我们可以直接对矩阵进行二分。

每一次选取行列中间位置元素，记为x，进行比较，可以将矩阵分成四个部分。其中左上方的子矩阵当中所有的元素小于x，右下方的所有元素大于x。那么每次查询可以将搜索的范围缩小1/4。剩下的三块子矩阵，使用递归，采用同样的方法进行查询即可。

聪明的读者应该已经看出来了，这其实是一个二分结合分治的运用。这题还有除了二分之外的其他解法，大家感兴趣可以自己思考一下。