给出二维平面上的两个正方形，找到一条直线能同时将两个正方形都分为面积相等的两半。

一条直线只要过正方形的中心，就一定会将它分为面积相等的两半。(矩形也一样) 那么，我们只要作一条过这两个正方形中心点的直线， 即可同时把这两个正方形都分为面积相等的两半。

设计算法，找到质因数只有3，5或7的第k个数。

1. 初始化结果res=1和队列q3,q5,q7

2. 分别往q3,q5,q7插入13,15,1*7
3. 求出三个队列的队头元素中最小的那个x，更新结果res=x
4. 如果x在：
   q3中，那么从q3中移除x，并向q3，q5，q7插入3x,5x,7x
   q5中，那么从q5中移除x，并向q5，q7插入5x,7x(不往q3中插入3x，因为这个数在q5中已经插入过了，eg:53插过35)
   q7中，那么从q7中移除x，并向q7插入7*x
5. 重复步骤3－5，直到找到第k个满足条件的数

线性求k最大

线性求k最大利用的是快排中的partition函数。每次选取一个基准元素pivot (可以用第1个元素，也可以随机选)，然后将其它元素与pivot对比。大于等于pivot 的放到左边，小于pivot的放到右边。调用一次partition后， pivot左边的数都是大于等于它的，pivot右边的数都是小于它的。 如果pivot此时正好是第k-1个元素，那么它左边加上它一共有k个元素， 而且这k个元素都是比右边的元素要大的，即它们就是最大的k个元素。如果pivot 左边不足k-1个元素，则在它右边进行同样的partition操作。如果pivot 左边是多于k-1个元素的，则在它左边进行partition操作。

该算法会改变数组中元素的顺序，期望时间复杂度是O(n)。

写一个程序，找到由其它单词组成的最长单词。

按单词的长度从大到小排序。(先寻找最长的单词)

不断地取单词的前缀s，当s存在于单词数组中，递归调用该函数， 判断剩余串是否可以由其它单词组成。如果可以，返回true。

随机产生一些数传递给一个函数，写程序找出并维护这些数的中位数。

中位数有一个性质，它平分了小于他的元素和大于他的元素，然后我们现在要动态加入新的元素。 新加入的元素，我们要怎么办呢？我们希望把元素分成两个集合A和B，使得满足以下两个性质：

A中元素均小于等于B中元素
A中的元素和B中元素一样多或只多一个。
如此，我们可以在log n时间内给出中位数，因为中位数要么是A的最大值，要么是A的最大值和B的最小值的平均值。同时我们也可以在log n时间加入一个新的元素并维持这两个性质：先把新元素加入A，然后把A的最大值移动到B使性质1满足，然后判断A和B的大小（如果Size A小于B则把B中最小元移入A）使性质2满足。

堆可以完美的完成上述操作，当然也可以用平衡二叉树解决，但是平衡树编写复杂，面试中不建议也需要实现此类数据结构。我们还是要用到堆这个在面试中容易出现，编写难度不大又很实用的数据结构。我们维护一个大根堆P（根节点值最大）和一个小根堆Q（根节点值最小），对应集合A和B，维护上述两个性质即可。

最大子矩阵和

O(nnm)正在思考有没有更优的。
循环i,j，b[k]为原矩阵第k列从i到j行的数字和，b[k]这一维用dp，sum<0时，sum = b[k]，or sum = max(sum,sum+b[k]）