n***t
发帖数: 76 | 1 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成为一个回文？只能在前端加，不
能在中间或者后端加。 |
c*********t
发帖数: 171 | 2 我猜第一个问题是要考察你会不会用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）
|
c*********t
发帖数: 171 | 3 我对（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）
|
c*********t
发帖数: 171 | 4 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）
|
c*********t
发帖数: 171 | 5 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）
|
m*****k
发帖数: 731 | 6 bitmap 吧
【在 c*********t 的大作中提到】
: 2. 不明白分布不分布。我会对此文件排序。从头到尾遍历文件，如果前后两值之差大
: 于1那么你就找到最小没有出现的值了。
:
: two"
|
m*****k
发帖数: 731 | 7 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）
|
c*********t
发帖数: 171 | 8 老了不知道bitmap是什么意思，如果是用一个bit纪录某数是否出现过那一定是错的。
考官会说没有那么多额外的存储空间。
所有这些很大很大的问题其实都是问排序！
【在 m*****k 的大作中提到】
: bitmap 吧
|
w****a
发帖数: 710 | |
g*****g
发帖数: 34805 | 10 1. 大文件做hash是会conflict的，所以hash只能看成一个bucket，key还是得句子本身
。也可以把hash+sentence做两次比较的Key。但这都不是重点。用Memcached, Redis一
类的结构，可以hash到K个结点上，维护个计数器，超过2可以不更新。最后各个节点把
自己查一遍就行。O(N/K)的时间。
相似句子也相似，把句子删除任意一个单词的句子都放进去，key后加个链表来表示相
似。
2. 相当一个完美哈希，节点的range就是个平均分段就行，其他的跟1没啥区别。可以
把分段后的所有可能都扔内存里然后挨个删，最后不剩几个排序时间接近O(1)。
这两道都是MapReduce. |
|
|
o***e
发帖数: 28 | 11 我觉得用一个文件来存储 bitmap (如您所说每一位代表该数字出现与否) 还好吧 可以
用 O(X) 的空间 (其实是 \Theta(X/8)) 换取 O(Y) 的时间
如果 X, Y 很大以至于需要外排序的话 其实效率也不高吧 : )
【在 c*********t 的大作中提到】
: 老了不知道bitmap是什么意思，如果是用一个bit纪录某数是否出现过那一定是错的。
: 考官会说没有那么多额外的存储空间。
: 所有这些很大很大的问题其实都是问排序！
|
g*****g
发帖数: 34805 | 12 即使数据很大放不进内存也不用排序，可以走数据库的路子，所有数字放进去
。开个内存缓冲，满了批量去删，剩下的没几个数字再排序。
【在 o***e 的大作中提到】
: 我觉得用一个文件来存储 bitmap (如您所说每一位代表该数字出现与否) 还好吧 可以
: 用 O(X) 的空间 (其实是 \Theta(X/8)) 换取 O(Y) 的时间
: 如果 X, Y 很大以至于需要外排序的话 其实效率也不高吧 : )
|
B**********2
发帖数: 923 | 13 第三个题楼主不是说分布式么。
每个计算单元假设内存极限是 Z, 则一共需要 X/Z = N个
把 X 分为N段，每段用一个单元来查就行了
bitmap是位表，C++一个标准Template
这样做不用排序，过一遍就行了
排序基于比较时间是O(N logN), 这题的意思本来就是N很大。
既然分布式了，就可以空间换时间了
【在 c*********t 的大作中提到】
: 老了不知道bitmap是什么意思，如果是用一个bit纪录某数是否出现过那一定是错的。
: 考官会说没有那么多额外的存储空间。
: 所有这些很大很大的问题其实都是问排序！
|
c*********t
发帖数: 171 | 14 也许现在技术进步了，N多年前所谓的大文件真的很大，如PB级。他软除了保存此文件
就找不到额外的空间保存中间数据了。排序的优点是没有中间数据。就在原始文件（或
内存）上操作。O(NlogN)和O(N)时间上差别不是很大。当然有一倍的空间更好。能改游
戏爆机总是很容易。
【在 B**********2 的大作中提到】
: 第三个题楼主不是说分布式么。
: 每个计算单元假设内存极限是 Z, 则一共需要 X/Z = N个
: 把 X 分为N段，每段用一个单元来查就行了
: bitmap是位表，C++一个标准Template
: 这样做不用排序，过一遍就行了
: 排序基于比较时间是O(N logN), 这题的意思本来就是N很大。
: 既然分布式了，就可以空间换时间了
|
c*********t
发帖数: 171 | 15 可能有。不过我习惯只要是P的我就不浪费时间优化。
花我一天太贵，不如多买几台服务器。
【在 w****a 的大作中提到】
: 第三题有没有比o(n^2)快的算法？
|
c*********t
发帖数: 171 | 16 我这个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.
|
c*********t
发帖数: 171 | 17 尼玛这就是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.
|
i****k
发帖数: 668 | 18 如果每个句子都不长，不到16个字节（前面给的例子就是这样），你这办法还有个P优
势啊。
【在 c*********t 的大作中提到】
: 我这个hash值不是32位整数，而是256位整数。理论上有可能碰撞。如果让你碰到，赶
: 快写论文海龟。山东大学那个女教授让美国废了MD5。好虫让美国废了SHA256！
: 谷歌就是有钱任性。好虫你是谷歌的么？
|
i****k
发帖数: 668 | 19 这没啥好奇怪的吧，MapReduce本质上不过是把大问题转化为很多个小问题，divide
conquer的思路而已。
【在 c*********t 的大作中提到】
: 尼玛这就是MapReduce？还有谁对我吹牛说那个大牛发明了MapReduce改变了世界。我们
: 一帮中国大陆穷酸20多年前就在黑板上做这种O(1)了。那时候机器才16K到48K内存。可
: 惜和我讨论那位在中国搞建筑去了。
|
g*****g
发帖数: 34805 | 20 MapReduce的贡献不在于这个方法有多牛，这个方法在狗做出来之前几十年就存在了。
而在于在一堆低端不可靠设备上做出可靠性来。归功于架构和GFS等的设计。
【在 i****k 的大作中提到】
: 这没啥好奇怪的吧，MapReduce本质上不过是把大问题转化为很多个小问题，divide
: conquer的思路而已。
|
|
|
c*********t
发帖数: 171 | 21 比较等长整数比比较串代码简单多了也快多了。
即使不用汇编/C/C++，字节对齐，包的大小还是要算的。多传一个包，你的应用用TCP
覆盖银河系就得多用26万年才能完成
【在 i****k 的大作中提到】
: 如果每个句子都不长，不到16个字节（前面给的例子就是这样），你这办法还有个P优
: 势啊。
|
m*****k
发帖数: 731 | 22 仅供参考
http://support.huawei.com/ecommunity/bbs/10185259.html
【在 c*********t 的大作中提到】
: 老了不知道bitmap是什么意思，如果是用一个bit纪录某数是否出现过那一定是错的。
: 考官会说没有那么多额外的存储空间。
: 所有这些很大很大的问题其实都是问排序！
|
h**********c
发帖数: 4120 | 23 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）
|
