有点类似于设计题，可以用一个优化过的prefix tree

137. Subset sum problem

可以转换为背包问题

138. Dutch National Flag Problem (DNFP)

http://www.iis.sinica.edu.tw/~scm/ncs/2010/10/dutch-national-fl

如果有多于三种元素，则称为America Flag Problem, 本质上是radix sort

139. 一个单词的列表，要找出两个单词，它们没有相同的字母出现，而且长度乘积最大

难题， TO LEARN

140. You are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.

DP题，定义g(n,l,r)为题目的答案，而f(n,l)为n个block,从左边看到l个block,则递推公式为：

g(n,l,r) = (1<=k<=n)sum(C(n-1,k-1)*f(k-1,l-1)*f(n-k,r-1))

f(n,l) = (1<=k<=n)sum(C(n-1,k-1)*f(K-1,l-1)*(n-k)!)

f(n,1) = (n-1)!

F(n,n) = 1

F(n,m) = 0 if n < m

141. There is a binary tree(Not a BST) in which you are given three nodes x,y,z. Write a function which finds whether y lies in the path b/w x

如何定义in the path …略。。。

142. binary search的各种变种

1）如果找不到元素，返回应该插入的位置

2）如果数组允许有重复，寻找最小的那个i，使得arr[i] = v， （第一次出现的位置）

3）如果数组允许有重复，寻找最大的那个i，使得arr[i] = v

与2)类似
4）如果数组允许有重复，寻找最小的那个i，使得arr[i] > v

5）如果数组允许有重复，寻找最大的那个i，使得arr[i] < v

与4)类似
6）给2个有序数组，大小一致，如何求他们的median

见第68题
7）循环数组的二分查找

143. 怎样de-dup一个sorted array？

可以直接线性扫描，也可以用binary search来优化（如果重复数比较多）

follow-up: 如果有一个big single file, many servers, how to use these servers to compute this problem 要求尽量balance load

balance load,可以将big file分成比较小的块，每台机器完成若干块，根据计算情况进行调度。

144. Given a number n, find the nearest palindrome of n just greater than n.

算法：

CODE

145. 有一个不定长的char string (S1)，都是0,1组成；另外一个string （S2）, 也是0,1
组成，可以认为是pattern,问S1中是否含有S2
e.g S1 = 11100011 10101011 11111111 10000100 ( 4 bytes, ’11100011′ is 1 byte)
S2 = 00111010
the answer is ture, 1110″00111010″1011

http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_a

Rabin Karp算法 ？ 略。。。

146. Write a function for a linked list that exchanges the positions of the nodes after the nodes referenced by two given pointers t and u. (assume t and u are either in the list or NULL).
Example:
1 2 4 3 6 8 5 7 9 10
Exchange nodes after 2 and 3:
1 2 6 3 4 8 5 7 9 10

简单题，略。。。

147. Design a data structure for a text editor. Require better than linear for both line search and insert a new line.

Notepad++使用gap buffer, 即在一段buffer的中间留下空间，这样插入和删除操作都是O(1). 关于search，可以用Rabin karp算法。

Rope 也是一种可以考虑的数据结构，见：

http://en.wikipedia.org/wiki/Rope_%28computer_science%29

148. Given an array of 0′s and 1′s. only, find the maximum length of the subarray such that the number of 0′s and 1′s in that subarray are equal.

将所有的0换成-1，先计算累加和,cum[i] = a[0]+…+a[i], 则问题转化为：求cum[i]相同时的最大的index差。扫描计算即可，复杂度O(N)

类似的问题有（利用累加和）：

1.一个有正有负的数组中，求一个subarray使其和最接近0

2.对数组进行add(l,r,v)操作，即对a[l]到a[r]的每一个元素加上v, 现有N个这种操作，怎么在O(N)时间内完成？

149. 一个数组有很多key，已知所有key属于三个组，存在先后顺序，现在要求把所有key按照组排序，比如{1， 2， 3}， {4， 5}， {6， 7}，key之间不需要有顺序，只要不同组之间的元素在数组里满足组规定的顺序就行了(DNFP )

DNFP问题,见138题。

150. 游戏算法，给定一个N*N格的板块，往上面放不规则的element。
如何表达这个板块，用什么数据结构来表达element，这个element有可能是任何形状，like “—”，X”，“Y”，“田”（参考俄罗斯方块）
如何判断这个element可以放在某个cell里面，放在cell的条件是这个element可以覆盖这个cell。（element之间不能重叠）
象俄罗斯方块一样，这个element可以rotate四个角度，问如何判断rotate后可以放入。

TO LEARN, 俄罗斯方块

这里的描述不是很清楚，如果是俄罗斯方块的话：（取自http://wintris.codeplex.com/）