91. Given an int n, print all the numbers which are less than n and in the following pattern: 1,4,5,9,14… Write a recursive program.
看不懂…
92. How to sort a large collection of string
因为string的比较开销比较大，所以可以考虑用radix sort. 见138题， America flag sort问题
93. How to serialize a very sparse tree
保存parent->child关系
94. Given an arbitrarily long string, design an algorithm to find the longest repetitive substring. For example, the longest repetitive substring of “abcabcabc” is “abcabc”.
TO LEARN. Suffix tree的应用
95. reverse a link list within each k blocks
96. BST，排序双链表互相转换
CODE
97. 字符表格找单词，比如下面的3*3字符表格
1 2 3
4 5 6
7 8 9
每一个位置都是随机生成的char,给你一个字典然后找到表格里面所有可能的单词.
单词的定义是任意个连续字符组合,一个位置用过之后就不能再用.
回溯， 略。。。
98. 给一个string，输出所有由这个sting中字符组成的所有可能strings。然后，如果有重复的字符怎么办。如果给你一个string, 和输出string长度，找出由这个sting中字符组成的所有可能string
生成子集的问题，略
99. 给一个log 文件，找最长session。session定义：同一个userid，两log间隔时间小于一小时
不是很理解，用map> 来记录用户的登录时间，然后再扫描？
100. 不用乘法实现两数相乘 m*n， O(lgn)
101. 一个返回所有n比特格雷码的函数vector getGrayCode(n) 比如 getGrayCode(2)， 应该返回{0,1,3,2}
略。。。
102. 两个sorted array A，B， 问能否从A，B中各取且只取一个数，是他们的和为x
从两头scan, 略
103. 一个数组有N个元素，都大于0.将数组分成K段，求使最大的每段数组和的最小值
初始条件: f(x,y,1) = a[x] + … + a[y]
递推： f(1, n, k) = min(1<=i<=n+1-k)max{f(1,i,1),f(i+1,n,k-1)}
该问题的一个变体是: 有一个包括N个整数的数组,求k个数，使得这k个数排序后，相邻两个数的差的最小值最大。
先将数组排序
初始条件: f(x,y,2) = a[y] – a[x]
递推: f（1,n,k） = max(2<=i<=n+2-k)min(f(1,i,2), f(i,n,k-1))
104. 判断某个点是否在多边形的内部。按逆时针方向依次给出多边形的所有顶点。
图形学，考虑依次形成的所有夹角的和，如果在内为2pi, 否则为0
105. 判断一个set里是否有四个数的和等于一个target number.
预先计算所有两数之和，得到map>>
然后再这个map中搜索有没有和为target number的pair(并且index不能重复)，时间和空间复杂度O(N^2).
另外一种做法是当成子集合问集，按target number(T)做DP，复杂度O(NT)
106. how to implement priority queue (describe)
用最大/最小堆来实现，堆的heapify操作
107. 找到数组中的第二大的元素
108. 两个人（A，B）参与一个游戏，规则如下：
1）一个随机的整数数列有偶数个数,a1,a2,…a2n
2）A先从数列取数，但只能从两头取,a1 or a2n
3)然后Ｂ取数，也是只能从剩下的两头取，依此类推，两个人轮流，都只能从两头取
４）最后谁手里的数和最大赢。
设v[x,y]是当某人在数列剩下x到y位时，能拿到的最大值，n[x,y]表示需要拿的位置(x或者y)则
初始化: v[x,x] = a[x], n[x,x] = x
递推: v[x,y] = max(v[x] + (v[x+2,y]或者v[x+1,y-1], 由n[x-1,y]决定)，
v[y] +（v[x,y-2]或者v[x+1,y-1]，由n[x,y-1]决定）)
n[x,y]由上一步取v[x]还是取v[y]决定。
109. 最大回文的详细解法
Suffix tree的应用， TO LEARN
110. 假定有个graph，怎么找出不带circle的最长path
有向无环图可以用DP解，一般情形下是NP完全问题
算法：
algorithm dag-longest-path is
input:
Directed acyclic graph G
output:
Length of the longest path
length_to = array with |V(G)| elements of type int with default value 0
for each vertex v in topOrder(G) do
for each edge (v, w) in E(G) do
if length_to[w] <= length_to[v] + weight(G,(v,w)) then
length_to[w] = length_to[v] + weight(G, (v,w))
return max(length_to[v] for v in V(G))
111. 关于外部排序
一般做法：
a) 使用多块磁盘同时进行读/写
b) 使用多线程提高内存里的sort的性能
c) 使用异步的IO使sort和磁盘读/写同时进行
d) 多机的并行（map reduce ）
e) 如果key较大，则可以使用radix sort提高速度
112. 正态随机
http://en.wikipedia.org/wiki/Normal_distribution#Generating_values_from_normal_distribution
根据中心极限定义，一种简单的做法是,生成2N个(0,1)之间的随机数，然后将它们的和减去N，得到一个近似正态分布的数
113. 实现linkedIn里查找两个人之间connection的功能。（如果每人有100个熟人，假设任何两个人之间只隔6个人，需要space 100^6，内存放不下。所以改用同时从两边bfs, 需要space 2*100^3）
略。。。
114. 两个Sorted Array，找K smallest element, array1 长度M，array2长度N，要求O（logM+logN)
见68题
115. [Facebook] Given a string and a dictionary that maps a character to several
characters, print all combination and tell the complexity.
i.e., string = “face”, f=> f, @, 4, h a=> a, c, e
print: face, @ace, 4ace, …..
116. Merge sort linked list.
略。。。
详见http://www.chiark.