知乎：互联网公司最常见的面试算法题有哪些？

链接：https://www.zhihu.com/question/24964987

编辑：深度学习与计算机视觉

声明：仅做学术分享，侵删

作者：知乎用户
https://www.zhihu.com/question/24964987/answer/128620102

本人在美国10年，FLAG公司，以及各大科技巨头面试也见过很多次，可以大概的分享下我的经验

首先需要明白的是：应届毕业生和在职跳槽，面试难度上，应届毕业生的难度，以及打分的要求，会略低于在职跳槽，原因很简单，应届毕业生经验不足，没有全职的工作经历。

至于湾区FLAG和各大公司巨头的面试流程，时间线，不是本问题的中心，如果需要的话，可以私信我。

首先，作为程序员，你必须知道Leetcode这个OJ，刷题题库，必备
题目分为easy, medium, hard等级，没有听说过的朋友可以先去看看。

现在讲讲面试的题目

Facebook，面试难度9分
考察的知识点很全面，Facebook的面试题目难度一般都在medium偏上一点，但为什么我打难度9分，因为Facebook的面试要求很高，简单的说，面试者必须在最快的时间内写出bug free的代码，一旦出现BUG，这轮面试基本就挂了。另外，FB比较强调最优解。比如，会先问你2sum，然后拓展到3sum，4sum。比如经典的动态规划，背包问题以及所有的follow up，都是比较经典的常考题目。

Linkedin，面试难度7分
Linkedin的面试难度适中，Leetcode上中等难度的题目居多，经典一点的，比如nested element iterator, sqrt, paint fence都是比较经典的题目。大概的难度都在这个范围之内

Amazon，面试难度6.5
整体而言，亚马逊在硅谷的四大巨头里的面试，技术难度是最低的，但是能够成功通过面试并没多很多。原因在于亚马逊很看重行为类问题（behaviral question）以及公司的文化配合（culture fit）。技术方面，经典一点的题目，比如最长回文串，二叉树层遍历，二叉树validate等等

Google，面试难度9.5
狗家的面试题目，在LEETCODE上算是medium偏难，以及一些hard的题目。但最难的点在于，谷歌有自己的题库，而且是不断跟新的，这个就无形中增大了面试难度。题目方面，谷歌考得很全面，线段树(segment tree)，动态规划DP，以及图，是常出现的。

作者：文航
https://www.zhihu.com/question/24964987/answer/33541018

说一说我在Airbnb当面试官的经验

先说个结论：算法是其次，主要是写码能力与熟练度

Airbnb一般的coding面试的流程是45分钟，10~15分钟白板分析下问题，25~30分钟上机实现算法，5分钟留给面试者问问题

时间的限制决定了题不可能太难，基本不会超过leetcode难度。而且Airbnb作为还算是创业公司，更看重的是快速落实一个想法的能力。一些常用的算法（什么拓扑排序啊，回溯，最小生成树这些，都是很基本的）你忘了也没关系，我们可以一起在白板上推。稍微有点实力的面试者白板出一个solution是没有问题的，所以这个时候就主要看写码能力与熟练度了。

上机写码考察的方面很多，比如面试者

• 语言的熟练程度 语言不重要，但你总得对你拿来面试的语言很熟吧。我们会先问你prefer什么语言，然后选这个语言熟的面试官来。
  
• 落实设计的能力 最怕吹半天，写一行代码都困难的那种人。
• 对电脑的熟悉程度  这个不是必须，但熟练使用快捷键、shell之类的总是加分项

湾区据我所知有越来越多的公司是采用上机写码或者pair programming的这种形式。（Square是纯pair programming。Uber是只白板，所以uber印度人多）

我见过很多面试者，名校毕业简历上project一大堆，结果第一步implement一个图都扭扭捏捏半天搞不出来，估计在project里面也就酱油为辅混资历为主。还有Amazon资深工程师，在eclipse里面写java，每一行不写完，让IDE自动改错，还都是拿鼠标去点，结果愣是没写完。

作者：土豆不是马铃薯
https://www.zhihu.com/question/24964987/answer/137554551

2017年校招，总共面试10家互联网公司，总结一下大概遇到的算法题。
1.数组中逆序对计算。(剑指offer)

2.判读一个树是不是另一个树的子树(剑指offer)

3.数据流要求o(1)求得中位数，o(lgn)插入（剑指offer）

4.顺时针打印矩阵（剑指offer）

5.复杂链表复制（剑指offer）

6.二叉排序树中第k小的数（剑指offer）

7.反转链表递归  、非递归（剑指offer）

8.链表中倒数第k个结点（剑指offer）

9.数组中超过一半的数字(剑指offer)

10.左旋转字符串（剑指offer）

11.把二叉树打印成多行（剑指offer）

12.旋转数组查找（剑指offer）

13.链表归并排序

14.Trapping Rain Water：https://leetcode.com/problems/trapping-rain-water/

15.Longest Palindromic Substring：https://leetcode.com/problems/longest-palindromic-substring/

16.Gray Code：https://leetcode.com/problems/gray-code/

17.Binary Tree Maximum Path Sum：https://leetcode.com/problems/binary-tree-maximum-path-sum/

18.Search for a Range：https://leetcode.com/problems/search-for-a-range/

19.算术表达式转逆波兰表达式（后缀表达） 

20.k-means  

21.字符串由大小写字母组成，要求去重，只允许使用几个int临时变量，要求时间复杂度尽可能少

22.青蛙每次跳台阶，每次一步或者二步，青蛙总共可以跳n次，台阶共m阶（n<=m），每个台阶有若干害虫，使得青蛙吃的害虫最多。

23.左右括号组成的字符串，去除最少使得剩余的字符串是合法的（符合左右括号规则）

24.实现5选3  组合

25.数组中后面的数减前面的数差的最大值，要求时间、空间复杂度尽可能低

26.多个有序数组的归并

27.多个有序数组求交集

28.二个有序数组求差集

29.字符串中最长不重复子串

30.小于10万的回文数的个数
总结：多刷几遍剑指offer！！！

往期精彩：
【原创首发】机器学习公式推导与代码实现30讲.pdf
【原创首发】深度学习语义分割理论与实战指南.pdf
 谈中小企业算法岗面试
 算法工程师研发技能表
 真正想做算法的，不要害怕内卷
 算法工程师的日常，一定不能脱离产业实践
 技术学习不能眼高手低
 技术人要学会自我营销
 做人不能过拟合
求个在看