先按结束的时候排序，然后依次选取

162. Search in skip list

TO LEARN

163. 给定一个string，可以任意删除其中的char,以使的剩下的string成为palindrome,求最长的这样的palindrome。问有啥dp算法可以解？

与reverse求longest common subsequence

164. 把一个有大写字母和小写字母的字符串变换成小写字母在前面大写字母在后面的字符串

略, partition

165. 给很多date ranges,一个array, 每个date range有开始日期和结束日期，判断连续不连续

CODE

166. 实现hash表

CODE

167. 判断两二叉树全等（在可以交换左右子树的条件下），进一步给出需要多少次交换。

CODE

168. 一个NxN矩阵，每个格子有一个整型数，从左上角到右下角找一条路径使得经过的格子数字和最大。只能向右和下移动。时间复杂度，如何优化。

DP，复杂度O(N*N)

169. 现在假设有一堆整数数组，有一个flip函数，接受一个数组下标i为参数，作用是将数组index 从0到i的元素反转。eg. 假设数组为5, 6, -1, 3, 2, 如果调用flip(3)，那么就将数组下标0, 1, 2, 3反转，数组变为 3, -1, 6, 5, 2。问：只使用flip函数(不能直接用swap或数组下标操作[]等对数组进行修改)，来对该数组排序。

IDEA：每做两次flip将当前最大的item放到位上

CODE

170. 一个大小为N的数组，其中有N-1个不同的整数，范围从0-N, 问找出missing的那个
整数。然后又扩展，问如果有k个missing，如果用O(1)space去找出来。

IDEA：将整数i放到数的第i位上

CODE

171. Suppose we have a stream of web clicks. Now you need to provide at any time the count of web clicks during the past 1 minute. To be specific, you get informed whenever a web click happens. You need to provide a function “getCount()” such that once called, return the count of clicks during the past 1 minute. The solution will be both constant in time and space.

用一个circular buffer来保存每一秒的click数，再维护一个total数即可。

172. 一个有序序列，从某个地方rotate，求在rotate的位置，比如 1 3 5 0 0 0，那么rotate的位置是5，他后来只用了5行就写出来了，很nb，被bs了~~
173. 二分图最大匹配

略。。。

174. [Facebook] implement copy-on-write string class.

TODO

175. 给你n个数字a1,a2…an，表示坐标上面（i，ai）个点，i＝1..n（i，ai）到（i，0）共n个线段，从中挑两条，和x轴一起构成一个容器，让容器能装的液体容量最大(容器不能倾斜)。

穷举？。。。

176. Describe an algorithm that takes an unsorted array of axis‐aligned rectangles and
returns any pair of rectangles that overlaps, if there is such a pair. Axis-aligned means that all the rectangle sides are either parallel or perpendicular to the x‐ and y‐axis. You can assume that each rectangle object has two variables in it: the x‐y coordinates of the upper‐left corner and the bottom‐right corner.

穷举？。。。

177. Given a list of intervals, 比如 (10,20),(30,50)…,and a target interval,
比如(18,35) 找有多少overlap.

http://programmers.stackexchange.com/questions/64132/interestin

INTERVAL TREE

178. 给定一个integer array, a1,a2…an, 找出所有a,b,c,d使得a+b = c+d. 很容易找到O(n^2)空间，O(n^2)时间的算法，不知道有没有更快更好的。

如果所有的数都相等，那至少需要O(n^2)时间复杂度。另外排序后，二重循环加两头扫描，不需要额外的空间复杂度了。

179. n个球, n很大 > 1 billion, k个颜色, k相对小， 比如10. 要求in space sort最efficient的做法 白板coding. （hint, k<< n 所以最后算法争取比nlog(n)小)
该题的第二问 k = 1000 实现比nlogn 更efficient的in space的算法

见138题

180. If the Fibonacci series is 1,2,3,5,8,13,….. then 10 can be written as 8 +
2 ==> 10010 and 17 can be written as 13 + 3 + 1 ==> 100101. The Question was, given n, I need to get all possible representations of n in Fibonacci Binary Number System. as 10 = 8 + 2 ==> 10010 also 10 = 5 + 3 + 2 ==> 1110 (Zeckendorf’s theorem)

如果要得到所有的组合，先计算出该数范围内的Fibonacci数，再当成找零问题来计算就可以了。

Zeckendorf’s theorem:

Every positive integer can be represented uniquely as the sum of one or more distinct Fibonacci numbers in such a way that the sum does not include any two consecutive Fibonacci numbers.