n*t
2 楼
1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
如何设计一种算法，能达到如下目的
（1）找出只出现一次的句子
（2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
都可以算作是类似的句子）
题目并没有说需要分布式算法还是单机算法。
2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
如何设计分布式算法，找到最小的没有出现的数？
3. 给一个字符串S，如何在S的前端加最少字符使得S成为一个回文？只能在前端加，不
能在中间或者后端加。
如何设计一种算法，能达到如下目的
（1）找出只出现一次的句子
（2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
都可以算作是类似的句子）
题目并没有说需要分布式算法还是单机算法。
2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
如何设计分布式算法，找到最小的没有出现的数？
3. 给一个字符串S，如何在S的前端加最少字符使得S成为一个回文？只能在前端加，不
能在中间或者后端加。
g*s
3 楼
【 以下文字转载自 FleaMarket 讨论区 】
发信人: geophysics (hoho), 信区: FleaMarket
标 题: [出售] 1X Samsung Galaxy Tab 4 7inch 8 GB
发信站: BBS 未名空间站 (Mon Mar 7 23:44:30 2016, 美东)
二手交易风险自负！请自行验证是否合法和一手卡！:
我想卖的物品:
Samsung Galaxy Tab 4 (7-Inch, Black, 8Gb)
可接受价格(必须明码标价！):
110
物品新旧要求:
新
邮寄方式要求:
买卖双方谁承担邮寄损失(Required if not code only):
付款方式说明:
其他补充说明:
广告的有效期:
物品来源(Required for All Cards!):
我的联系方式:
pm
Warranty期限:
state and zip:
发信人: geophysics (hoho), 信区: FleaMarket
标 题: [出售] 1X Samsung Galaxy Tab 4 7inch 8 GB
发信站: BBS 未名空间站 (Mon Mar 7 23:44:30 2016, 美东)
二手交易风险自负！请自行验证是否合法和一手卡！:
我想卖的物品:
Samsung Galaxy Tab 4 (7-Inch, Black, 8Gb)
可接受价格(必须明码标价！):
110
物品新旧要求:
新
邮寄方式要求:
买卖双方谁承担邮寄损失(Required if not code only):
付款方式说明:
其他补充说明:
广告的有效期:
物品来源(Required for All Cards!):
我的联系方式:
pm
Warranty期限:
state and zip:
k*n
4 楼
500 if no bank linked.
1k if use cc to pay. i guess if use bank to deposit then pay, then no limit.
1k if use cc to pay. i guess if use bank to deposit then pay, then no limit.
c*t
5 楼
我猜第一个问题是要考察你会不会用hash。通常很大很大就是说你只能从头到尾扫描。
我对（1）的解法：
1、对每一个句子计算hash，可以用MD5，也可以用SHA256，结果存入另一个文件。
2、对所有结果进行排序（hash值算一大整数）
3、遍历此排序后文件，如前后均不相等，说明此数对应的句子只出现一次。
two"
【在 n***t 的大作中提到】
: 1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
: 如何设计一种算法，能达到如下目的
: （1）找出只出现一次的句子
: （2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
: 顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
: 都可以算作是类似的句子）
: 题目并没有说需要分布式算法还是单机算法。
: 2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
: 数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
: 个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
我对（1）的解法：
1、对每一个句子计算hash，可以用MD5，也可以用SHA256，结果存入另一个文件。
2、对所有结果进行排序（hash值算一大整数）
3、遍历此排序后文件，如前后均不相等，说明此数对应的句子只出现一次。
two"
【在 n***t 的大作中提到】
: 1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
: 如何设计一种算法，能达到如下目的
: （1）找出只出现一次的句子
: （2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
: 顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
: 都可以算作是类似的句子）
: 题目并没有说需要分布式算法还是单机算法。
: 2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
: 数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
: 个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
c*t
6 楼
我对（2）的解法：
1、首先如（1）计算每个句子的hash，保存入一个文件并排序
2、遍历全部句子并提取所有单词
3、遍历所有句子，尝试每个单词加在头或尾，计算hash，在排了序文件中二分检索是
否有此hash，如有则这两句子符合满足要求，输出
此算法复杂度为O（句子数xlog句子数x单词数），但当句子数很大时，因为单词有限，
所以是O（句子数xlog句子数）
two"
【在 n***t 的大作中提到】
: 1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
: 如何设计一种算法，能达到如下目的
: （1）找出只出现一次的句子
: （2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
: 顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
: 都可以算作是类似的句子）
: 题目并没有说需要分布式算法还是单机算法。
: 2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
: 数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
: 个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
1、首先如（1）计算每个句子的hash，保存入一个文件并排序
2、遍历全部句子并提取所有单词
3、遍历所有句子，尝试每个单词加在头或尾，计算hash，在排了序文件中二分检索是
否有此hash，如有则这两句子符合满足要求，输出
此算法复杂度为O（句子数xlog句子数x单词数），但当句子数很大时，因为单词有限，
所以是O（句子数xlog句子数）
two"
【在 n***t 的大作中提到】
: 1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
: 如何设计一种算法，能达到如下目的
: （1）找出只出现一次的句子
: （2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
: 顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
: 都可以算作是类似的句子）
: 题目并没有说需要分布式算法还是单机算法。
: 2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
: 数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
: 个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
c*t
7 楼
2. 不明白分布不分布。我会对此文件排序。从头到尾遍历文件，如果前后两值之差大
于1那么你就找到最小没有出现的值了。
two"
【在 n***t 的大作中提到】
: 1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
: 如何设计一种算法，能达到如下目的
: （1）找出只出现一次的句子
: （2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
: 顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
: 都可以算作是类似的句子）
: 题目并没有说需要分布式算法还是单机算法。
: 2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
: 数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
: 个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
于1那么你就找到最小没有出现的值了。
two"
【在 n***t 的大作中提到】
: 1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
: 如何设计一种算法，能达到如下目的
: （1）找出只出现一次的句子
: （2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
: 顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
: 都可以算作是类似的句子）
: 题目并没有说需要分布式算法还是单机算法。
: 2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
: 数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
: 个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
c*t
8 楼
3. 需要确定两个下标i，j，在第i个坐标左右j个字符一一对成。极端就是i ＝ 0，j
＝ len － 1；或者i在中间，全部对称。
最简单粗暴的做法是做两重循环
two"
【在 n***t 的大作中提到】
: 1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
: 如何设计一种算法，能达到如下目的
: （1）找出只出现一次的句子
: （2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
: 顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
: 都可以算作是类似的句子）
: 题目并没有说需要分布式算法还是单机算法。
: 2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
: 数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
: 个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
＝ len － 1；或者i在中间，全部对称。
最简单粗暴的做法是做两重循环
two"
【在 n***t 的大作中提到】
: 1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
: 如何设计一种算法，能达到如下目的
: （1）找出只出现一次的句子
: （2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
: 顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
: 都可以算作是类似的句子）
: 题目并没有说需要分布式算法还是单机算法。
: 2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
: 数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
: 个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
m*k
9 楼
bitmap 吧
【在 c*********t 的大作中提到】
: 2. 不明白分布不分布。我会对此文件排序。从头到尾遍历文件，如果前后两值之差大
: 于1那么你就找到最小没有出现的值了。
:
: two"
【在 c*********t 的大作中提到】
: 2. 不明白分布不分布。我会对此文件排序。从头到尾遍历文件，如果前后两值之差大
: 于1那么你就找到最小没有出现的值了。
:
: two"
m*k
10 楼
3
O(n^2) find largest palindrome in S starting from S[0] , then reverse the
remaining part and prefix to S ?
two"
【在 n***t 的大作中提到】
: 1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
: 如何设计一种算法，能达到如下目的
: （1）找出只出现一次的句子
: （2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
: 顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
: 都可以算作是类似的句子）
: 题目并没有说需要分布式算法还是单机算法。
: 2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
: 数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
: 个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
O(n^2) find largest palindrome in S starting from S[0] , then reverse the
remaining part and prefix to S ?
two"
【在 n***t 的大作中提到】
: 1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
: 如何设计一种算法，能达到如下目的
: （1）找出只出现一次的句子
: （2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
: 顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
: 都可以算作是类似的句子）
: 题目并没有说需要分布式算法还是单机算法。
: 2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
: 数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
: 个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
c*t
11 楼
老了不知道bitmap是什么意思，如果是用一个bit纪录某数是否出现过那一定是错的。
考官会说没有那么多额外的存储空间。
所有这些很大很大的问题其实都是问排序！
【在 m*****k 的大作中提到】
: bitmap 吧
考官会说没有那么多额外的存储空间。
所有这些很大很大的问题其实都是问排序！
【在 m*****k 的大作中提到】
: bitmap 吧
w*a
12 楼
第三题有没有比o(n^2)快的算法？
g*g
13 楼
1. 大文件做hash是会conflict的，所以hash只能看成一个bucket，key还是得句子本身
。也可以把hash+sentence做两次比较的Key。但这都不是重点。用Memcached, Redis一
类的结构，可以hash到K个结点上，维护个计数器，超过2可以不更新。最后各个节点把
自己查一遍就行。O(N/K)的时间。
相似句子也相似，把句子删除任意一个单词的句子都放进去，key后加个链表来表示相
似。
2. 相当一个完美哈希，节点的range就是个平均分段就行，其他的跟1没啥区别。可以
把分段后的所有可能都扔内存里然后挨个删，最后不剩几个排序时间接近O(1)。
这两道都是MapReduce.
。也可以把hash+sentence做两次比较的Key。但这都不是重点。用Memcached, Redis一
类的结构，可以hash到K个结点上，维护个计数器，超过2可以不更新。最后各个节点把
自己查一遍就行。O(N/K)的时间。
相似句子也相似，把句子删除任意一个单词的句子都放进去，key后加个链表来表示相
似。
2. 相当一个完美哈希，节点的range就是个平均分段就行，其他的跟1没啥区别。可以
把分段后的所有可能都扔内存里然后挨个删，最后不剩几个排序时间接近O(1)。
这两道都是MapReduce.
o*e
14 楼
我觉得用一个文件来存储 bitmap (如您所说每一位代表该数字出现与否) 还好吧 可以
用 O(X) 的空间 (其实是 \Theta(X/8)) 换取 O(Y) 的时间
如果 X, Y 很大以至于需要外排序的话 其实效率也不高吧 : )
【在 c*********t 的大作中提到】
: 老了不知道bitmap是什么意思，如果是用一个bit纪录某数是否出现过那一定是错的。
: 考官会说没有那么多额外的存储空间。
: 所有这些很大很大的问题其实都是问排序！
用 O(X) 的空间 (其实是 \Theta(X/8)) 换取 O(Y) 的时间
如果 X, Y 很大以至于需要外排序的话 其实效率也不高吧 : )
【在 c*********t 的大作中提到】
: 老了不知道bitmap是什么意思，如果是用一个bit纪录某数是否出现过那一定是错的。
: 考官会说没有那么多额外的存储空间。
: 所有这些很大很大的问题其实都是问排序！
g*g
15 楼
即使数据很大放不进内存也不用排序，可以走数据库的路子，所有数字放进去
。开个内存缓冲，满了批量去删，剩下的没几个数字再排序。
【在 o***e 的大作中提到】
: 我觉得用一个文件来存储 bitmap (如您所说每一位代表该数字出现与否) 还好吧 可以
: 用 O(X) 的空间 (其实是 \Theta(X/8)) 换取 O(Y) 的时间
: 如果 X, Y 很大以至于需要外排序的话 其实效率也不高吧 : )
。开个内存缓冲，满了批量去删，剩下的没几个数字再排序。
【在 o***e 的大作中提到】
: 我觉得用一个文件来存储 bitmap (如您所说每一位代表该数字出现与否) 还好吧 可以
: 用 O(X) 的空间 (其实是 \Theta(X/8)) 换取 O(Y) 的时间
: 如果 X, Y 很大以至于需要外排序的话 其实效率也不高吧 : )
B*2
16 楼
第三个题楼主不是说分布式么。
每个计算单元假设内存极限是 Z, 则一共需要 X/Z = N个
把 X 分为N段，每段用一个单元来查就行了
bitmap是位表，C++一个标准Template
这样做不用排序，过一遍就行了
排序基于比较时间是O(N logN), 这题的意思本来就是N很大。
既然分布式了，就可以空间换时间了
【在 c*********t 的大作中提到】
: 老了不知道bitmap是什么意思，如果是用一个bit纪录某数是否出现过那一定是错的。
: 考官会说没有那么多额外的存储空间。
: 所有这些很大很大的问题其实都是问排序！
每个计算单元假设内存极限是 Z, 则一共需要 X/Z = N个
把 X 分为N段，每段用一个单元来查就行了
bitmap是位表，C++一个标准Template
这样做不用排序，过一遍就行了
排序基于比较时间是O(N logN), 这题的意思本来就是N很大。
既然分布式了，就可以空间换时间了
【在 c*********t 的大作中提到】
: 老了不知道bitmap是什么意思，如果是用一个bit纪录某数是否出现过那一定是错的。
: 考官会说没有那么多额外的存储空间。
: 所有这些很大很大的问题其实都是问排序！
c*t
17 楼
也许现在技术进步了，N多年前所谓的大文件真的很大，如PB级。他软除了保存此文件
就找不到额外的空间保存中间数据了。排序的优点是没有中间数据。就在原始文件（或
内存）上操作。O(NlogN)和O(N)时间上差别不是很大。当然有一倍的空间更好。能改游
戏爆机总是很容易。
【在 B**********2 的大作中提到】
: 第三个题楼主不是说分布式么。
: 每个计算单元假设内存极限是 Z, 则一共需要 X/Z = N个
: 把 X 分为N段，每段用一个单元来查就行了
: bitmap是位表，C++一个标准Template
: 这样做不用排序，过一遍就行了
: 排序基于比较时间是O(N logN), 这题的意思本来就是N很大。
: 既然分布式了，就可以空间换时间了
就找不到额外的空间保存中间数据了。排序的优点是没有中间数据。就在原始文件（或
内存）上操作。O(NlogN)和O(N)时间上差别不是很大。当然有一倍的空间更好。能改游
戏爆机总是很容易。
【在 B**********2 的大作中提到】
: 第三个题楼主不是说分布式么。
: 每个计算单元假设内存极限是 Z, 则一共需要 X/Z = N个
: 把 X 分为N段，每段用一个单元来查就行了
: bitmap是位表，C++一个标准Template
: 这样做不用排序，过一遍就行了
: 排序基于比较时间是O(N logN), 这题的意思本来就是N很大。
: 既然分布式了，就可以空间换时间了
c*t
18 楼
可能有。不过我习惯只要是P的我就不浪费时间优化。
花我一天太贵，不如多买几台服务器。
【在 w****a 的大作中提到】
: 第三题有没有比o(n^2)快的算法？
花我一天太贵，不如多买几台服务器。
【在 w****a 的大作中提到】
: 第三题有没有比o(n^2)快的算法？
c*t
19 楼
我这个hash值不是32位整数，而是256位整数。理论上有可能碰撞。如果让你碰到，赶
快写论文海龟。山东大学那个女教授让美国废了MD5。好虫让美国废了SHA256！
谷歌就是有钱任性。好虫你是谷歌的么？
【在 g*****g 的大作中提到】
: 1. 大文件做hash是会conflict的，所以hash只能看成一个bucket，key还是得句子本身
: 。也可以把hash+sentence做两次比较的Key。但这都不是重点。用Memcached, Redis一
: 类的结构，可以hash到K个结点上，维护个计数器，超过2可以不更新。最后各个节点把
: 自己查一遍就行。O(N/K)的时间。
: 相似句子也相似，把句子删除任意一个单词的句子都放进去，key后加个链表来表示相
: 似。
: 2. 相当一个完美哈希，节点的range就是个平均分段就行，其他的跟1没啥区别。可以
: 把分段后的所有可能都扔内存里然后挨个删，最后不剩几个排序时间接近O(1)。
: 这两道都是MapReduce.
快写论文海龟。山东大学那个女教授让美国废了MD5。好虫让美国废了SHA256！
谷歌就是有钱任性。好虫你是谷歌的么？
【在 g*****g 的大作中提到】
: 1. 大文件做hash是会conflict的，所以hash只能看成一个bucket，key还是得句子本身
: 。也可以把hash+sentence做两次比较的Key。但这都不是重点。用Memcached, Redis一
: 类的结构，可以hash到K个结点上，维护个计数器，超过2可以不更新。最后各个节点把
: 自己查一遍就行。O(N/K)的时间。
: 相似句子也相似，把句子删除任意一个单词的句子都放进去，key后加个链表来表示相
: 似。
: 2. 相当一个完美哈希，节点的range就是个平均分段就行，其他的跟1没啥区别。可以
: 把分段后的所有可能都扔内存里然后挨个删，最后不剩几个排序时间接近O(1)。
: 这两道都是MapReduce.
c*t
20 楼
尼玛这就是MapReduce？还有谁对我吹牛说那个大牛发明了MapReduce改变了世界。我们
一帮中国大陆穷酸20多年前就在黑板上做这种O(1)了。那时候机器才16K到48K内存。可
惜和我讨论那位在中国搞建筑去了。
【在 g*****g 的大作中提到】
: 1. 大文件做hash是会conflict的，所以hash只能看成一个bucket，key还是得句子本身
: 。也可以把hash+sentence做两次比较的Key。但这都不是重点。用Memcached, Redis一
: 类的结构，可以hash到K个结点上，维护个计数器，超过2可以不更新。最后各个节点把
: 自己查一遍就行。O(N/K)的时间。
: 相似句子也相似，把句子删除任意一个单词的句子都放进去，key后加个链表来表示相
: 似。
: 2. 相当一个完美哈希，节点的range就是个平均分段就行，其他的跟1没啥区别。可以
: 把分段后的所有可能都扔内存里然后挨个删，最后不剩几个排序时间接近O(1)。
: 这两道都是MapReduce.
一帮中国大陆穷酸20多年前就在黑板上做这种O(1)了。那时候机器才16K到48K内存。可
惜和我讨论那位在中国搞建筑去了。
【在 g*****g 的大作中提到】
: 1. 大文件做hash是会conflict的，所以hash只能看成一个bucket，key还是得句子本身
: 。也可以把hash+sentence做两次比较的Key。但这都不是重点。用Memcached, Redis一
: 类的结构，可以hash到K个结点上，维护个计数器，超过2可以不更新。最后各个节点把
: 自己查一遍就行。O(N/K)的时间。
: 相似句子也相似，把句子删除任意一个单词的句子都放进去，key后加个链表来表示相
: 似。
: 2. 相当一个完美哈希，节点的range就是个平均分段就行，其他的跟1没啥区别。可以
: 把分段后的所有可能都扔内存里然后挨个删，最后不剩几个排序时间接近O(1)。
: 这两道都是MapReduce.
i*k
21 楼
如果每个句子都不长，不到16个字节（前面给的例子就是这样），你这办法还有个P优
势啊。
【在 c*********t 的大作中提到】
: 我这个hash值不是32位整数，而是256位整数。理论上有可能碰撞。如果让你碰到，赶
: 快写论文海龟。山东大学那个女教授让美国废了MD5。好虫让美国废了SHA256！
: 谷歌就是有钱任性。好虫你是谷歌的么？
势啊。
【在 c*********t 的大作中提到】
: 我这个hash值不是32位整数，而是256位整数。理论上有可能碰撞。如果让你碰到，赶
: 快写论文海龟。山东大学那个女教授让美国废了MD5。好虫让美国废了SHA256！
: 谷歌就是有钱任性。好虫你是谷歌的么？
i*k
22 楼
这没啥好奇怪的吧，MapReduce本质上不过是把大问题转化为很多个小问题，divide
conquer的思路而已。
【在 c*********t 的大作中提到】
: 尼玛这就是MapReduce？还有谁对我吹牛说那个大牛发明了MapReduce改变了世界。我们
: 一帮中国大陆穷酸20多年前就在黑板上做这种O(1)了。那时候机器才16K到48K内存。可
: 惜和我讨论那位在中国搞建筑去了。
conquer的思路而已。
【在 c*********t 的大作中提到】
: 尼玛这就是MapReduce？还有谁对我吹牛说那个大牛发明了MapReduce改变了世界。我们
: 一帮中国大陆穷酸20多年前就在黑板上做这种O(1)了。那时候机器才16K到48K内存。可
: 惜和我讨论那位在中国搞建筑去了。
g*g
23 楼
MapReduce的贡献不在于这个方法有多牛，这个方法在狗做出来之前几十年就存在了。
而在于在一堆低端不可靠设备上做出可靠性来。归功于架构和GFS等的设计。
【在 i****k 的大作中提到】
: 这没啥好奇怪的吧，MapReduce本质上不过是把大问题转化为很多个小问题，divide
: conquer的思路而已。
而在于在一堆低端不可靠设备上做出可靠性来。归功于架构和GFS等的设计。
【在 i****k 的大作中提到】
: 这没啥好奇怪的吧，MapReduce本质上不过是把大问题转化为很多个小问题，divide
: conquer的思路而已。
c*t
24 楼
比较等长整数比比较串代码简单多了也快多了。
即使不用汇编/C/C++，字节对齐，包的大小还是要算的。多传一个包，你的应用用TCP
覆盖银河系就得多用26万年才能完成
【在 i****k 的大作中提到】
: 如果每个句子都不长，不到16个字节（前面给的例子就是这样），你这办法还有个P优
: 势啊。
即使不用汇编/C/C++，字节对齐，包的大小还是要算的。多传一个包，你的应用用TCP
覆盖银河系就得多用26万年才能完成
【在 i****k 的大作中提到】
: 如果每个句子都不长，不到16个字节（前面给的例子就是这样），你这办法还有个P优
: 势啊。
m*k
25 楼
仅供参考
http://support.huawei.com/ecommunity/bbs/10185259.html
【在 c*********t 的大作中提到】
: 老了不知道bitmap是什么意思，如果是用一个bit纪录某数是否出现过那一定是错的。
: 考官会说没有那么多额外的存储空间。
: 所有这些很大很大的问题其实都是问排序！
http://support.huawei.com/ecommunity/bbs/10185259.html
【在 c*********t 的大作中提到】
: 老了不知道bitmap是什么意思，如果是用一个bit纪录某数是否出现过那一定是错的。
: 考官会说没有那么多额外的存储空间。
: 所有这些很大很大的问题其实都是问排序！
h*c
26 楼
1. 如果句子长度有限，可以先分析
比如16,
In addition, 可以就每个句子的高频字母进行分类
比如
i love you
o2e1i1l1v1
I do not give shit
o2t2...
如果你的copora 有也这样的分类，估计能直接把句子找出来
3. 应该先找input 里是不是有一个最大子回文
1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
如何设计一种算法，能达到如下目的
（1）找出只出现一次的句子
（2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
都可以算作是类似的句子）
题目并没有说需要分布式算法还是单机算法。
3. 给一个字符串S，如何在S的前端加最少字符使得S成为一个回文？只能在前端加，不
能在中间或者后端加。
【在 n***t 的大作中提到】
: 1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
: 如何设计一种算法，能达到如下目的
: （1）找出只出现一次的句子
: （2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
: 顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
: 都可以算作是类似的句子）
: 题目并没有说需要分布式算法还是单机算法。
: 2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
: 数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
: 个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
比如16,
In addition, 可以就每个句子的高频字母进行分类
比如
i love you
o2e1i1l1v1
I do not give shit
o2t2...
如果你的copora 有也这样的分类，估计能直接把句子找出来
3. 应该先找input 里是不是有一个最大子回文
1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
如何设计一种算法，能达到如下目的
（1）找出只出现一次的句子
（2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
都可以算作是类似的句子）
题目并没有说需要分布式算法还是单机算法。
3. 给一个字符串S，如何在S的前端加最少字符使得S成为一个回文？只能在前端加，不
能在中间或者后端加。
【在 n***t 的大作中提到】
: 1.有个很大很大的文件， 每一行是一句话。有可能有重复的话。
: 如何设计一种算法，能达到如下目的
: （1）找出只出现一次的句子
: （2）找出类似的句子。 （类似的定义是：两个句子只相差一个单词但是相同的单词
: 顺序需要一样。 比如"I love you" 和 "I love", "I love him", "I love you two"
: 都可以算作是类似的句子）
: 题目并没有说需要分布式算法还是单机算法。
: 2. 有很多很大的文件，文件中每一行是一个正整数。 所有文件中，数字的总
: 数量是Y。 所有这些数字的数值范围是[1,X]，可能有重复。 （换句话说，如果每一
: 个数字都不一样的话那么X==Y，但是实际情况可能是X接近于Y）
相关阅读
Motorola MILESTONE XT720 unlocked $369 怎么样？在AmazonWireless买手机如何keep现在的号码？上网时自动记录的密码怎么查？有没有14inch的reader谁能给个samantha for igo primo的连接今天早晨看别人折腾的iRobot Roomba + KinectKOHLS的Literati论Smart Phone自带GPS如何秒杀Garmin，TomTom以及麦哲伦 (转载)Laptop Connector Card能用iphone的data plan嘛？kindle上pdf文件highlight和take notes的功能是软件方面的还是硬件方面快手看片/下载不错请问下tmobile的定制机刷机可以用att吗？问个Android 2.1的问题android PDAnet 在 verizon 还能用吗？Android系统的T-Mobile My Touch 3G手机,求中国象棋游戏debian装android sdk的问题有用Sony PRS－950的吗双核手机LG STAR的评测出来了每个主意一个包子