1. 在linked list中找倒数第N个结点
2. 倒转linked list
3. 二叉树的结点有指向parent的指针，求最近公共祖先
4. 给一个数组,如何打印该数组成员构成集合的全部子集合.
5. 有两个字符串，一个是text,一个是command, Command有四种：
‘+’: 在text中前进一位
‘-’: 在text中后退一位
‘a’: 在当前位置插入一个字符，字符由command中的后一位决定
‘d’: 删除当前字符
实现函数Process(string& text, string& command, string& result);
Coding题，大致要点:
6. 实现一个LRU的cache
数据结构：
插入新cache的算法:
关于多线程，一般来说reader/writer lock不适用，因为reader也会更改LRU cache. 一种解决的办法是让每个线程拥有自己的cache.
7. 两个排序的数组，求它们的交集
8. 在二叉树中添加额外的两个指针（树可能非满），遍历整棵树并将同一层的结点用这两个额外指针连接起来
9. 用一个给定的值partition一个数组，注意这个值不一定在数组中出现
10. 用数组实现一个queue, 考虑以下一些内容：
a) 实现固定size
b) 实现可变size 每次size不够用时，建一个更大的array并复制原有数据
c) 与linked list的实现相比，有什么好处和坏处？保证了操作恒定为O(1),但是内存有浪费，且不连续
d) 如何处理thread safe
11. 洗牌算法
For i = 0 to n-1,
生成一个i到n-1之间的随机数j，将v[i]与v[j]交换
12. [Microsoft] 对stack上的元素排序，可以使用的方法有pop(), top(), push(), isEmpty(), isFull().
13. [Microsoft] 有一个M*N行的矩阵，如果第(i, j)个元素是0，则把i行和j列都设为零，注意尽量少使用额外空间
分成如下几步:
14. [Microsoft] 一个二维空间第一象限有很多点，怎么找出最外围的那些点？
Graham扫描算法：
a) Px为栈顶的下一个点，Py为栈顶，当前点为Pi
b) 如果Py->Pi, 相对于Px->Py向右
i. Pop栈
ii. Push Pi到栈
算法复杂为O(NlogN) (第二步的排序)
15. [Google] 返回一组字符串的最长公共前缀，如 “abc”, “abcdef”, “abcd”, 则返回”abc”
16. [Microsft] 给出平面上第一象限内landscape的轮廓，也就是一些列的(x,y)坐标, x=0,1,…,N
，以及Y轴上光源坐标(0,H)。问这N+1个点钟那些被照亮那些是阴影。(叉乘)
一一计算光源到(x,y)的角度，再与左边的角度对比即可知是否被遮挡，复杂度O(N)
17. [Microsoft] 一个linked list，每个节点除了正常next指针外，还有一个extra指针，这个指针可以指向链表中的任一节点，不同的extra指针可以指向同一个节点，extra指针也可能
形成loop。问怎么复制这个结构。
18. [Microsoft] 怎么组织字典，使得在解cross puzzle时可以很快得到满足条件的所有单词(比如
所有第二个字母是o，第5个是H的单词）。不过这题算brain storm，不用写code.
按单词的长度不同，构造多个container
对某一组长度相同的单词，构造多个index, 从(2,o), (5, H) 映射到单词（id）, 每一个collection保持有序，可以加快merge的速度
19. [Google] 如何设计binary tree和hash table的iterator
Binary Tree Iterator:
假设是中序遍历的话，在iterator中保存一个遍历的状态(parent node stack).
Hash Table Iterator:
取决于hash table的数据结构，一般直接按array或者bucket顺序遍历就可以了。
20. [Google] 设计一个class，类似于stack, 但可以是O(1)时间内返回min()
给stack加一个只用来保存当前最小值的stack, Push时，如果当前值比minStack栈顶小，则也push到MinStack, Pop时，如果minStack栈顶与当前pop元素一样大，则也pop minStack
21. [Google] 比较两个binary tree是不是完全一致
递归比较 if (tree1->value == tree2->value) && is_equal(tree1->left, tree2->left) && is_equal(tree1->right, tree2->right)
22. [Google] 一个整数数组里怎么同时找最大和最小的数，尽量优化比较次数
考虑二个数a,b， a与b先比，大的与当前最大比，小的与当前最小比。两个数共需要比较三次。
23. [Google] 在一个循环有序的数组里查找一个数
24. [Google] 给一个array和一个target value, 检查array里是否存在两个数之和为target
两种做法:
25. [Google] 给一个文本， 然后给出几个关键词及他们所出现的位置，比如
this: 1, 16, 55….
is: 5, 33, 77…
要求找出最短的一段文章使其具备给出的关键词。
大致算法：按位置往后找，直到所有的词都出现，然后再尝试把左边的位置缩减。如此直到找到更短的区间。
见后面的find_min_window的程序，这里需要处理inverted index
26. [Google] 给出一棵tree, 该tree没有任何特征， 即可以有多个子节点， 父节点和左右子节点也
没有大小关系。但每个节点的值不相等。现给出几个值， 如(12， 24) 请找出从根节点到值为12 和24的节点的subtree.
27. [Google] 给一个array, 再给一个sh值， 设计函数将数组内的所有元素向右偏移sh个位置(将数
组看成一个圈)。
见Programming Pearls, 先把[a,c] reverse, 再reverse[a,b],[b,c]
28. [Microsoft] 删除数组中的重复元素
略。。。
29. [Microsoft] 按如下规则转化数字的字符串
(integers that appear >=1 times)
(integers that appear >=2 times)
…
(integers that appear >=n times)
并保持字符原来的顺序
例如: 12223314->12342312
略。。。
30. [Microsoft] 检查一个表达式中的括号是否合法，括号包括 {, [, (, ), ], }
简单的栈的应用