f*****n
发帖数: 35 | 1 一道RF的面试题：
有N个ad, (n是million级别的)
每个ad的表示为（id, value）
比如：
121 -> new
130 -> new york
145 -> new york time square
156 -> new york department store
假设有一 query = new york department store
规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
上述例子中ad 121， 130， 156是valid的，145是invalid
问：
如何设计一个solution，使得
vector getValid(string query) （返回所有valid的ad的id）这个函
数在worst case时复杂度也能小于O(n)，面试官的说法是does not depend on N.
整个solution可以分两个阶段，第一阶段是preprocessing，这个可以是O(n)的，但是
第二阶段query阶段，也即调用函数getValid()，必须小于O(n)
我给是方案是在preprocessing阶段建立类似trie的结构，就是把trie中每个字母换成
单词，每增加一个单词，向下走一层。建树时就顺便mark每个node是否valid。query时
只要检查所有leaf node，如果valid就向上检查parent，直到invalid为止。这样
average的复杂度应该是O(logN)。但是面试官说worst case，就是每个ad都是valid时
，我的方案的复杂度还是O(N)。
大家有什么想法吗？ |
f*****n
发帖数: 35 | |
x*********w
发帖数: 533 | 3
preprocessing 就是建reverse indexing,
然后查 ”new york department store“的时候得查4次reverse indexing的集合，
每个集合遍历检查每个广告排除包含其他单词的广告， 然后union这4次的结果
【在 f*****n 的大作中提到】
: 一道RF的面试题：
: 有N个ad, (n是million级别的)
: 每个ad的表示为（id, value）
: 比如：
: 121 -> new
: 130 -> new york
: 145 -> new york time square
: 156 -> new york department store
: 假设有一 query = new york department store
: 规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
|
f*****n
发帖数: 35 | 4 你这方法就是建一个map，key是单词，value是包含这个单词的广告，这是我提出的第
一种方案，被否了。
【在 x*********w 的大作中提到】
:
: preprocessing 就是建reverse indexing,
: 然后查 ”new york department store“的时候得查4次reverse indexing的集合，
: 每个集合遍历检查每个广告排除包含其他单词的广告， 然后union这4次的结果
|
x*********w
发帖数: 533 | 5
不是符合要求吗，为啥被否呢？
【在 f*****n 的大作中提到】
: 你这方法就是建一个map，key是单词，value是包含这个单词的广告，这是我提出的第
: 一种方案，被否了。
|
b*****n
发帖数: 618 | 6 这题的要求preprocess是 O(n)， 查找是O(2^k)， 其中k为query的长度，假设query的
长度一般比较小，可以认为constant
对每个ad做hashing，每个query取所有子集的hashing查找，关键是怎么做hashing让不
同顺序但是所含单词相同的ad的hash值相同， 比如， h(new york time) = h(york
new time) |
r**h
发帖数: 1288 | 7 将一个query里面的单词按照lexicology order排序后再计算hash值
【在 b*****n 的大作中提到】
: 这题的要求preprocess是 O(n)， 查找是O(2^k)， 其中k为query的长度，假设query的
: 长度一般比较小，可以认为constant
: 对每个ad做hashing，每个query取所有子集的hashing查找，关键是怎么做hashing让不
: 同顺序但是所含单词相同的ad的hash值相同， 比如， h(new york time) = h(york
: new time)
|
u******g
发帖数: 89 | 8 这种算法如何判断145是invalid的。。
【在 x*********w 的大作中提到】
:
: 不是符合要求吗，为啥被否呢？
|
g*********s
发帖数: 150 | 9 题目中的N和n是同样的意思吗？
【在 f*****n 的大作中提到】
: 一道RF的面试题：
: 有N个ad, (n是million级别的)
: 每个ad的表示为（id, value）
: 比如：
: 121 -> new
: 130 -> new york
: 145 -> new york time square
: 156 -> new york department store
: 假设有一 query = new york department store
: 规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
|
b*****n
发帖数: 618 | 10 这个是我当时给的答案
不过面试官的意思是排序这步也可以省掉，有直接算hash的方法
【在 r**h 的大作中提到】
: 将一个query里面的单词按照lexicology order排序后再计算hash值
|
|
|
l*****e
发帖数: 3 | 11 Is it related with 'Bag of words'? How about hash trick.
wiki: Bag of words, hash trick |
x*********w
发帖数: 533 | 12
在第一轮查new的时候就排除了啊
【在 u******g 的大作中提到】
: 这种算法如何判断145是invalid的。。
|
u******g
发帖数: 89 | 13 哦你说“每个集合遍历检查每个广告排除包含其他单词的广告”。。看起来会复杂度会
更高些。。
【在 x*********w 的大作中提到】
:
: 在第一轮查new的时候就排除了啊
|
Y********f
发帖数: 410 | 14 需要加个count？ preprocess加上ad中单词的count， 对query的每个单词查询时，把
对应的ad加入hash table并记录被查询的次数，然后traverse hashtable，查询的次数
等于ad的count的ad就是。
这个和前面xiaoxiaowww的差不多，但是感觉应该会快些。
【在 f*****n 的大作中提到】
: 你这方法就是建一个map，key是单词，value是包含这个单词的广告，这是我提出的第
: 一种方案，被否了。
|
h*****n
发帖数: 15 | 15 inverted index
IR里面的经典问题 |
r**h
发帖数: 1288 | 16 请教一下，使用inverted index的话，求并集或者交集如何做到小于O(N)呢？
无论是sort之后有序查找还是使用bitmap，最坏情况下复杂度还是O(N)呀
【在 h*****n 的大作中提到】
: inverted index
: IR里面的经典问题
|
x*****0
发帖数: 452 | |
e*****n
发帖数: 316 | |
f*********1
发帖数: 75 | 19 大家看这个行不行？
由2^k 得到启发
建一个大表 每行表示一个ad， 每列表示frequent query string 的一个词，表的值表
示单词是否出现在某一个ad里。
wordcount new... york ...department ...store ... sale.
ad1 5 1 1 1 1 1
ad2 1 0 1 0 0 1
ad3 4 1 1 1 1 0
...
adn 1 1 0 0 0 0
建表需要O(N)
查询需要先生成query string的所有subsets， 这一步需要2^k, 然后与(&)query
string match对应列vector，选与值为1的ads。最后再用第一列的word count 排除包
含多余query string 单词个数的ad即得到所求的ads。
【在 f*****n 的大作中提到】
: 一道RF的面试题：
: 有N个ad, (n是million级别的)
: 每个ad的表示为（id, value）
: 比如：
: 121 -> new
: 130 -> new york
: 145 -> new york time square
: 156 -> new york department store
: 假设有一 query = new york department store
: 规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
|
y*c
发帖数: 904 | |
|
|
c********p
发帖数: 1969 | |
H****S
发帖数: 1359 | 22 做一个reversed indexing先，然后建立另外一个哈希表，键是索引，值是所含*独特*
单词数量。查找时，先用reversed indexing求得所有索引，建立一个映射关系，索引
对应索引出现次数，如果这个次数低于其对应独特单词数量，即舍弃。
【在 f*****n 的大作中提到】
: 一道RF的面试题：
: 有N个ad, (n是million级别的)
: 每个ad的表示为（id, value）
: 比如：
: 121 -> new
: 130 -> new york
: 145 -> new york time square
: 156 -> new york department store
: 假设有一 query = new york department store
: 规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
|
v********n
发帖数: 18 | 23 mark nn【在 forecan (Harry)的大作中提到：】n：一道RF的面试题：n：有N个ad, (n
是million级别的)n：每个ad的表示为（id, value）n：比如：n：121 -> newn：130 -
> new yorkn：145 -> new york time squaren……nn--n[发自未名空间Android客户端
] |
f*******b
发帖数: 520 | |
m****i
发帖数: 650 | 25 mark
【在 f*****n 的大作中提到】
: 一道RF的面试题：
: 有N个ad, (n是million级别的)
: 每个ad的表示为（id, value）
: 比如：
: 121 -> new
: 130 -> new york
: 145 -> new york time square
: 156 -> new york department store
: 假设有一 query = new york department store
: 规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
|
f*****n
发帖数: 35 | 26 一道RF的面试题：
有N个ad, (n是million级别的)
每个ad的表示为（id, value）
比如：
121 -> new
130 -> new york
145 -> new york time square
156 -> new york department store
假设有一 query = new york department store
规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
上述例子中ad 121， 130， 156是valid的，145是invalid
问：
如何设计一个solution，使得
vector getValid(string query) （返回所有valid的ad的id）这个函
数在worst case时复杂度也能小于O(n)，面试官的说法是does not depend on N.
整个solution可以分两个阶段，第一阶段是preprocessing，这个可以是O(n)的，但是
第二阶段query阶段，也即调用函数getValid()，必须小于O(n)
我给是方案是在preprocessing阶段建立类似trie的结构，就是把trie中每个字母换成
单词，每增加一个单词，向下走一层。建树时就顺便mark每个node是否valid。query时
只要检查所有leaf node，如果valid就向上检查parent，直到invalid为止。这样
average的复杂度应该是O(logN)。但是面试官说worst case，就是每个ad都是valid时
，我的方案的复杂度还是O(N)。
大家有什么想法吗？ |
f*****n
发帖数: 35 | |
x*********w
发帖数: 533 | 28
preprocessing 就是建reverse indexing,
然后查 ”new york department store“的时候得查4次reverse indexing的集合，
每个集合遍历检查每个广告排除包含其他单词的广告， 然后union这4次的结果
【在 f*****n 的大作中提到】
: 一道RF的面试题：
: 有N个ad, (n是million级别的)
: 每个ad的表示为（id, value）
: 比如：
: 121 -> new
: 130 -> new york
: 145 -> new york time square
: 156 -> new york department store
: 假设有一 query = new york department store
: 规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
|
f*****n
发帖数: 35 | 29 你这方法就是建一个map，key是单词，value是包含这个单词的广告，这是我提出的第
一种方案，被否了。
【在 x*********w 的大作中提到】
:
: preprocessing 就是建reverse indexing,
: 然后查 ”new york department store“的时候得查4次reverse indexing的集合，
: 每个集合遍历检查每个广告排除包含其他单词的广告， 然后union这4次的结果
|
x*********w
发帖数: 533 | 30
不是符合要求吗，为啥被否呢？
【在 f*****n 的大作中提到】
: 你这方法就是建一个map，key是单词，value是包含这个单词的广告，这是我提出的第
: 一种方案，被否了。
|
|
|
b*****n
发帖数: 618 | 31 这题的要求preprocess是 O(n)， 查找是O(2^k)， 其中k为query的长度，假设query的
长度一般比较小，可以认为constant
对每个ad做hashing，每个query取所有子集的hashing查找，关键是怎么做hashing让不
同顺序但是所含单词相同的ad的hash值相同， 比如， h(new york time) = h(york
new time) |
r**h
发帖数: 1288 | 32 将一个query里面的单词按照lexicology order排序后再计算hash值
【在 b*****n 的大作中提到】
: 这题的要求preprocess是 O(n)， 查找是O(2^k)， 其中k为query的长度，假设query的
: 长度一般比较小，可以认为constant
: 对每个ad做hashing，每个query取所有子集的hashing查找，关键是怎么做hashing让不
: 同顺序但是所含单词相同的ad的hash值相同， 比如， h(new york time) = h(york
: new time)
|
u******g
发帖数: 89 | 33 这种算法如何判断145是invalid的。。
【在 x*********w 的大作中提到】
:
: 不是符合要求吗，为啥被否呢？
|
g*********s
发帖数: 150 | 34 题目中的N和n是同样的意思吗？
【在 f*****n 的大作中提到】
: 一道RF的面试题：
: 有N个ad, (n是million级别的)
: 每个ad的表示为（id, value）
: 比如：
: 121 -> new
: 130 -> new york
: 145 -> new york time square
: 156 -> new york department store
: 假设有一 query = new york department store
: 规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
|
b*****n
发帖数: 618 | 35 这个是我当时给的答案
不过面试官的意思是排序这步也可以省掉，有直接算hash的方法
【在 r**h 的大作中提到】
: 将一个query里面的单词按照lexicology order排序后再计算hash值
|
l*****e
发帖数: 3 | 36 Is it related with 'Bag of words'? How about hash trick.
wiki: Bag of words, hash trick |
x*********w
发帖数: 533 | 37
在第一轮查new的时候就排除了啊
【在 u******g 的大作中提到】
: 这种算法如何判断145是invalid的。。
|
u******g
发帖数: 89 | 38 哦你说“每个集合遍历检查每个广告排除包含其他单词的广告”。。看起来会复杂度会
更高些。。
【在 x*********w 的大作中提到】
:
: 在第一轮查new的时候就排除了啊
|
Y********f
发帖数: 410 | 39 需要加个count？ preprocess加上ad中单词的count， 对query的每个单词查询时，把
对应的ad加入hash table并记录被查询的次数，然后traverse hashtable，查询的次数
等于ad的count的ad就是。
这个和前面xiaoxiaowww的差不多，但是感觉应该会快些。
【在 f*****n 的大作中提到】
: 你这方法就是建一个map，key是单词，value是包含这个单词的广告，这是我提出的第
: 一种方案，被否了。
|
h*****n
发帖数: 15 | 40 inverted index
IR里面的经典问题 |
|
|
r**h
发帖数: 1288 | 41 请教一下，使用inverted index的话，求并集或者交集如何做到小于O(N)呢？
无论是sort之后有序查找还是使用bitmap，最坏情况下复杂度还是O(N)呀
【在 h*****n 的大作中提到】
: inverted index
: IR里面的经典问题
|
x*****0
发帖数: 452 | |
e*****n
发帖数: 316 | |
f*********1
发帖数: 75 | 44 大家看这个行不行？
由2^k 得到启发
建一个大表 每行表示一个ad， 每列表示frequent query string 的一个词，表的值表
示单词是否出现在某一个ad里。
wordcount new... york ...department ...store ... sale.
ad1 5 1 1 1 1 1
ad2 1 0 1 0 0 1
ad3 4 1 1 1 1 0
...
adn 1 1 0 0 0 0
建表需要O(N)
查询需要先生成query string的所有subsets， 这一步需要2^k, 然后与(&)query
string match对应列vector，选与值为1的ads。最后再用第一列的word count 排除包
含多余query string 单词个数的ad即得到所求的ads。
【在 f*****n 的大作中提到】
: 一道RF的面试题：
: 有N个ad, (n是million级别的)
: 每个ad的表示为（id, value）
: 比如：
: 121 -> new
: 130 -> new york
: 145 -> new york time square
: 156 -> new york department store
: 假设有一 query = new york department store
: 规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
|
y*c
发帖数: 904 | |
c********p
发帖数: 1969 | |
H****S
发帖数: 1359 | 47 做一个reversed indexing先，然后建立另外一个哈希表，键是索引，值是所含*独特*
单词数量。查找时，先用reversed indexing求得所有索引，建立一个映射关系，索引
对应索引出现次数，如果这个次数低于其对应独特单词数量，即舍弃。
【在 f*****n 的大作中提到】
: 一道RF的面试题：
: 有N个ad, (n是million级别的)
: 每个ad的表示为（id, value）
: 比如：
: 121 -> new
: 130 -> new york
: 145 -> new york time square
: 156 -> new york department store
: 假设有一 query = new york department store
: 规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
|
v********n
发帖数: 18 | 48 mark nn【在 forecan (Harry)的大作中提到：】n：一道RF的面试题：n：有N个ad, (n
是million级别的)n：每个ad的表示为（id, value）n：比如：n：121 -> newn：130 -
> new yorkn：145 -> new york time squaren……nn--n[发自未名空间Android客户端
] |
f*******b
发帖数: 520 | |
m****i
发帖数: 650 | 50 mark
【在 f*****n 的大作中提到】
: 一道RF的面试题：
: 有N个ad, (n是million级别的)
: 每个ad的表示为（id, value）
: 比如：
: 121 -> new
: 130 -> new york
: 145 -> new york time square
: 156 -> new york department store
: 假设有一 query = new york department store
: 规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
|
|
|
s******e
发帖数: 128 | 51 为什么前面人说用inverted index 或 hash 什么的？
我看就是普通的trie嘛。从根往下走，记住沿路的叶子点（有flag的点）。
【在 h*****n 的大作中提到】
: inverted index
: IR里面的经典问题
|
h*d
发帖数: 19309 | 52 suffix tree?
【在 f*****n 的大作中提到】
: 一道RF的面试题：
: 有N个ad, (n是million级别的)
: 每个ad的表示为（id, value）
: 比如：
: 121 -> new
: 130 -> new york
: 145 -> new york time square
: 156 -> new york department store
: 假设有一 query = new york department store
: 规定ad中每个单词都包含在query中时，这个ad为valid （即ad是query的子集）
|
s******r
发帖数: 21 | 53 用bloom filter可能能解决这个问题。
预处理，每一个广告单词hash后建立bloom filter,例如广告130 new york对应的bloom
filter可能是
10001001
145对应的是
11011111
查询时
把query string里面的每个单词hash后建立一个bloom filter的表格，例如是
10011111
比较10001001 和10011111，可以看出广告130每个单词都极可能在query string里面出
现。
广告145不符合要求，因为第二位的bit是1，而query第二位是0 |
c*********n
发帖数: 1057 | 54 bloom filter没法满足复杂度要求吧？ |
