k****i 发帖数: 128 | 1 给一个list of sentences, 然后找出一个pair,common words 最大。
This is a good day
This is a bad day
That was good day
return 第一个和第二个句子,因为有四个common words
这道感觉挺简单的题,竟然coding的时候凌乱了....这题感觉就是想容易写难 |
J****R 发帖数: 373 | 2 你的方法是什么?
我想的先对每个字符串按照单词排序,
然后把每行的第一个单词作为Key,行号作为list, 存在hashmap里。
对每个key对应的list 进行iterate,找到每个key对应的最长的pair的长度。
比较每个Key对应的最长的pair的长度,找到最大的。
time complex is nlgn |
x****g 发帖数: 1512 | 3 不同key但是有common words就漏了?
ABCD
BCD
AC
A=>1,3
B=>2
max其实在{1,2} ?
【在 J****R 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的方法是什么? : 我想的先对每个字符串按照单词排序, : 然后把每行的第一个单词作为Key,行号作为list, 存在hashmap里。 : 对每个key对应的list 进行iterate,找到每个key对应的最长的pair的长度。 : 比较每个Key对应的最长的pair的长度,找到最大的。 : time complex is nlgn
|
c*****m 发帖数: 315 | 4 这个是不是只管common words,不考虑单词顺序的? |
k****i 发帖数: 128 | 5 对啊,例子里已经给了, 单词排序+句子前缀排序就行了,就是coding有点难
【在 c*****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个是不是只管common words,不考虑单词顺序的?
|
b****f 发帖数: 138 | |
x****g 发帖数: 1512 | 7 感觉做一遍预处理更有效?
string->id
每个就变成id sequence,去重
不用没完没了比字符串
每个sequce排序之后,common words就是两个sequence的交集。
所有sequence按长度排序,完了从大往小扫,也许可以提前退出。
但最差还得o(N^2)
有优算法吗?
【在 k****i 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 对啊,例子里已经给了, 单词排序+句子前缀排序就行了,就是coding有点难
|
t*********h 发帖数: 941 | 8 bitvector?
【在 x****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉做一遍预处理更有效? : string->id : 每个就变成id sequence,去重 : 不用没完没了比字符串 : 每个sequce排序之后,common words就是两个sequence的交集。 : 所有sequence按长度排序,完了从大往小扫,也许可以提前退出。 : 但最差还得o(N^2) : 有优算法吗?
|
g*****g 发帖数: 34805 | 9 我提个思路,先对所有句子标号,然后作个 reverse indexing, 单词指向所有有这个
单词的句子。
然后设一个N*(N-1)/2大的数组,用来存放match的次数。把单词指向的句子之间两两
match + 1, 同时维护一个最高的count和相关的两个句子就行。假如用的单词很多,大
多数单词只出现在少数的句子里,性能逼近O(N) |
x****g 发帖数: 1512 | 10 这个假设不太成立?
所有句子都含有单词a,其它任意。只会比o(N^2)更差?
如果句子来自文章或者网络啥的。很容易都含有a,an,is,the...等等。
【在 g*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我提个思路,先对所有句子标号,然后作个 reverse indexing, 单词指向所有有这个 : 单词的句子。 : 然后设一个N*(N-1)/2大的数组,用来存放match的次数。把单词指向的句子之间两两 : match + 1, 同时维护一个最高的count和相关的两个句子就行。假如用的单词很多,大 : 多数单词只出现在少数的句子里,性能逼近O(N)
|
|
|
d******n 发帖数: 22 | 11 楼主能否把解法说清楚的,不要惜字啊,
就一两句话我等菜鸟完全看不懂啊 |
g*****g 发帖数: 212 | 12 正解。
两两句子比较 也就是O(N^2*M)
M为sentence的最大单词长度。
这个方法,worse.
我怀疑,要么面试官只想考查coding的quality
要么lz倒霉了,面试官觉得有更优解法,实际可能没有。
【在 x****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个假设不太成立? : 所有句子都含有单词a,其它任意。只会比o(N^2)更差? : 如果句子来自文章或者网络啥的。很容易都含有a,an,is,the...等等。
|
M*********n 发帖数: 4839 | |
g*****g 发帖数: 212 | 14 匹配是无序的,前缀树和后缀树都没用
【在 M*********n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 类似与trie?如果每个单词是一个节点的话?
|
m********m 发帖数: 10 | 15 不知道这思路对不对,各位大牛指教。
1. create a map with word as key and a number as value
2. walk through each sentence and extract word
- if a word does not exist in map, assign a unique number and insert <
word, number> into the map
take "This is a good day" as example, you could have map end up like
"This", 0
"is", 1
"a", 2
"good", 3
"day", 4
- create a bit vector, and for each word in sentence, enable ith bit
which i == word number
so for "This is a good day", bit vector will be 0x1f.
3. perform OR for bit vectors in every two sentences. number of bits set to
1 is the number of common words |
t*****i 发帖数: 10 | 16 看不懂,有code么
like
【在 m********m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不知道这思路对不对,各位大牛指教。 : 1. create a map with word as key and a number as value : 2. walk through each sentence and extract word : - if a word does not exist in map, assign a unique number and insert < : word, number> into the map : take "This is a good day" as example, you could have map end up like : "This", 0 : "is", 1 : "a", 2 : "good", 3
|
m********c 发帖数: 105 | 17 用bit operation比较两个sentence中的common words,这个思路很赞啊。
我觉得必须要两两比较sentences,time complexity最好也是O(n^2),n是# sentences
like
【在 m********m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不知道这思路对不对,各位大牛指教。 : 1. create a map with word as key and a number as value : 2. walk through each sentence and extract word : - if a word does not exist in map, assign a unique number and insert < : word, number> into the map : take "This is a good day" as example, you could have map end up like : "This", 0 : "is", 1 : "a", 2 : "good", 3
|
x****g 发帖数: 1512 | 18 用bit vector其实意义不大。
把数字序列变成bit vector本身就是o(k 单子平均长度),
而且因为bit vector长度为所有unique单词个数/8
(这个会随着#sentences个数增长,而不是单词平均长度,所以不好。)
s1编号为1,1000000000
s2变好为2.
做OR运算其实有大量无用功发生。完事了你还得统计bit==1的位数...
在做两两比较o(N^2)的目标前提下,你已经有id sequence.
那么简单了事无非就是计算
#1 => #2...#n
#2 => #3...#n
所以你只要对当前的#i建hashset或者dic都行o(#i)单词个数
对于每一个#i+1....#n,无非就是查表计数。o(#s)
最后为o(N^2*k)其中k为单词平均长度。
sentences
【在 m********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用bit operation比较两个sentence中的common words,这个思路很赞啊。 : 我觉得必须要两两比较sentences,time complexity最好也是O(n^2),n是# sentences : : like
|
m********c 发帖数: 105 | 19 不明白为什么最后是O(N^2*k) 而不是O(N^2*m) (m是# words in a sentences).
【在 x****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用bit vector其实意义不大。 : 把数字序列变成bit vector本身就是o(k 单子平均长度), : 而且因为bit vector长度为所有unique单词个数/8 : (这个会随着#sentences个数增长,而不是单词平均长度,所以不好。) : s1编号为1,1000000000 : s2变好为2. : 做OR运算其实有大量无用功发生。完事了你还得统计bit==1的位数... : 在做两两比较o(N^2)的目标前提下,你已经有id sequence. : 那么简单了事无非就是计算 : #1 => #2...#n
|
x****g 发帖数: 1512 | 20 k我其实是指平均单词个数。就是你的avg(m)
我觉得这道题,其实是文档相似度的一个简化版本。
如果要求100%准确的话,比较难优化。
目的应该是搞这个路子非100%的
http://blog.csdn.net/beta2/article/details/5014530
【在 m********c 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不明白为什么最后是O(N^2*k) 而不是O(N^2*m) (m是# words in a sentences).
|
|
|
g*****g 发帖数: 34805 | 21 前面O(kN)的索引时间就可以计算出词频。就像你说的,有些单词频率很高,可以分而
治之。
频率高的还用简单的比较,频率不高的则是O(m^2N),其中m是不常见词汇平均出现的次
数。
对于N很大,k也很大的应用。比如搜索引擎比较所有的网页。m^2远小于N。所以整体的
复杂度就是
O(k’N^2) + O(m^2N), k' 是个常数,比如10个常用的a, the, I等。要比O(kN^2)好,
后者的k可能有1000。
【在 x****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个假设不太成立? : 所有句子都含有单词a,其它任意。只会比o(N^2)更差? : 如果句子来自文章或者网络啥的。很容易都含有a,an,is,the...等等。
|
x****g 发帖数: 1512 | 22 又看了看,感觉没想通,呵呵。
N^2是由于两两比较引起的。
你按词索引能减少比较的对象就是那种毫无关系的,说白的就是common为0的。
这个和具体每个词是否高频或者低频无关。
只要有1个公共的,他俩就得比一次。其它再公共也不用比,比过了就完事。
所以没想明白和频率有啥关系,还是我没看懂你的思路?
解释一下,谢谢。
【在 g*****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 前面O(kN)的索引时间就可以计算出词频。就像你说的,有些单词频率很高,可以分而 : 治之。 : 频率高的还用简单的比较,频率不高的则是O(m^2N),其中m是不常见词汇平均出现的次 : 数。 : 对于N很大,k也很大的应用。比如搜索引擎比较所有的网页。m^2远小于N。所以整体的 : 复杂度就是 : O(k’N^2) + O(m^2N), k' 是个常数,比如10个常用的a, the, I等。要比O(kN^2)好, : 后者的k可能有1000。
|
g*****g 发帖数: 34805 | 23 举个极端的例子,所有单词都只在所有句子里一共出现两次。所以每个单词都指向两个
句子。
起一个N*N 的二维数组,把单词指向的匹配都加1,一个单词只用做一次。所有整个开
销就是所有不同单词的数目,这个还不如前面建立reverse index的cost大。
【在 x****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 又看了看,感觉没想通,呵呵。 : N^2是由于两两比较引起的。 : 你按词索引能减少比较的对象就是那种毫无关系的,说白的就是common为0的。 : 这个和具体每个词是否高频或者低频无关。 : 只要有1个公共的,他俩就得比一次。其它再公共也不用比,比过了就完事。 : 所以没想明白和频率有啥关系,还是我没看懂你的思路? : 解释一下,谢谢。
|
k****i 发帖数: 128 | |
t**********r 发帖数: 2153 | 25 reverse index
【在 k****i 的大作中提到】![](/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 : 这道感觉挺简单的题,竟然coding的时候凌乱了....这题感觉就是想容易写难
|
k****r 发帖数: 807 | 26 这个brute force是不是太笨了?///
pair, vector> max_common_words(vector>
sentences) {
unordered_map> string_map;
unordered_map, int, hashPair> pair_map; // pair, count
pair, vector> res;
for (int i = 0; i < sentences.size(); i++) {
for (int j = 0; j < sentences[i].size(); j++) {
string_map[sentences[i][j]].push_back(i);
}
}
for (auto& it : string_map) {
for (int i = 0; i < it.second.size(); i++) {
for (int j = i + 1; j < it.second.size(); j++) {
auto p = make_pair(it.second[i], it.second[j]);
pair_map[p]++;
}
}
}
int count = 0;
for (auto& it : pair_map) {
if (it.second > count) {
count = it.second;
res =
make_pair(sentences[it.first.first], sentences[it.first.second]);
}
}
return res;
} |
g*******g 发帖数: 11 | 27 提个解法, 不知道是否好?
1. 先个每个句子编个号:
This is a good day --- # 1
This is a bad day --- # 2
That was good day --- # 3
2. 从第一个句子开始, 给每个新单词做个链表或动态数组之类并加上句子编号, 如果
是旧单词直接加句子编号, 如下:
This->1->2
is->1->2
a->1->2
good->1->3
day->1->2->3
bad->2
That->3
was->3
3. 建立一个小数组, 分别记录出现的频率:
freq[0] ---- 代表#1-#2共同的单词的次数
freq[1] ---- 代表#1-#3共同的单词的次数
freq[2] ---- 代表#2-#3共同的单词的次数
4. 先赋所有freq为0
5. 扫描所有单词链条中出现同单词次数, 得到结果:
freq[0] = 4
freq[1] = 2
freq[2] = 1 |
m*****k 发帖数: 731 | 28 s1: e f
s2: d e f
s3: a b c e
"也许可以提前退出", how?
【在 x****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉做一遍预处理更有效? : string->id : 每个就变成id sequence,去重 : 不用没完没了比字符串 : 每个sequce排序之后,common words就是两个sequence的交集。 : 所有sequence按长度排序,完了从大往小扫,也许可以提前退出。 : 但最差还得o(N^2) : 有优算法吗?
|