b******7
发帖数: 79 | 1 刚刚on-stie面试完某大公司。面试了7个人，大概问了20-30道题，有1道题不会，尽管
其他的都打上来了，很是郁闷，本以为自己准备的足够好了，哎。但是这道题不会，很
不甘心，希望大侠们帮助！！！
In our indexes, we have millions of URLs each of which has a link to the
page content, now, suppose a user type a query with wild cards *, which
represent 0 or multiple occcurrences of any characters, how to build the
index such that such a type of query can be executed efficiently and the
contents of all correpsonding URLs can be displayed to the users? For
example, given a query http://www.*o*ve | b******7
发帖数: 79 | 2 刚刚on-stie面试完某大公司。面试了7个人，大概问了20-30道题，有1道题不会，尽管
其他的都打上来了，很是郁闷，本以为自己准备的足够好了，哎。但是这道题不会，很
不甘心，希望大侠们帮助！！！
In our indexes, we have millions of URLs each of which has a link to the
page content, now, suppose a user type a query with wild cards *, which
represent 0 or multiple occcurrences of any characters, how to build the
index such that such a type of query can be executed efficiently and the
contents of all correpsonding URLs can be displayed to the users? For
example, given a query http://www.*o*ve | a*********7
发帖数: 30080 | 3 是不是可以先把split query into a few parts, for example, *o*ve*ou => o, ve,
ou, 然后用其中一个先query（这步可以再优化一下，比如说先用最长的一部分）；
得到的结果处理一下，比如说用ou做query，得到iloveyou.com, itveabou.com，处理
后就变成了ilovey，itveab；再用ve对处理过的结果做query。。。
是个比较笨的方法，呵呵
into
a few parts, for example, *o*ve*ou => o, ve, ou, 然后分别用o, ve, ou 查询，
但是似乎不适合这道题。 另外，如果对Index里的每一个URL建suffix tree ，然后对
每个query check againgt 所有的suffix tree, 这样实际上就是scan all urls, 明显
也不合适。但是排序？我想不出来。
【在 b******7 的大作中提到】
: 刚刚on-stie面试完某大公司。面试了7个人，大概问了20-30道题，有1道题不会，尽管
: 其他的都打上来了，很是郁闷，本以为自己准备的足够好了，哎。但是这道题不会，很
: 不甘心，希望大侠们帮助！！！
: In our indexes, we have millions of URLs each of which has a link to the
: page content, now, suppose a user type a query with wild cards *, which
: represent 0 or multiple occcurrences of any characters, how to build the
: index such that such a type of query can be executed efficiently and the
: contents of all correpsonding URLs can be displayed to the users? For
: example, given a query http://www.*o*ve
| g*******y
发帖数: 1930 | | a****n
发帖数: 1887 | 5 我估计他在问你grep 的Regular Expressions参数怎么写
million就是希望你不要都load到内存里去，（其实都load进去估计也就不超过200M）
具体你google grep Regular Expressions吧 | b******7
发帖数: 79 | 6 @asuran
我当时想了很多方法，实在不行了，我也是这么说的，能不能用grep,结果马上被嘲笑
了。
@geniusxsy, 能不能帮帮忙想想啊! 我觉得这个版里面，你算是最认真也最聪明的一个
了。其他人回答问题都不是没有你那么认真，一般都是很随便过一下脑子就写（我绝不
是说别人不好，其实只要写点我都非常感谢），只是从我看这版的经验，geniusxsy 是
最认真的一个。一般他提出的方法都比较efficient, 所以geniusxsy , 能不能在帮小
弟一把啊？真的是心理堵得慌。。。 | z*f
发帖数: 293 | | b***e
发帖数: 1419 | 8 suffix tree 是干连续的, 子序列不灵.
【在 z*f 的大作中提到】
: 为什么SUFFIX TREE 不行？
| b***e
发帖数: 1419 | 9 搞个字典树(wiki trie). 如果是查字典的话(就是没有*), 就容易了, 就一个路
径.
如果*在最后, 也容易, 就是一个路径下的sub tree.
如果任意加*, 要加强trie. 每个节点不但要指向他的下一个字符, 并且要指向
所有substring里的字符. 这相当于建立了对所有url的subsequence的trie. 这
样的话search的时间就是给定pattern的长度. | g*******y
发帖数: 1930 | 10 呵呵，你太过奖了～我不过是对做题和回帖比较积极而已，呵呵。本版也还是有很多牛
人的
这题说实话我觉得是很难的。太多的情况要考虑，而且还得有合理的一些假定条件，合适的预处理和搜索技术。。。
我现在能想到的几点是，
1.对每个URL做第一步预处理，以letter为key，存下字母出现位置。这样处理后，能保证在linear时间判断一个URL是否match一个输入(验证一个数列是否部分连续/单增)
2.接下来进一步的预处理，我猜这类题的思路应该是通过二次或者多次搜索，第一次做一个简化的搜索，大幅缩小搜索范围，第二次再在缩小的范围内继续搜索。比如搜索ab*cd*ef*gh...，第一步先搜索ab*cd，获得一个缩小的范围后再进一步的搜索。
通常第一次简化的搜索是放在在预处理里面做，相当于就是事先算好答案，到时候直接获得答案就行了。
这个思路的麻烦是，我需要有合理的一些假定，比如URL的长度大多小于某个值等等，URL出现的字母具体一定的随机分布性质（这个在实际不是很成立的），然后才能确定怎么划分第一次搜索第二次搜索。另外还有要考虑一些预处理的时间限制，允许的空间资源等等。这些都是一堆的tradeo
【在 b******7 的大作中提到】
: @asuran
: 我当时想了很多方法，实在不行了，我也是这么说的，能不能用grep,结果马上被嘲笑
: 了。
: @geniusxsy, 能不能帮帮忙想想啊! 我觉得这个版里面，你算是最认真也最聪明的一个
: 了。其他人回答问题都不是没有你那么认真，一般都是很随便过一下脑子就写（我绝不
: 是说别人不好，其实只要写点我都非常感谢），只是从我看这版的经验，geniusxsy 是
: 最认真的一个。一般他提出的方法都比较efficient, 所以geniusxsy , 能不能在帮小
: 弟一把啊？真的是心理堵得慌。。。
| | | b******7
发帖数: 79 | 11 @blaze
你的这个想法我在面试的时候，最后没招了，也说了，但是好像人家并不满意。我想主
要的缺点就是这样每个node非常的heavy,那么这个prefix tree的size有点exploded. | b******7
发帖数: 79 | 12 @geniusxsy, 对对，版上牛人是不少，可能大部分潜水（我潜水，但是我不是牛人）。
不过blaze确实也是经常提出很好的算法。Algorithmics怎么不出来了。有时候他能给
点新点子。
你的方法的思路2我很同意。就是很难找到一个合适的index organization，你的方法1
有点像给URL自己建inverted list,尽管不太一样。我记得我当时连这个也说了，好象
也不再点子上。但是你的思路2应该肯定是对的。哪位大侠救人啊！～ | b***e
发帖数: 1419 | 13 In fact, I wrote 2 posts and deleted the first one. But here was the
idea:
Build a dictionary tree with the urls, and in each node of the tree,
cache a hash table that records all the chars that appear in the sub
tree. The hash table is just the size of your alphabet. This way, if
we start to search for patterns with *, we can prune the the search
space radically, e.g., if at some nodes, we are searching for a pattern
but the hash table on the current node doesn't contain all the chars in
the
【在 b******7 的大作中提到】
: @blaze
: 你的这个想法我在面试的时候，最后没招了，也说了，但是好像人家并不满意。我想主
: 要的缺点就是这样每个node非常的heavy,那么这个prefix tree的size有点exploded.
| k***e
发帖数: 556 | 14 it seems that suffix trie did not work. if we set up suffix tree for
separated urls, we still need to check every url for match. if we combine
the urls into a big suffix tree, then it is hard to use the tree labels for
searching.
*o*ve*ou => o, ve, ou, 然后分别用o, ve, ou 查询
I don't know why you think this did not work. I think we can extend that
idea. It is infact k-gram method in the information retrieval. for example,
2-gram of google will be go, oo, og, gl, le. We preprocess all the urls to
get i
【在 b******7 的大作中提到】
: 刚刚on-stie面试完某大公司。面试了7个人，大概问了20-30道题，有1道题不会，尽管
: 其他的都打上来了，很是郁闷，本以为自己准备的足够好了，哎。但是这道题不会，很
: 不甘心，希望大侠们帮助！！！
: In our indexes, we have millions of URLs each of which has a link to the
: page content, now, suppose a user type a query with wild cards *, which
: represent 0 or multiple occcurrences of any characters, how to build the
: index such that such a type of query can be executed efficiently and the
: contents of all correpsonding URLs can be displayed to the users? For
: example, given a query http://www.*o*ve
| m*****f
发帖数: 1243 | 15 你说得对, 包括*的大范围搜索应该是一个open end question, 我觉得建trie这个
方案已经很不错了
【在 b***e 的大作中提到】
: In fact, I wrote 2 posts and deleted the first one. But here was the
: idea:
: Build a dictionary tree with the urls, and in each node of the tree,
: cache a hash table that records all the chars that appear in the sub
: tree. The hash table is just the size of your alphabet. This way, if
: we start to search for patterns with *, we can prune the the search
: space radically, e.g., if at some nodes, we are searching for a pattern
: but the hash table on the current node doesn't contain all the chars in
: the
| H*M
发帖数: 1268 | 16 I am curious.
in database, there are some matching query using "LIKE, _ %"...
for example:
select * from student
where student.name LIKE 'B_%B'
what kind of tech do they use there? isn't it very similar to this question?
【在 m*****f 的大作中提到】
: 你说得对, 包括*的大范围搜索应该是一个open end question, 我觉得建trie这个
: 方案已经很不错了
| m*****f
发帖数: 1243 | 17 student table能有多大阿
在URL里search那可是千万级别的...
question?
【在 H*M 的大作中提到】
: I am curious.
: in database, there are some matching query using "LIKE, _ %"...
: for example:
: select * from student
: where student.name LIKE 'B_%B'
: what kind of tech do they use there? isn't it very similar to this question?
| b******7
发帖数: 79 | 18 @blaze，你的树的方法有点不太适用此题，毕竟这里是URLs,不是对dictionry of
english words. 然而，从你的方法，我突然想起来我以前post的一个问题就是任意给
定几个字符，找出在字典里含有所有字符的最长的单词那道。好像你的方法（就是每个
节点存子树拥有字符）适合那个题。当时没人提出合理解法，也许你的这个解法就是那
个题的正确解？ | b******7
发帖数: 79 | 19 @blaze，你的树的方法有点不太适用此题，毕竟这里是URLs,不是对dictionry of
english words. 然而，从你的方法，我突然想起来我以前post的一个问题就是任意给
定几个字符，找出在字典里含有所有字符的最长的单词那道。好像你的方法（就是每个
节点存子树拥有字符）适合那个题。当时没人提出合理解法，也许你的这个解法就是那
个题的正确解？ | k***e
发帖数: 556 | 20 不是很明白你的解法，有如下问题：
For the first 7 chars in the url, we will do the full subsequence
construct. This way, the explosion is controlled within 2^7 = 128,
which is probably fine.
这个2^7是怎么来的啊？
对于使用trie,我的问题是如果开头就是*应该怎么匹配?
关于使用wildcard ? 来匹配一个字符,在algorithm on strings, trees and
sequences中有一个简单的使用suffix trie的算法,复杂度将是
km, k指?的数目,m是src string的长度
而本题是用*匹配,复杂度应该更高
【在 b***e 的大作中提到】
: In fact, I wrote 2 posts and deleted the first one. But here was the
: idea:
: Build a dictionary tree with the urls, and in each node of the tree,
: cache a hash table that records all the chars that appear in the sub
: tree. The hash table is just the size of your alphabet. This way, if
: we start to search for patterns with *, we can prune the the search
: space radically, e.g., if at some nodes, we are searching for a pattern
: but the hash table on the current node doesn't contain all the chars in
: the
| S******n
发帖数: 1009 | 21 此题 与 如下问题有什么区别啊？
.Wild card match:
4a: Pattern contains '?'(s)
4b: Pattern contains '*'(s)
4c: Pattern contains both;
如果只是用含有？和*的字符串与目标字符串比较应该不难啊
the
which
the
the
iloveyou.com, itveabcu.com, etc.
into
【在 b******7 的大作中提到】
: 刚刚on-stie面试完某大公司。面试了7个人，大概问了20-30道题，有1道题不会，尽管
: 其他的都打上来了，很是郁闷，本以为自己准备的足够好了，哎。但是这道题不会，很
: 不甘心，希望大侠们帮助！！！
: In our indexes, we have millions of URLs each of which has a link to the
: page content, now, suppose a user type a query with wild cards *, which
: represent 0 or multiple occcurrences of any characters, how to build the
: index such that such a type of query can be executed efficiently and the
: contents of all correpsonding URLs can be displayed to the users? For
: example, given a query http://www.*o*ve
| R*******n
发帖数: 162 | 22 to lz:
Lucene 里头有个 wildcard query 的实现， 你看看？ |
|
