f********e
发帖数: 100 | 1 版上最新的：
给一个dictionary，然后可以support的query是，给一个string，返回在
dictionary里面包含给定string的所有character的最短的string
我能想到的是把query变成sorted hash table. dictionary的words也都变成sorted
hash table, 放在象trie一样的结构里。这样query来时可以filter字典里哪些词会
contain query.然后就得把这些candidates 都把min window算一遍。
但这样的话如果candidates多了，很贵。。。 |
n******n
发帖数: 12088 | 2 这不是和找所有anagram类似吗？建一个新字典。
【在 f********e 的大作中提到】
: 版上最新的：
: 给一个dictionary，然后可以support的query是，给一个string，返回在
: dictionary里面包含给定string的所有character的最短的string
: 我能想到的是把query变成sorted hash table. dictionary的words也都变成sorted
: hash table, 放在象trie一样的结构里。这样query来时可以filter字典里哪些词会
: contain query.然后就得把这些candidates 都把min window算一遍。
: 但这样的话如果candidates多了，很贵。。。
|
f********e
发帖数: 100 | 3 新字典，what are the keys and values?
【在 n******n 的大作中提到】
: 这不是和找所有anagram类似吗？建一个新字典。
|
n******n
发帖数: 12088 | 4 anagram你怎么做？类似
【在 f********e 的大作中提到】
: 新字典，what are the keys and values?
|
b*****n
发帖数: 618 | 5 用类似的方法可能会有问题，
你怎么样来表示整个字典？
另外query的时候怎么做？
【在 n******n 的大作中提到】
: anagram你怎么做？类似
|
l*****a
发帖数: 14598 | 6 巨牛这题对你来说是小菜吧？
不就是Map>吗
key就是每个词对应的character set.
List按照从短到长顺序保存，每次插入相应位置吧
query就是O(1)
【在 b*****n 的大作中提到】
: 用类似的方法可能会有问题，
: 你怎么样来表示整个字典？
: 另外query的时候怎么做？
|
n******n
发帖数: 12088 | 7 而且也不用保存所有，保持当前看到最短串集合就可以。
【在 l*****a 的大作中提到】
: 巨牛这题对你来说是小菜吧？
: 不就是Map>吗
: key就是每个词对应的character set.
: List按照从短到长顺序保存，每次插入相应位置吧
: query就是O(1)
|
b*****n
发帖数: 618 | 8 大牛您笑话我了
看来这个题目我没说清楚。。。
包含不是相同的意思，比如dict＝["abc", "abde"]
如果query是“ab”的话，应该返回"abc"
【在 l*****a 的大作中提到】
: 巨牛这题对你来说是小菜吧？
: 不就是Map>吗
: key就是每个词对应的character set.
: List按照从短到长顺序保存，每次插入相应位置吧
: query就是O(1)
|
A*******e
发帖数: 2419 | 9 什么是sorted hash table？hash table只能是unsorted.
【在 f********e 的大作中提到】
: 版上最新的：
: 给一个dictionary，然后可以support的query是，给一个string，返回在
: dictionary里面包含给定string的所有character的最短的string
: 我能想到的是把query变成sorted hash table. dictionary的words也都变成sorted
: hash table, 放在象trie一样的结构里。这样query来时可以filter字典里哪些词会
: contain query.然后就得把这些candidates 都把min window算一遍。
: 但这样的话如果candidates多了，很贵。。。
|
A*******e
发帖数: 2419 | 10 如果query里有重复字符怎么算？
比如字典{"abc", "bbcc"}，查询"bcc"，该返回哪个？
【在 b*****n 的大作中提到】
: 大牛您笑话我了
: 看来这个题目我没说清楚。。。
: 包含不是相同的意思，比如dict＝["abc", "abde"]
: 如果query是“ab”的话，应该返回"abc"
|
|
|
A*******e
发帖数: 2419 | 11 另外query的字符串不一定在字典里？那会麻烦不少啊。
【在 A*******e 的大作中提到】
: 如果query里有重复字符怎么算？
: 比如字典{"abc", "bbcc"}，查询"bcc"，该返回哪个？
|
b*****n
发帖数: 618 | 12 这个可以看作两个不同题目，
可以不考虑每个distinct character的数量，也可以考虑每个dictinct character的数
量。
但是我想解法应该差不太多。。
【在 A*******e 的大作中提到】
: 如果query里有重复字符怎么算？
: 比如字典{"abc", "bbcc"}，查询"bcc"，该返回哪个？
|
b*****n
发帖数: 618 | 13 是的，query字符串并不一定在字典里，是任意的。
【在 A*******e 的大作中提到】
: 另外query的字符串不一定在字典里？那会麻烦不少啊。
|
A*******e
发帖数: 2419 | 14 我感觉考虑字符个数的话会麻烦一些，没细想。
如果不考虑重复，只是覆盖“所有不同字符”，那就先把所有单词按长度排序，然后遍
历排序的单词，建反向索引：
a
b
...
ab
ac
...
abc
abd
...
比如第一个处理过后的单词是abc，那么f("a"), f("b"), f("c")，f("ab")等等都返回
"abc"。一旦某个索引被设置，以后就不用考虑这个组合。比如第二个单词是"abcd"的
话，只会生成"ad", "bd"，等等。
另外每个字符串映射成26-bit的整数，索引表大小是2^26，32M*4 = 128M字节，每个查
询都是O(1)。
【在 b*****n 的大作中提到】
: 是的，query字符串并不一定在字典里，是任意的。
|
b*****n
发帖数: 618 | 15 我觉得这样可以，基本思路也差不多，就是做inverted index
【在 A*******e 的大作中提到】
: 我感觉考虑字符个数的话会麻烦一些，没细想。
: 如果不考虑重复，只是覆盖“所有不同字符”，那就先把所有单词按长度排序，然后遍
: 历排序的单词，建反向索引：
: a
: b
: ...
: ab
: ac
: ...
: abc
|
b*******d
发帖数: 750 | 16
帅哥，是字母字符集吗？
如果是的话，一共只有2^26个可能的query，pre-processing个查询表，可以避免
inverted index。
【在 b*****n 的大作中提到】
: 大牛您笑话我了
: 看来这个题目我没说清楚。。。
: 包含不是相同的意思，比如dict＝["abc", "abde"]
: 如果query是“ab”的话，应该返回"abc"
|
b*****n
发帖数: 618 | 17 美女，你这个和上一个帖子的解法有区别吗？
另外关键你的preoprocess的cost是多少
【在 b*******d 的大作中提到】
:
: 帅哥，是字母字符集吗？
: 如果是的话，一共只有2^26个可能的query，pre-processing个查询表，可以避免
: inverted index。
|
y******s
发帖数: 92 | 18 s1按照char排序，得到说s2，然后把s1存入s2的trie的位置中。当query(s3)的时候，
先把s3按照char排序，然后进入trie查找。需要注意的一种情况：比如s3排序后为"aab
....",查找完aa，之后，要同时进入'a'和‘b'子node查找。 |
b*******d
发帖数: 750 | 19
o。。。。
完全没有看到前文。。。
i guess nobody cares pre-process的cost...
【在 b*****n 的大作中提到】
: 美女，你这个和上一个帖子的解法有区别吗？
: 另外关键你的preoprocess的cost是多少
|
b*****n
发帖数: 618 | 20 面试官care。。。
如果是incremental build这个dictionary还好。
另外，这是个open ended question，这个solution在一般情况下是可以的
不过如果给的corpus情况不一样就可能会有麻烦，不管是在index的size上还是process
的cost上。但是我觉得不管怎么样都是inverted index吧，只是只存最短的一个而已。
【在 b*******d 的大作中提到】
:
: o。。。。
: 完全没有看到前文。。。
: i guess nobody cares pre-process的cost...
|
b*******d
发帖数: 750 | 21
process
唉。。。可能离开google太早了。。现在一切都变了。。。
【在 b*****n 的大作中提到】
: 面试官care。。。
: 如果是incremental build这个dictionary还好。
: 另外，这是个open ended question，这个solution在一般情况下是可以的
: 不过如果给的corpus情况不一样就可能会有麻烦，不管是在index的size上还是process
: 的cost上。但是我觉得不管怎么样都是inverted index吧，只是只存最短的一个而已。
|
b*****n
发帖数: 618 | 22 求指教狗家变的咋了？跟以前有什么不同？
【在 b*******d 的大作中提到】
:
: process
: 唉。。。可能离开google太早了。。现在一切都变了。。。
|
