匿名网友
61. [Google] 两个排序好的数组，求和最小的M个pair, 比如 A={1, 2, 4, 5, 6}, B={3, 5, 7, 9}
m=3那么Results就是(1, 3),(2, 3),(1, 5)
这个结构形成了一个行列有序的矩阵，这个题就类似于在行列有序的矩阵中找第k个元素。
结论是:
对于一个n×m(n≤m)的矩阵，若每行和每列都是递增的，则可以在O(nlog2m/n)找到第k大的数。论文题目为“Generalized Selection and Ranking: Sorted Matrices”
如果是查中位数：
先找出每一行（列）的中位数，再找出中位数的中位数，这样可以去掉接近一半的数，再在剩下的数里找中位数即可，复杂度O(N(logN)^2)
62. [Microsoft] 一个数组，有大小写字母和数字，一次编历，大写字母在一起， 小写字母在一起，数字在一起.
见138. Dutch National Flag Problem (DNFP)
63. [Google] 1. 给定一个树和任意2个nodes，找出来最小的subtree包含这2个nodes 第26题
2. 写BFS算法打印subtree的nodes 等价于分层访问树
3. 如果把树变成了graph（可能有loop），怎么改刚写的BFS 需要标记已经访问过的点
64. 实现next_permutation
算法：
- 1. 从后往前找，找到第一个x1,使a[x1]<a[x1+1]
- 2. 从后往前找，找到第一个x2,使a[x2]>a[x1]
- 3. 交换a[x1],a[x2], 并且反置a[x1+1 … end]
65. 最长上升子序列
66. 给一个single linked list， 里面有true和false两类的node，写一个程序把
true node 和false node分类，并且中间生成一个新的node把两类分开。
将true和false两类node接到两个不同的list,最后再合并即可
67. 1 billion query里选出时间最近5分钟内最frequent的1000个query，one pass
精确解：选出所有5分钟内的query,count每个query的个数，同时维护一个最大堆，最后得到查询
扩展：如果query的数量非常大，则可以在一个个time windows里面做一些sample, 最后把这五分钟内的sample结果合并起来
68. 两个排序数组找共同中值。
69. 实现strstr(str1, str2)
70. 给定一个排好序的linked list，删除其中所有的重复元素。比如给定1->2->3->3->
4->4->5，返回1->2->5。给定1->1->1->2->3，返回2->3
71. 返回给定字符串的第一个不符合字母顺序的index, 比如abcdaf就需要返回第二个a的index，比如aZe就返回e的index
依次扫描即可。。。
72. 检查sudoku的输入是valid，允许solution是不完全的
略
73. 实现 wildcast string matching.
74. 给你一本dictionary，任意给你七个letters，让你找出包含这七个字母的、最长的单词。条件：可以pre-processing，这样每次给你不同的letters时，可以very efficient
将单词按长度从长到短编号
对每一个字母，建一个collection，按编号排序。
对给出的七个字母，找到它们的collection中的第一个共同的字母。
75. 表达式求值
76. 两个string, 给出它们的两个substring, 定义它们的距离为distance=sum_i|s1[i]-s2[i]|， 怎么找距离最大的两个substring?
穷举。。。 有没有更好的办法？
77 N*N的0/1矩阵，找出最大的全0矩阵
最大直方图的应用， O(N^3)时间复杂度
78. 将一个linked list按不同元素的值分组
用多个head放不同元素的组，最后合并
79. serialize and re-construct binary tree.
按pre-order遍历，写入结点，包括NULL的子结点
Re-construct的时候，读入结点，构建node,再递归构建child,(当该Node不为空)
80. 手机上的电话号码提示, 用prefix tree
CODE prefix tree
81. [Facebook] 给定一个数组，删除最少的元素使得剩下的元素有序
等价于找最长上升（下降）子序列，见65题
82. [Facebook] BST中找中间节点
中序遍历一遍放到数组中，最后拿中间数
83. [Facebook] implement char *remove_badchars(char string[], char bad_chars[]) in place。
将bad_chars放到hash中查询，用两个指针来remove bad char, code略。。。
84. [Facebook] implement adding two unsigned numbers without using “+”
85. [Facebook] How to implement a smart_pointer
TO LEARN
86. [Facebook] implement sqrt
87. [Facebook] implement reader/writer lock
TO LEARN
88. given a word a and a word b, all are 6-letter. Also given a dictionary. Find a transformation from a to b, such that: (a) each time you can changeone letter; (b) all the changed word should appear in the dictionary
图的search问题，见crack the interview. 略…
89. 给定一个硬币集合{10,5,2,1},给定一个input amount，找出所有的硬币组合其sum可以等于这个数额，硬币可以被重复使用，就是说amount = 4, 集合可以是{2,2}.
90. 集合的intersection, union
TO LEARN
