开心一下，已经顺利毕业了！想起去年的这个时候，自己也在为找实习、找工作，而拼命刷算法、刷面经。最近几天闲来无事，于是，决定将之前购买的和自己收集的算法课程（主要包括“算法面试笔试视频资料”和“java后台开发面试视频资料”），整理了一下，做个总结，希望可以帮助到正在找工作的同学。其中，九章算法课程（算法基础班 算法强化班 系统设计班 动态DP班 国内BAT班）系列资料，可以见下图所示！PS：需要的同学，可以加我扣好友：3196254974！其实，说实话，这些资料挺有帮助的，针对性的，对于找实习找工作以及学习来说，比自己一个人盲目的复习，会好很多！
1 落单的数
题目描述：
有2n+1个数，其中2n个数两两成对，1个数落单，找出这个数。要求O(n)的时间复杂度，O(1)的空间复杂度。
进阶问题：如果有2n+2个数，其中有2个数落单，该怎么办？
分析
初阶：将2n+1个数异或起来，相同的数会抵消，异或的答案就是要找的数。
进阶：假设两个不同的数是a和b，并且a!=b，将2n+2个数异或起来就会得到c=a xor b，并且c不等于0。因此在c的二进制位中找到一个为1的位，可推断在这位上a和b分别为0和1，因此将2n+2个数分为该位位0的组和该位为1的组，两组中各自会包含2n’+1个数和2n’’+1个数，用初阶的算法即可解决。
2 抄书问题
题目描述：
有n本书和k个抄写员。要求n本书必须连续的分配给这k个抄写员抄写。也就是说前a1本书分给第一个抄写员，接下来a2本书分给第二个抄写员，如此类推（a1,a2需要你的算法来决定）。给定n,k和每本书的页数p1,p2..pn，假定每个抄写员速度一样（每分钟1页），k个抄写员同时开始抄写，问最少需要多少时间能够将所有书全部抄写完工？（提示：本题有很多种算法可以在不同的时间复杂度下解决，需要尽可能的想到所有的方法）
分析
解法1：动态规划 设f[i][j]代表前i本书分给j个抄写员抄完的最少耗时。答案就是f[n][k]。状态转移方程f[i][j] = min{max(f[x][j-1], sum(x+1, i)), j<x<i}。其中x是在枚举第j个抄写员是从哪本书开始抄写。 时间复杂度O(n^2*k)
解法2：动态规划+决策单调。 同上一解法，但在x的枚举上进行优化，设s[i][j]为使得f[i][j]获得最优值的x是多少。根据四边形不等式原理，有s[i][j-1]>=s[i][j]>=s[i-1][j]。因此x这一层的枚举不再是每次都是n而是总共加起来n。 时间复杂度O(n*k)
解法3：二分答案。二分最慢的时间，然后尝试一本本的加进来，加满了就给一个抄写员。看最后需要的抄写员数目是多余k个还是少于k个，然后来决定是将答案往上调整还是往下调整。 时间复杂度O( n log SUM(pi) )
3 找坏球
题目描述：
有12个球，1个没有砝码的天秤。其中有11个球的重量是一样的，另外1个是坏球，和其他球的重量不一样，但无法确定是轻了还是重了。请问如何用天秤称3次，就找到坏球并确定是轻了还是重了。（没有砝码的天秤只能比较出两边谁重谁轻或是重量相等，无法求得具体的重量差）
分析
12个球，编号A=（1，2，3，4 ）B=（5，6，7，8）C=（9，10，11，12）
分为三组:A, B, C。
先比较A,B,如果A与B平衡，则A，B中均为好球
比较5，6，7与9，10，11
若平衡，则坏球为8或12
- 比较8与任何一个好球，平衡，坏球为12；不平，坏球为8。
若不平，则目前可以知道是坏的球比好球是重还是轻，假设为重
- 比较9，10，若平衡，则坏球为12；不平，坏球为重的那个
若A，B不平，则C为好球
比较1，2，5 与 3，4，6（
交叉，这玩意面试的时候能想到？）- 若平衡，则坏球在7，8之间，且之前已经得知轻重的一个关系，再比较一次7，8
- 若不平衡，或者1，2为坏球，或者5，6为坏球，再比较一次。
4 索引比例
题目描述：
估算Baidu和Google的网页索引数量之比
分析
我们可以假设能够通过搜索引擎做到如下的两件事：
随机取到一个网页
判断某个网页(url)是否被索引
因此，在Baidu上多次随机关键词进行搜索，获取到每个关键词对应结果的若干网页信息（url），将这些url在Google上查找是否被索引到。从而得到Baidu网页中Google索引的的比例为1/B。
对Google做同样的事情，得到Google网页中被Baidu索引的比例1/G。由此可知Baidu和Google的索引比例为B:G
5 第k大的数
题目描述
初阶：有两个数组A和B，假设A和B已经有序（从大到小），求A和B数组中所有数的第K大。
进阶：有N台机器，每台机器上有一个有序大数组，需要求得所有机器上所有数中的第K大。注意，需要考虑N台机器的并行计算能力。
分析
初阶：比较A[k/2]和B[k/2]，如果A[k/2]>=B[k/2]那么A的前k/2个数一定都在前k-1大中，将A数组前k/2个数扔掉，反之扔掉B的前k/2个数。将k减小k/2。重复上述操作直到k=1。比较A和B的第一个数即可得到结果。时间复杂度O(logk) Leetcode原题，据说极其高频
进阶：二分答案S，将S广播给每台机器，每台机器用二分法求得有多少比该数小的数。汇总结果后可判断是该将S往上还是往下调整。
面试官角度：
初阶问题是一个比较难度大的算法题。需要有一定的算法训练功底。主要用到的思想是递归。首先容易想到的方法是合并两个数组（见面试题5，有序数组的合并），这样复杂度为O(k)，那么答出这个以后，面试官会问你，还有更好的方法么？这个时候就要往O(logk)的思路去想，O(logk)就意味着需要用一种方法每次将k的规模减小一半，于是想到，每次要扔掉一个数组或两个数组中的k/2个数，于是想到去比较A[k/2]和B[k/2]，仔细思考比较结果，然后想到较大的那一方的前k/2个数一定都在前k-1大的数中，于是可以扔掉。
进阶问题的考察点是逆向思维。二分答案是一种常见的算法思路（见面试题2 抄书问题），所以当你想不出题目的时候，往往可以试试看是否可以二分答案。因为需要发挥N台机器的并行计算能力，所以想到让每台机器互不相关的做一件事情，然后将结果汇总来判断。