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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 版上最新的: : 给一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这不是和找所有anagram类似吗?建一个新字典。
|
n******n 发帖数: 12088 | 4 anagram你怎么做?类似
【在 f********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 新字典,what are the keys and values?
|
b*****n 发帖数: 618 | 5 用类似的方法可能会有问题,
你怎么样来表示整个字典?
另外query的时候怎么做?
【在 n******n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : anagram你怎么做?类似
|
l*****a 发帖数: 14598 | 6 巨牛这题对你来说是小菜吧?
不就是Map>吗
key就是每个词对应的character set.
List按照从短到长顺序保存,每次插入相应位置吧
query就是O(1)
【在 b*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用类似的方法可能会有问题, : 你怎么样来表示整个字典? : 另外query的时候怎么做?
|
n******n 发帖数: 12088 | 7 而且也不用保存所有,保持当前看到最短串集合就可以。
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 巨牛这题对你来说是小菜吧? : 不就是Map>吗 : key就是每个词对应的character set. : List按照从短到长顺序保存,每次插入相应位置吧 : query就是O(1)
|
b*****n 发帖数: 618 | 8 大牛您笑话我了
看来这个题目我没说清楚。。。
包含不是相同的意思,比如dict=["abc", "abde"]
如果query是“ab”的话,应该返回"abc"
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 巨牛这题对你来说是小菜吧? : 不就是Map>吗 : key就是每个词对应的character set. : List按照从短到长顺序保存,每次插入相应位置吧 : query就是O(1)
|
|
A*******e 发帖数: 2419 | 9 什么是sorted hash table?hash table只能是unsorted.
【在 f********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 版上最新的: : 给一个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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大牛您笑话我了 : 看来这个题目我没说清楚。。。 : 包含不是相同的意思,比如dict=["abc", "abde"] : 如果query是“ab”的话,应该返回"abc"
|
|
|
A*******e 发帖数: 2419 | 11 另外query的字符串不一定在字典里?那会麻烦不少啊。
【在 A*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果query里有重复字符怎么算? : 比如字典{"abc", "bbcc"},查询"bcc",该返回哪个?
|
b*****n 发帖数: 618 | 12 这个可以看作两个不同题目,
可以不考虑每个distinct character的数量,也可以考虑每个dictinct character的数
量。
但是我想解法应该差不太多。。
【在 A*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果query里有重复字符怎么算? : 比如字典{"abc", "bbcc"},查询"bcc",该返回哪个?
|
b*****n 发帖数: 618 | 13 是的,query字符串并不一定在字典里,是任意的。
【在 A*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 另外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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 是的,query字符串并不一定在字典里,是任意的。
|
b*****n 发帖数: 618 | 15 我觉得这样可以,基本思路也差不多,就是做inverted index
【在 A*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我感觉考虑字符个数的话会麻烦一些,没细想。 : 如果不考虑重复,只是覆盖“所有不同字符”,那就先把所有单词按长度排序,然后遍 : 历排序的单词,建反向索引: : a : b : ... : ab : ac : ... : abc
|
b*******d 发帖数: 750 | 16
帅哥,是字母字符集吗?
如果是的话,一共只有2^26个可能的query,pre-processing个查询表,可以避免
inverted index。
【在 b*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 大牛您笑话我了 : 看来这个题目我没说清楚。。。 : 包含不是相同的意思,比如dict=["abc", "abde"] : 如果query是“ab”的话,应该返回"abc"
|
b*****n 发帖数: 618 | 17 美女,你这个和上一个帖子的解法有区别吗?
另外关键你的preoprocess的cost是多少
【在 b*******d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 帅哥,是字母字符集吗? : 如果是的话,一共只有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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 美女,你这个和上一个帖子的解法有区别吗? : 另外关键你的preoprocess的cost是多少
|
b*****n 发帖数: 618 | 20 面试官care。。。
如果是incremental build这个dictionary还好。
另外,这是个open ended question,这个solution在一般情况下是可以的
不过如果给的corpus情况不一样就可能会有麻烦,不管是在index的size上还是process
的cost上。但是我觉得不管怎么样都是inverted index吧,只是只存最短的一个而已。
【在 b*******d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : o。。。。 : 完全没有看到前文。。。 : i guess nobody cares pre-process的cost...
|
b*******d 发帖数: 750 | 21
process
唉。。。可能离开google太早了。。现在一切都变了。。。
【在 b*****n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 面试官care。。。 : 如果是incremental build这个dictionary还好。 : 另外,这是个open ended question,这个solution在一般情况下是可以的 : 不过如果给的corpus情况不一样就可能会有麻烦,不管是在index的size上还是process : 的cost上。但是我觉得不管怎么样都是inverted index吧,只是只存最短的一个而已。
|
b*****n 发帖数: 618 | 22 求指教狗家变的咋了?跟以前有什么不同?
【在 b*******d 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : process : 唉。。。可能离开google太早了。。现在一切都变了。。。
|