弱问一道G家电面题 - 未名空间MITBBS历史存档

s*u2013-02-22 08:02

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*t2013-02-22 08:02

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*22013-02-22 08:02

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*22013-02-22 08:02

4 楼

如果m个sentence，平均每个n个words
要m^2*n的复杂度吧？

s*u2013-02-22 08:02

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*t2013-02-22 08:02

6 楼

你用hashmap解吧，m^2*n
有没有可能用suffix tree 呢？

【在 p*****2 的大作中提到】

: 如果m个sentence，平均每个n个words
: 要m^2*n的复杂度吧？

p*22013-02-22 08:02

7 楼

hashset就可以了。
suffix tree怎么搞？

【在 c********t 的大作中提到】

: 你用hashmap解吧，m^2*n
: 有没有可能用suffix tree 呢？

c*t2013-02-22 08:02

8 楼

想了想，好像搞不了。排序呢？

【在 p*****2 的大作中提到】

:
: hashset就可以了。
: suffix tree怎么搞？

p*22013-02-22 08:02

9 楼

排序好像也没省时间。

【在 c********t 的大作中提到】

: 想了想，好像搞不了。排序呢？

p*22013-02-22 08:02

10 楼

LZ当时怎么答的？

c*t2013-02-22 08:02

11 楼

先每个sentence 都排序 m*nlogn
再 sentence排序 mlogm (不确定是不是这个复杂度）
再两两比较 m*n

【在 p*****2 的大作中提到】

: LZ当时怎么答的？

c*t2013-02-22 08:02

12 楼

貌似brute force了

【在 p*****2 的大作中提到】

: LZ当时怎么答的？

p*22013-02-22 08:02

13 楼

LZ不是N^2解的吗？

【在 c********t 的大作中提到】

: 貌似brute force了

s*u2013-02-22 08:02

14 楼

我直接就暴力的hashset了，但是感觉哥们要更好的方法

s*u2013-02-22 08:02

15 楼

说错了，hashmap

【在 s*******u 的大作中提到】

: 我直接就暴力的hashset了，但是感觉哥们要更好的方法

p*22013-02-22 08:02

16 楼

店面答成这样也可以了吧？感觉不容易想更好的。不知道是不是跟一些search算法相关
。

【在 s*******u 的大作中提到】

: 我直接就暴力的hashset了，但是感觉哥们要更好的方法

s*u2013-02-22 08:02

17 楼

没有，n^2m

【在 p*****2 的大作中提到】

:
: 店面答成这样也可以了吧？感觉不容易想更好的。不知道是不是跟一些search算法相关
: 。

d*s2013-02-22 08:02

18 楼

感觉跟inverted index有关，但想不出比sorting更好的算法

Y*Y2013-02-22 08:02

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*e2013-02-22 08:02

20 楼

如果长度相等，有概率方法近似算。

【在 d*s 的大作中提到】

: 感觉跟inverted index有关，但想不出比sorting更好的算法

b*u2013-02-22 08:02

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*s2013-02-22 08:02

22 楼

是的，我的想法是把单词当作维度，如果句子中出现了这个单词，就标记为1，否则为0，
那么在字典展开的空间里，相似度就是两个向量的内积。
可以用locality sensitive hashing来做clustering，求出所有相似的词组，不过似乎
这个对于严格求解最相似的一对句子帮助不大

【在 f*****e 的大作中提到】

: 如果长度相等，有概率方法近似算。

f*t2013-02-22 08:02

23 楼

这个很可能是最优解

为0，

【在 d*s 的大作中提到】

: 是的，我的想法是把单词当作维度，如果句子中出现了这个单词，就标记为1，否则为0，
: 那么在字典展开的空间里，相似度就是两个向量的内积。
: 可以用locality sensitive hashing来做clustering，求出所有相似的词组，不过似乎
: 这个对于严格求解最相似的一对句子帮助不大

f*e2013-02-22 08:02

24 楼

和我想的差不多。

为0，

【在 d*s 的大作中提到】

: 是的，我的想法是把单词当作维度，如果句子中出现了这个单词，就标记为1，否则为0，
: 那么在字典展开的空间里，相似度就是两个向量的内积。
: 可以用locality sensitive hashing来做clustering，求出所有相似的词组，不过似乎
: 这个对于严格求解最相似的一对句子帮助不大

b*u2013-02-22 08:02

25 楼

good point
如果需要两两计算内积，复杂度为n, 结果还是n×m^2
我觉得关键是避免直接比较句子和句子的相似度

为0，

【在 d*s 的大作中提到】

: 是的，我的想法是把单词当作维度，如果句子中出现了这个单词，就标记为1，否则为0，
: 那么在字典展开的空间里，相似度就是两个向量的内积。
: 可以用locality sensitive hashing来做clustering，求出所有相似的词组，不过似乎
: 这个对于严格求解最相似的一对句子帮助不大

e*s2013-02-22 08:02

26 楼

大牛，我表示没一个名词看得懂。

为0，

【在 d*s 的大作中提到】

: 是的，我的想法是把单词当作维度，如果句子中出现了这个单词，就标记为1，否则为0，
: 那么在字典展开的空间里，相似度就是两个向量的内积。
: 可以用locality sensitive hashing来做clustering，求出所有相似的词组，不过似乎
: 这个对于严格求解最相似的一对句子帮助不大

d*s2013-02-22 08:02

27 楼

把所有句子用向量表示之后可以用n-dimensional all nearest neighbohr search,
nlgn
搜索过程中记录下最近的一对就可以了。总共的操作耗时O(m*n + nlgn)，应该是最优了
http://link.springer.com/article/10.1007%2FBF02187718
不过我不认为普通青年可以在面试时间内把这个算法做完。。。

【在 f*******t 的大作中提到】

: 这个很可能是最优解
:
: 为0，

p*p2013-02-22 08:02

28 楼

对，不管怎么弄只要两两比就m^2了
或者计算minhash后排序，两两之间靠近的是最相似的，但这个应该只是近似解

【在 b*****u 的大作中提到】

: good point
: 如果需要两两计算内积，复杂度为n, 结果还是n×m^2
: 我觉得关键是避免直接比较句子和句子的相似度
:
: 为0，

c*t2013-02-22 08:02

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*u2013-02-22 08:02

30 楼

这个太狠了吧。。。作为2b青年的我表示压力很大。。

优了

【在 d*s 的大作中提到】

: 把所有句子用向量表示之后可以用n-dimensional all nearest neighbohr search,
: nlgn
: 搜索过程中记录下最近的一对就可以了。总共的操作耗时O(m*n + nlgn)，应该是最优了
: http://link.springer.com/article/10.1007%2FBF02187718
: 不过我不认为普通青年可以在面试时间内把这个算法做完。。。

j*22013-02-22 08:02

31 楼

出这么难什么意思啊？没成心招人是吗？

m*n2013-02-22 08:02

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*e2013-02-22 08:02

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*t2013-02-22 08:02

34 楼

冷骑哥写个代码出来吧。。我没想明白怎么update第二个map

【在 c********t 的大作中提到】

: 数学白痴完全不懂ls几位说的。
: 按你的思路，我给个解法吧，不用排序
: HashMap> 存有这个单词的句子序号。
: HashMap, int count> 存两句子index pair和两句的重复单词数。
: 一边扫描所有句子所有单词，对每个词，insert/update上上面两个map.
: 最后结果是第二个map里，最大count的 pair
: 复杂度 m*n*k k是每两个句子的平均重复词数。对相似度不大的很多句子，应该非常快
: 。
: 程序很好写。

t*62013-02-22 08:02

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*t2013-02-22 08:02

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*y2013-02-22 08:02

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*o2013-02-22 08:02

38 楼

正是。
加上长度应该可以改进，长度等于the number of distinct words in that sentence

【在 K********y 的大作中提到】

:
: 优了
: 可是这真的是nearest neighbor问题吗？如果有两个句子完全一样，但只包含一个单词
: ，它们的距离为零但未必是要找的答案啊？