盘点互联网公司最常见的面试编程题

第一时间速享原创干货

1 突破编程题

互联网公司面试，笔试环节或第一面往往都是现场做编程题。很多面试的老铁反映说，败在了编程题上，去不了自己心仪的公司，拿不到想要的待遇。

确实，很遗憾。目前不光在国内，在北美等知名互联网公司，没有一家不做编程题的，可能比我们还要残酷，他们一般是做三道，可能挂掉一道就没有机会进入下一面。

所以，无论我们下一站通往哪里，具有良好的编程基本功，理解并掌握常用的计算机算法思想，都是必要的。好消息是，在短短的１个小时现场编程环节，公司所考的这些题目，往往有迹可循，难度适中，不会涉及技巧淫技(trick)。

这样的话，我们完全可以经过充分的准备，很稳地通过这一关，为下一环节争取更好的面试印象。

Leetcode是比较专业的训练编程题的平台，目前也有中文leetcode网站，https://leetcode-cn.com 称它为"力扣"，在这里已经总结了如何高效使用Leetcode编程题，下面结合自身做题经历，再总结下。

2 开胃小菜

力扣介绍互联网公司最常考的面试算法题时，首先亮出了5道开胃小菜，我们首先分析下为什么是这５道。

这5道题的一个基本归类：

只出现一次的数字在题库编号为 136, 难度为简单级别，考察位运算；

求众数，编号169, 难度为简单，考察位运算，分治思想；

搜索二维矩阵II，编号240，难度中等，考察二分查找，分治思想；

合并两个有序数组，编号88，难度简单，考察双指针；

鸡蛋掉落，编号887，难度为难，考察队列，决策树；

也就说这5道题目，包括简单，中等，难度都有，考察的大都也是常用的，不是偏题、怪题，平时多加训练，除了有难度的鸡蛋掉落外，可能其他都能从容应对。

但是如果平时没有有意训练，可能第一道在O(n)时间，O(1)空间下都不太容易想得出来。因此，根据题目标签，有方法体系地慢慢训练吧，不光对面试有帮助，还能培养我们的算法思维，考虑问题更加缜密，写出来的代码更高效。

3 练习方法

力扣官网进一步介绍了训练和准备面试算法题的方法，首先理清楚问题的类型，其次，掌握常用的算法和数据结构。

对于问题类型，力扣给出了下面这幅图，这幅图还是比较笼统，下面我补充一些愚见。本篇我们讨论问题的范围是面试算法题，那么问题的类型，大家的预期应该是常考算法题的一些标签、归类等。

常用的数据结构：

1) 数组，应用广泛，可以灵活结合各种算法思想使用；

2) 堆，最常用的大小堆，堆排序等；

3) 队列，先进先出的数组，二叉树的遍历可以使用队列实现

4) 栈，先进后出的数组，二叉树的遍历用栈也可实现

5) 树，比较常考，常见的比如二叉树遍历，求高度、深度，是否对称等等

6) 图，图的深度和广度优先遍历等，Dij, Flody最短路、prim 最小生成树、网络流等；

除了上图中所总结的还包括一个重要的、常考的数据结构：链表，比如链表的增删，反转，子环，拼接等，不妨多练习，很容易出错。

常用的一些算法思想或类别：

1) 动态规划，常考，重要的是找到初始条件，状态迭代方程，比如机器人不同的行走路线个数等；还有背包问题、最长子序列等等，题目相当灵活；

2) 字符串：判断是否为回文字符串，子串，共有子串等；

3) 数字考察，比如求sqrt(2)，判断数字是否为幸福数等；

4) 二分查找：sqrt(2)求法，使用它的前提一般是要求数组有序；

5) 深度优先搜索：一般可结合回溯求解很多有意思的问题，比如1234的全排列等，搜索过程往往还还会涉及剪枝技巧等；

6) 回溯：类似枚举，但超越枚举的带有智能退回到回溯点的搜索方法，常见的八皇后问题；

7) 双指针，组合使用两个指针解决问题，定好初始状态，比如止于会和处，常见的快速排序其实就有这类味道；

8) 广度优先搜索，不同于深度优先的另一种搜索机制；

9) 分治：归并排序就是分治的最典型例子

10) 位运算：文章开头说的只出现一次的数，就是一个最典型的例子，还有两个数的和分解为位运算问题。

11) 递归：递归让代码变得更精炼，二叉树的遍历就是最有代表性的例子，递归代码只有5行以内；

12) 贪心：贪心有时可以得到最优解，有时只能得到可行解。

４ 必备题目

下面参考力扣列出的一些经典题目，按照标签分类统计。

数组

152. 乘积最大子序列

169. 求众数

189. 旋转数组

217. 存在重复元素

283. 移动零

384. 打乱数组

350. 两个数组的交集II

334. 递增的三元字序列

240. 搜索二维矩阵II

238. 除自身以外数组的乘积

链表

138.复制带随机指针的链表

141. 环形链表

148. 排序链表

160. 相交链表

206. 反转链表

234. 回文链表

237. 删除链表中的节点

328. 奇偶链表

堆

155. 最小堆

215. 数组中的第K个最大元素

295. 数据流的中位数

378. 有序矩阵中的第K小的元素

347. 前K个高频元素

栈

150. 逆波兰表达式求值

227. 基本计算器II

341. 扁平化嵌套李彪迭代器

哈希

171. Excel表序列号

454. 四数相加II

380. 常数时间插入、删除和获取随机元素

队列

滑动窗口最大值

二叉树

230. 二叉搜索树中的第K小的元素

236. 二叉树的最近公共祖先

297. 二叉树的序列话与反序列化

线段树

218. 天际线问题

排序

179. 最大数

324. 摆动排序II

二分检索

162. 寻找峰值

287. 寻找重复数

315. 计算右侧小于当前元素的个数

滑动窗口

395. 至少有K个重复字符的最长子串

动态规划

124. 二叉树中的最大路径和

128. 最长连续序列

198. 打家劫舍

279. 完全平方数

300. 最长上升子序列

322. 零钱兑换

329. 矩阵中的最长递增路径

图论

127. 单词接龙

200. 岛屿的个数

207. 课程表

210. 课程表II

字符串

125. 验证回文串

131. 分割回文串

139. 单词拆分

140. 单词拆分II

208. 实现前缀树

212. 单词搜索II

242. 有效的字母异位词

387. 字符串中的第一个唯一字符

344. 反转字符串

作为补充，还有一类题目常考，并且如果平时不训练，考场上不太容易快速想出来，就是一类深度优先搜索和回溯相结合的题目，在leetcode题库中这类相似的有好几道：

如何求 1~n 这连续 n 个数的全排列

集合内元素都不相同，求子集

集合内元素可能相同，求子集

求集合的不同组合序列

各个分割字符串都是回文数：

文章参考:

https://leetcode-cn.com/explore/interview/card/top-interview-quesitons-in-2018/

https://www.zhihu.com/question/24964987/answer/200681301

http://www.sohu.com/a/311462244_473283