s*******u
发帖数: 25 | 1 估计是悲剧了，给一个list of sentences, 然后找出一个pair,common words 最大。
举例：
This is a good day
This is a bad day
That was good day
return 第一个和第二个句子，因为有四个common words. 当时随口说了一个O(N^2)的
，本想仔细想想，人家说这样不好，但是你写吧。。直接就让这么写了，然后就没有然
后了。后来也没想出来个好方法，大牛们给个思路吧。 |
c********t
发帖数: 5706 | 2 This is a good day
That was good day
算几个common words?
下列算几个？
This is a good day
What a good day is
【在 s*******u 的大作中提到】
: 估计是悲剧了，给一个list of sentences, 然后找出一个pair,common words 最大。
: 举例：
: This is a good day
: This is a bad day
: That was good day
: return 第一个和第二个句子，因为有四个common words. 当时随口说了一个O(N^2)的
: ，本想仔细想想，人家说这样不好，但是你写吧。。直接就让这么写了，然后就没有然
: 后了。后来也没想出来个好方法，大牛们给个思路吧。
|
j******2
发帖数: 362 | 3 关注这题
【在 s*******u 的大作中提到】
: 估计是悲剧了，给一个list of sentences, 然后找出一个pair,common words 最大。
: 举例：
: This is a good day
: This is a bad day
: That was good day
: return 第一个和第二个句子，因为有四个common words. 当时随口说了一个O(N^2)的
: ，本想仔细想想，人家说这样不好，但是你写吧。。直接就让这么写了，然后就没有然
: 后了。后来也没想出来个好方法，大牛们给个思路吧。
|
p*****2
发帖数: 21240 | 4 如果m个sentence，平均每个n个words
要m^2*n的复杂度吧？ |
s*******u
发帖数: 25 | 5 This is a good day
That was good day
算几个common words?
算两个good day，都简化了，空格split，然后大小写都无所谓(nnd,面得时候忘了问大
小写了)
下列算几个？
This is a good day
What a good day is
4个，不算顺序。 |
c********t
发帖数: 5706 | 6 你用hashmap解吧，m^2*n
有没有可能用suffix tree 呢？
【在 p*****2 的大作中提到】
: 如果m个sentence，平均每个n个words
: 要m^2*n的复杂度吧？
|
p*****2
发帖数: 21240 | 7
hashset就可以了。
suffix tree怎么搞？
【在 c********t 的大作中提到】
: 你用hashmap解吧，m^2*n
: 有没有可能用suffix tree 呢？
|
c********t
发帖数: 5706 | 8 想了想，好像搞不了。排序呢？
【在 p*****2 的大作中提到】
:
: hashset就可以了。
: suffix tree怎么搞？
|
p*****2
发帖数: 21240 | 9
排序好像也没省时间。
【在 c********t 的大作中提到】
: 想了想，好像搞不了。排序呢？
|
p*****2
发帖数: 21240 | |
|
|
c********t
发帖数: 5706 | 11 先 每个sentence 都排序 m*nlogn
再 sentence排序 mlogm (不确定是不是这个复杂度）
再 两两比较 m*n
【在 p*****2 的大作中提到】
: LZ当时怎么答的？
|
c********t
发帖数: 5706 | 12 貌似brute force了
【在 p*****2 的大作中提到】
: LZ当时怎么答的？
|
p*****2
发帖数: 21240 | 13
LZ不是N^2解的吗？
【在 c********t 的大作中提到】
: 貌似brute force了
|
s*******u
发帖数: 25 | 14 我直接就暴力的hashset了，但是感觉哥们要更好的方法 |
s*******u
发帖数: 25 | 15 说错了，hashmap
【在 s*******u 的大作中提到】
: 我直接就暴力的hashset了，但是感觉哥们要更好的方法
|
p*****2
发帖数: 21240 | 16
店面答成这样也可以了吧？感觉不容易想更好的。不知道是不是跟一些search算法相关
。
【在 s*******u 的大作中提到】
: 我直接就暴力的hashset了，但是感觉哥们要更好的方法
|
s*******u
发帖数: 25 | 17 没有，n^2m
【在 p*****2 的大作中提到】
:
: 店面答成这样也可以了吧？感觉不容易想更好的。不知道是不是跟一些search算法相关
: 。
|
d*s
发帖数: 699 | 18 感觉跟inverted index有关，但想不出比sorting更好的算法 |
Y**Y
发帖数: 66 | 19 我的想法：
所有的words放在一起拍序，然后对每个出现多余一次的word,产生他们所在的list的
index的pair.
比如这个例子： day(1), day(2), day(3)， 就产生(1,2), (1,3), (2,3)
然后再hash_table,算出现次数最多的pair.
不过worst case还是m*n^2：(m*n)log(m*n) + m*n^2.
【在 s*******u 的大作中提到】
: 估计是悲剧了，给一个list of sentences, 然后找出一个pair,common words 最大。
: 举例：
: This is a good day
: This is a bad day
: That was good day
: return 第一个和第二个句子，因为有四个common words. 当时随口说了一个O(N^2)的
: ，本想仔细想想，人家说这样不好，但是你写吧。。直接就让这么写了，然后就没有然
: 后了。后来也没想出来个好方法，大牛们给个思路吧。
|
f*****e
发帖数: 2992 | 20 如果长度相等，有概率方法近似算。
【在 d*s 的大作中提到】
: 感觉跟inverted index有关，但想不出比sorting更好的算法
|
|
|
b*****u
发帖数: 648 | 21 建立一个词典 map > dict
对每一个新句子 i 里的单词 w，dict[w].push_back(i)， 耗时 mn
然后再对每个句子里的词进行查询， 对得到的句子编号(对应的词数)进行堆排序，找
出最大值和对
应的句子， 耗时 mnlogn， 结果写在一个m*m的矩阵里
最后对矩阵里的元素进行堆排序，耗时 m^2 log m^2
总共是 mn+mnlogn+mmlogm, 小于 nm^2 |
d*s
发帖数: 699 | 22 是的，我的想法是把单词当作维度，如果句子中出现了这个单词，就标记为1，否则为0，
那么在字典展开的空间里，相似度就是两个向量的内积。
可以用locality sensitive hashing来做clustering，求出所有相似的词组，不过似乎
这个对于严格求解最相似的一对句子帮助不大
【在 f*****e 的大作中提到】
: 如果长度相等，有概率方法近似算。
|
f*******t
发帖数: 7549 | 23 这个很可能是最优解
为0，
【在 d*s 的大作中提到】
: 是的，我的想法是把单词当作维度，如果句子中出现了这个单词，就标记为1，否则为0，
: 那么在字典展开的空间里，相似度就是两个向量的内积。
: 可以用locality sensitive hashing来做clustering，求出所有相似的词组，不过似乎
: 这个对于严格求解最相似的一对句子帮助不大
|
f*****e
发帖数: 2992 | 24 和我想的差不多。
为0，
【在 d*s 的大作中提到】
: 是的，我的想法是把单词当作维度，如果句子中出现了这个单词，就标记为1，否则为0，
: 那么在字典展开的空间里，相似度就是两个向量的内积。
: 可以用locality sensitive hashing来做clustering，求出所有相似的词组，不过似乎
: 这个对于严格求解最相似的一对句子帮助不大
|
b*****u
发帖数: 648 | 25 good point
如果需要两两计算内积，复杂度为n, 结果还是n×m^2
我觉得关键是避免直接比较句子和句子的相似度
为0，
【在 d*s 的大作中提到】
: 是的，我的想法是把单词当作维度，如果句子中出现了这个单词，就标记为1，否则为0，
: 那么在字典展开的空间里，相似度就是两个向量的内积。
: 可以用locality sensitive hashing来做clustering，求出所有相似的词组，不过似乎
: 这个对于严格求解最相似的一对句子帮助不大
|
e***s
发帖数: 799 | 26 大牛，我表示没一个名词看得懂。
为0，
【在 d*s 的大作中提到】
: 是的，我的想法是把单词当作维度，如果句子中出现了这个单词，就标记为1，否则为0，
: 那么在字典展开的空间里，相似度就是两个向量的内积。
: 可以用locality sensitive hashing来做clustering，求出所有相似的词组，不过似乎
: 这个对于严格求解最相似的一对句子帮助不大
|
d*s
发帖数: 699 | 27 把所有句子用向量表示之后可以用n-dimensional all nearest neighbohr search,
nlgn
搜索过程中记录下最近的一对就可以了。总共的操作耗时O(m*n + nlgn)，应该是最优了
http://link.springer.com/article/10.1007%2FBF02187718
不过我不认为普通青年可以在面试时间内把这个算法做完。。。
【在 f*******t 的大作中提到】
: 这个很可能是最优解
:
: 为0，
|
p*****p
发帖数: 379 | 28 对，不管怎么弄只要两两比就m^2了
或者计算minhash后排序，两两之间靠近的是最相似的，但这个应该只是近似解
【在 b*****u 的大作中提到】
: good point
: 如果需要两两计算内积，复杂度为n, 结果还是n×m^2
: 我觉得关键是避免直接比较句子和句子的相似度
:
: 为0，
|
c********t
发帖数: 5706 | 29 数学白痴完全不懂ls几位说的。
按你的思路，我给个解法吧，不用排序
HashMap> 存有这个单词的句子序号。
HashMap, int count> 存两句子index pair和两句的重复单词数。
一边扫描所有句子所有单词，对每个词，insert/update上上面两个map.
最后结果是第二个map里，最大count的 pair
复杂度 m*n*k k是每两个句子的平均重复词数。对相似度不大的很多句子，应该非常快
。
程序很好写。
【在 Y**Y 的大作中提到】
: 我的想法：
: 所有的words放在一起拍序，然后对每个出现多余一次的word,产生他们所在的list的
: index的pair.
: 比如这个例子： day(1), day(2), day(3)， 就产生(1,2), (1,3), (2,3)
: 然后再hash_table,算出现次数最多的pair.
: 不过worst case还是m*n^2：(m*n)log(m*n) + m*n^2.
|
s*******u
发帖数: 25 | 30 这个太狠了吧。。。作为2b青年的我表示压力很大。。
优了
【在 d*s 的大作中提到】
: 把所有句子用向量表示之后可以用n-dimensional all nearest neighbohr search,
: nlgn
: 搜索过程中记录下最近的一对就可以了。总共的操作耗时O(m*n + nlgn)，应该是最优了
: http://link.springer.com/article/10.1007%2FBF02187718
: 不过我不认为普通青年可以在面试时间内把这个算法做完。。。
|
|
|
j******2
发帖数: 362 | |
m*****n
发帖数: 204 | 32 有个思路不知道对不对, 就是递归去分析
M sentences, U unique words, N word counts. Build mapping from word to set
of sentences: O(M*N)
Put unique words in any order. Loop from 1..U, maintain the current best
and second best subsets.
May need backtrack to find previous third best to promote but I haven't
figured out this part.
【在 s*******u 的大作中提到】
: 估计是悲剧了，给一个list of sentences, 然后找出一个pair,common words 最大。
: 举例：
: This is a good day
: This is a bad day
: That was good day
: return 第一个和第二个句子，因为有四个common words. 当时随口说了一个O(N^2)的
: ，本想仔细想想，人家说这样不好，但是你写吧。。直接就让这么写了，然后就没有然
: 后了。后来也没想出来个好方法，大牛们给个思路吧。
|
f*****e
发帖数: 2992 | 33 怎样才能成为一个优秀的data scientist呢？
需要什么样的skill set呢？
你是CS+statics背景吗？
优了
【在 d*s 的大作中提到】
: 把所有句子用向量表示之后可以用n-dimensional all nearest neighbohr search,
: nlgn
: 搜索过程中记录下最近的一对就可以了。总共的操作耗时O(m*n + nlgn)，应该是最优了
: http://link.springer.com/article/10.1007%2FBF02187718
: 不过我不认为普通青年可以在面试时间内把这个算法做完。。。
|
B********t
发帖数: 147 | 34 冷骑哥 写个代码出来吧。。我没想明白怎么update第二个map
【在 c********t 的大作中提到】
: 数学白痴完全不懂ls几位说的。
: 按你的思路，我给个解法吧，不用排序
: HashMap> 存有这个单词的句子序号。
: HashMap, int count> 存两句子index pair和两句的重复单词数。
: 一边扫描所有句子所有单词，对每个词，insert/update上上面两个map.
: 最后结果是第二个map里，最大count的 pair
: 复杂度 m*n*k k是每两个句子的平均重复词数。对相似度不大的很多句子，应该非常快
: 。
: 程序很好写。
|
t********6
发帖数: 348 | 35 伪代码，不是最优解，轻拍
// make sure not same word in one sentence??
// what if same word in one sentence??
unordered_map > M;
int best;
int s1; // best sentence 1
int s2; // best sentence 2
for ( s : sentence ) {
// N: the number of common words with sentence a is b
unordered_map N;
for ( w : s) {
for( i : M[w]) {
N[i]++;
if (N[i] > best) {
// update the best, s1, s2
}
}
M[w].push_back(s_index);
}
} |
c********t
发帖数: 5706 | 36 如果你觉得Pair不好用，干脆用一个hash func
比如说 key = smaller_index * num_of_sentence + bigger_index
最终结果（i,j)=( key/num_of_sentence, key%num_of_sentence)
【在 B********t 的大作中提到】
: 冷骑哥 写个代码出来吧。。我没想明白怎么update第二个map
|
K********y
发帖数: 47 | 37
优了
可是这真的是nearest neighbor问题吗？如果有两个句子完全一样，但只包含一个单词
，它们的距离为零但未必是要找的答案啊？
【在 d*s 的大作中提到】
: 把所有句子用向量表示之后可以用n-dimensional all nearest neighbohr search,
: nlgn
: 搜索过程中记录下最近的一对就可以了。总共的操作耗时O(m*n + nlgn)，应该是最优了
: http://link.springer.com/article/10.1007%2FBF02187718
: 不过我不认为普通青年可以在面试时间内把这个算法做完。。。
|
b*******o
发帖数: 8 | 38 正是。
加上长度应该可以改进， 长度等于the number of distinct words in that sentence
【在 K********y 的大作中提到】
:
: 优了
: 可是这真的是nearest neighbor问题吗？如果有两个句子完全一样，但只包含一个单词
: ，它们的距离为零但未必是要找的答案啊？
|
