一些大公司的面试题，大牛帮忙看看。
=========================
题目1：
有一句中间有拼错单词的英文句子，如："Ths is a worng sentencce." 其中，拼错的单
词都可以通过1次或多次编辑操作（编辑操作 包括："增加"、"删除"、"修改" 单词中的字
母）纠正，如：Ths增加一个i变成This; wrong先将o改成r，再将第二个r改成o就纠正为w
rong; sentencce中删除一个c就纠正为sentence. 假如我有一张单词表，里面有几十万个
单词，给你一个英文句子，如何发现其中出错的单词（即这个单词没有出现在我的单词表
中）并用最少的 编辑操作 纠正句子中的全部错误？
==========================
题目2：
我有一批很大的数据（约10T），每行是一个字符串（有重复）。现在的任务是想统计出重
复最多的 TOP 10% 的字符串都是哪些？ 给你1000台机器，每台机器的配置如下：1G内存
，15G硬盘。
注意：是 TOP 10% 而不是 TOP 10.
==========================
题目3：
有一台微型计算机，1M内存、CPU是 1G Hz（即每秒状态转换10^9次），问最长的可终止的
程序要运行多长时间？
==========================
题目4：
有1枚硬币，正反均匀，即投掷出去后出现正面和反面的概率都是50%。
1) 投掷10次出现：3次正面、7次反面；
2) 投掷100次出现：30次正面、70次反面；
这两种情况的概率哪个大哪个小？你是如何分析的？如何较快的分析出这类的题目？
[解决办法]
题目3：
假设一个int所占字节数为2，
时间最长的程序是不是应该是
for( int i1=0; i1 < 2^16; ++i1) for( int i2=0; i1 < 2^16; ++i2) for ... ... { 进行某操作； }
[解决办法]
1、把字典(单词个数n)读入内存，并构建AVL。O(nlogn)
2、取句子中某单词A(长度s)，在AVL中二分查找，存在，则认为单词无错。不存在则认为单词出错。O(logn)
3、先序遍历AVL，求每个结点B(长度t)与A的最长公共序列C(长度m)（动态规划可解），如果B=A或者B=C，说明此时可用“删除”或“增加”某些字母纠错，求出A、B长度之差即修改次数。O(n*(s+t))
4、对3所求C不等于A或者B，求C作为公共序列，求每对相邻字母在A和B中对应的位置之间字母个数最大值并相加。即为此次修改次数。如:A:wolng，B:wrng，C: wng。wn在A之间字母个数为2,在B之间字母个数1，修改次数为二者最大值2，两两相邻字母间的所求修改次数之和即为最后的修改次数。O(n*(s+t+m))
5、对3，4两种情况均取其修改次数最小，即为最后最少编辑次数，对应的B即为修改后单词。时间：O(nlogn) + O(n*(s+t+m))，空间：o(n) + o(st)。
[解决办法]