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 的大作中提到】
: 你的方法是什么？
: 我想的先对每个字符串按照单词排序，
: 然后把每行的第一个单词作为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 的大作中提到】
: 这个是不是只管common words，不考虑单词顺序的？
|
b****f
发帖数: 138 | |
x****g
发帖数: 1512 | 7 感觉做一遍预处理更有效？
string->id
每个就变成id sequence，去重
不用没完没了比字符串
每个sequce排序之后，common words就是两个sequence的交集。
所有sequence按长度排序，完了从大往小扫，也许可以提前退出。
但最差还得o(N^2)
有优算法吗?
【在 k****i 的大作中提到】
: 对啊，例子里已经给了， 单词排序＋句子前缀排序就行了，就是coding有点难
|
t*********h
发帖数: 941 | 8 bitvector?
【在 x****g 的大作中提到】
: 感觉做一遍预处理更有效？
: 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 的大作中提到】
: 我提个思路，先对所有句子标号，然后作个 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 的大作中提到】
: 这个假设不太成立？
: 所有句子都含有单词a,其它任意。只会比o(N^2)更差？
: 如果句子来自文章或者网络啥的。很容易都含有a,an,is,the...等等。
|
M*********n
发帖数: 4839 | |
g*****g
发帖数: 212 | 14 匹配是无序的，前缀树和后缀树都没用
【在 M*********n 的大作中提到】
: 类似与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 的大作中提到】
: 不知道这思路对不对，各位大牛指教。
: 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 的大作中提到】
: 不知道这思路对不对，各位大牛指教。
: 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 的大作中提到】
: 用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 的大作中提到】
: 用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 的大作中提到】
: 不明白为什么最后是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 的大作中提到】
: 这个假设不太成立？
: 所有句子都含有单词a,其它任意。只会比o(N^2)更差？
: 如果句子来自文章或者网络啥的。很容易都含有a,an,is,the...等等。
|
x****g
发帖数: 1512 | 22 又看了看，感觉没想通，呵呵。
N^2是由于两两比较引起的。
你按词索引能减少比较的对象就是那种毫无关系的，说白的就是common为0的。
这个和具体每个词是否高频或者低频无关。
只要有1个公共的，他俩就得比一次。其它再公共也不用比，比过了就完事。
所以没想明白和频率有啥关系，还是我没看懂你的思路？
解释一下，谢谢。
【在 g*****g 的大作中提到】
: 前面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 的大作中提到】
: 又看了看，感觉没想通，呵呵。
: N^2是由于两两比较引起的。
: 你按词索引能减少比较的对象就是那种毫无关系的，说白的就是common为0的。
: 这个和具体每个词是否高频或者低频无关。
: 只要有1个公共的，他俩就得比一次。其它再公共也不用比，比过了就完事。
: 所以没想明白和频率有啥关系，还是我没看懂你的思路？
: 解释一下，谢谢。
|
k****i
发帖数: 128 | |
t**********r
发帖数: 2153 | 25 reverse index
【在 k****i 的大作中提到】
: 给一个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 的大作中提到】
: 感觉做一遍预处理更有效？
: string->id
: 每个就变成id sequence，去重
: 不用没完没了比字符串
: 每个sequce排序之后，common words就是两个sequence的交集。
: 所有sequence按长度排序，完了从大往小扫，也许可以提前退出。
: 但最差还得o(N^2)
: 有优算法吗?
|
