校招面试常考算法题总结

一面：

算法题：编辑距离 ，最长上升子序列 （LC经典动态规划原题）

算法题: 旋转数组查找target的开始和结束索引 (LC 二分搜索经典题目）

最直观的做法是两次二分，第一次二分先找到分界点，第二次二分找到开始和结束

算法题1：排序数组有重复，旋转之后查找 (LC/剑指offer原题）

算法题2：二维数组左到右上到下非递增，查找元素，注意数组维度很大时要使用二分查找思想。

数学题：抛硬币的依图祖传题，具体题目记不太清了，用到了贝叶斯公式和等比数列求和。 ( 概率题以及贝叶斯公式有时候在面试中(主要是算法岗)也会遇到)

二面：

算法题：二维数组全是0或1，求全为1的最大子矩形面积 (LC85题）这道题比较难

算法题：一维数组，索引差为宽度，两边值较小的为高，求最大矩形面积, (LC84题)

算法题：全排列(LC原题，递归回溯)

算法题：topK，用了快排和堆两种思路，堆的解法让现场建堆(算法导论上那一堆关于heap-sort的辅助函数都让写，当时全职实习没时间复习基础，基本都忘了，凭借之前的印象大致写出来了)

简单的算法题：爬楼梯，斐波那契数列’

三道算法题：最长回文序列: LC516 用动态规划解

非循环打印

判断图形是否为凸多边形： 计算几何问题，用叉积，但是现场面试一般很少出现。

算法题：一维乱序数组，给定一个target，输出所有和为target的子数组 （ 使用前缀和容易给出O(n^2))的做法, LC560)

面试官做搜索和视频推荐的，给讲了mapreduce的原理，让自己用python实现word-count

map reduce 基本原理在面试中也经常问到

算法题：判断两个链表是否有交点，自己说了三四种方法，面试官比较满意。

这道题目比较简单

算法题，每隔K个翻转链表

这道翻转链表的题目，稍微有点难，需要画图思考

算法题1：给定一个一维数组，输出一个一维数组，每个位置对应输入数组相同位置之后第一个比该位置元素大的数，没有的话输出-1，当时只想出了n**2的暴力做法，这个题目可以使用单调栈，On时间复杂度，当时没想出来。

算法题2：给定一个数组，判断是否存在索引i<j<k，满足Ai<Aj<Ak，使用两种方法做出来了 (LC原题)