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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 估计是悲剧了,给一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 估计是悲剧了,给一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果m个sentence,平均每个n个words : 要m^2*n的复杂度吧?
|
p*****2 发帖数: 21240 | 7
hashset就可以了。
suffix tree怎么搞?
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你用hashmap解吧,m^2*n : 有没有可能用suffix tree 呢?
|
c********t 发帖数: 5706 | 8 想了想,好像搞不了。排序呢?
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : hashset就可以了。 : suffix tree怎么搞?
|
p*****2 发帖数: 21240 | 9
排序好像也没省时间。
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 想了想,好像搞不了。排序呢?
|
p*****2 发帖数: 21240 | |
|
|
c********t 发帖数: 5706 | 11 先 每个sentence 都排序 m*nlogn
再 sentence排序 mlogm (不确定是不是这个复杂度)
再 两两比较 m*n
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : LZ当时怎么答的?
|
c********t 发帖数: 5706 | 12 貌似brute force了
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : LZ当时怎么答的?
|
p*****2 发帖数: 21240 | 13
LZ不是N^2解的吗?
【在 c********t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 貌似brute force了
|
s*******u 发帖数: 25 | 14 我直接就暴力的hashset了,但是感觉哥们要更好的方法 |
s*******u 发帖数: 25 | 15 说错了,hashmap
【在 s*******u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我直接就暴力的hashset了,但是感觉哥们要更好的方法
|
p*****2 发帖数: 21240 | 16
店面答成这样也可以了吧?感觉不容易想更好的。不知道是不是跟一些search算法相关
。
【在 s*******u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我直接就暴力的hashset了,但是感觉哥们要更好的方法
|
s*******u 发帖数: 25 | 17 没有,n^2m
【在 p*****2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 店面答成这样也可以了吧?感觉不容易想更好的。不知道是不是跟一些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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 估计是悲剧了,给一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉跟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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果长度相等,有概率方法近似算。
|
f*******t 发帖数: 7549 | 23 这个很可能是最优解
为0,
【在 d*s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是的,我的想法是把单词当作维度,如果句子中出现了这个单词,就标记为1,否则为0, : 那么在字典展开的空间里,相似度就是两个向量的内积。 : 可以用locality sensitive hashing来做clustering,求出所有相似的词组,不过似乎 : 这个对于严格求解最相似的一对句子帮助不大
|
f*****e 发帖数: 2992 | 24 和我想的差不多。
为0,
【在 d*s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是的,我的想法是把单词当作维度,如果句子中出现了这个单词,就标记为1,否则为0, : 那么在字典展开的空间里,相似度就是两个向量的内积。 : 可以用locality sensitive hashing来做clustering,求出所有相似的词组,不过似乎 : 这个对于严格求解最相似的一对句子帮助不大
|
b*****u 发帖数: 648 | 25 good point
如果需要两两计算内积,复杂度为n, 结果还是n×m^2
我觉得关键是避免直接比较句子和句子的相似度
为0,
【在 d*s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是的,我的想法是把单词当作维度,如果句子中出现了这个单词,就标记为1,否则为0, : 那么在字典展开的空间里,相似度就是两个向量的内积。 : 可以用locality sensitive hashing来做clustering,求出所有相似的词组,不过似乎 : 这个对于严格求解最相似的一对句子帮助不大
|
e***s 发帖数: 799 | 26 大牛,我表示没一个名词看得懂。
为0,
【在 d*s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是的,我的想法是把单词当作维度,如果句子中出现了这个单词,就标记为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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个很可能是最优解 : : 为0,
|
p*****p 发帖数: 379 | 28 对,不管怎么弄只要两两比就m^2了
或者计算minhash后排序,两两之间靠近的是最相似的,但这个应该只是近似解
【在 b*****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我的想法: : 所有的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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把所有句子用向量表示之后可以用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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 估计是悲剧了,给一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把所有句子用向量表示之后可以用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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 数学白痴完全不懂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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 冷骑哥 写个代码出来吧。。我没想明白怎么update第二个map
|
K********y 发帖数: 47 | 37
优了
可是这真的是nearest neighbor问题吗?如果有两个句子完全一样,但只包含一个单词
,它们的距离为零但未必是要找的答案啊?
【在 d*s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 把所有句子用向量表示之后可以用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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 优了 : 可是这真的是nearest neighbor问题吗?如果有两个句子完全一样,但只包含一个单词 : ,它们的距离为零但未必是要找的答案啊?
|