w***y 发帖数: 6251 | 1 -a query has m words
-n documents
how to find documents that contains at least p (p
讲出算法并implement
我知道是一个简易版的document selection, 但是不知道选什么data structure/code
怎么写。
production里面用heap做的,面试写起来不容易啊, 而且我还不知道java 内置的那个
priorityqueue实现的heap, 怎么对element做cnt++的运算//囧 |
k*******r 发帖数: 355 | 2 难道不是用inverted indexing做? |
w***y 发帖数: 6251 | 3 是这个思路, 但是不知道面试的时候具体怎么写code啊
好比inverted index这个 word 到docID的map 怎么实现; 每个docID 包含word个数的
count存、怎么increase.........
答用两个hashtable做的同学已经fail了, 囧
【在 k*******r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 难道不是用inverted indexing做?
|
b*****g 发帖数: 983 | 4 heap
code
【在 w***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : -a query has m words : -n documents : how to find documents that contains at least p (p: 讲出算法并implement : 我知道是一个简易版的document selection, 但是不知道选什么data structure/code : 怎么写。 : production里面用heap做的,面试写起来不容易啊, 而且我还不知道java 内置的那个 : priorityqueue实现的heap, 怎么对element做cnt++的运算//囧
|
b********e 发帖数: 386 | 5 This is hard problem for people who do not have search related experiences.
for basics, you need to know how a compiled query goes through an inverted
index.
which may take long paragraph to explain.
code
【在 w***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : -a query has m words : -n documents : how to find documents that contains at least p (p: 讲出算法并implement : 我知道是一个简易版的document selection, 但是不知道选什么data structure/code : 怎么写。 : production里面用heap做的,面试写起来不容易啊, 而且我还不知道java 内置的那个 : priorityqueue实现的heap, 怎么对element做cnt++的运算//囧
|
l*****a 发帖数: 14598 | 6 你是希望找到一组document, 其中每个都包含at least p words
还是说找到document的组合,使得每个组合含at least p words
code
【在 w***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : -a query has m words : -n documents : how to find documents that contains at least p (p: 讲出算法并implement : 我知道是一个简易版的document selection, 但是不知道选什么data structure/code : 怎么写。 : production里面用heap做的,面试写起来不容易啊, 而且我还不知道java 内置的那个 : priorityqueue实现的heap, 怎么对element做cnt++的运算//囧
|
w***y 发帖数: 6251 | 7 今天onsite被问了这个,囧了个囧
我没做出最优解, 不过把题目搞清触了
“希望找到一组document, 其中每个都包含at least p words”
问题的最后的关键是, 假定由w1... wq 组成的query涉及k个documents, 用什么样的
data structure或者strategy去计数, 能用少于k的space -- 所以即使用heap,也还
是不行, 因为heap还是需要k个node
人家提示可以用extra computation, 但是我还是没有idea, compute什么样的数据出来
, 可以节省空间
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你是希望找到一组document, 其中每个都包含at least p words : 还是说找到document的组合,使得每个组合含at least p words : : code
|
j***u 发帖数: 16 | 8 如果按inverted index方法
DocID_1 = { word1,word2,word3}
DocID_2 = { word2,word3}
DocID_3 = { word1,word3,word4}
那么,Hash链表
H(word1)-->DocID_1-->DocID_3
H(word2)-->DocID_1-->DocID_2
H(word3)-->DocID_1-->DocID_2-->DocID_3
如查询 word1+word2, 就是求每个word的hash链的交集 {DocID_1}
就变成求所有查询word的hash链的交集.
如果是这样的话,问题可以先简化找2个链表的重复数据,
然后根据得到的重复数据集合,和下一个链表比较 找交集 |
w***y 发帖数: 6251 | 9 我想这个思路应该是正确的, 因为当时面试的人也提示我考虑p=1 (union) 或者p=m
(intersection) 的情况
但是我想不明白,如果 p 介于1~m之间, 怎么做。。。。。
【在 j***u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 如果按inverted index方法 : DocID_1 = { word1,word2,word3} : DocID_2 = { word2,word3} : DocID_3 = { word1,word3,word4} : 那么,Hash链表 : H(word1)-->DocID_1-->DocID_3 : H(word2)-->DocID_1-->DocID_2 : H(word3)-->DocID_1-->DocID_2-->DocID_3 : 如查询 word1+word2, 就是求每个word的hash链的交集 {DocID_1} : 就变成求所有查询word的hash链的交集.
|
w****x 发帖数: 2483 | 10 倒排索引, 要先做预处理.
然后用一个map, map的pair是<文件号, 出现几个词>
1. 遍历一便句子的每一个不重复的词, 把这个词对应的文件号key的value加1.
2. 便利map, 找出频率>=p的文件 |
w****m 发帖数: 146 | 11 你这个就是forward index啊,和inverted index有什么关系
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 倒排索引, 要先做预处理. : 然后用一个map, map的pair是<文件号, 出现几个词> : 1. 遍历一便句子的每一个不重复的词, 把这个词对应的文件号key的value加1. : 2. 便利map, 找出频率>=p的文件
|
j***u 发帖数: 16 | 12 就是
i.e. m = 3 = word1 + word2 + word3,
1>先求 union(m) = H(word1) + H(word2) + H(word3) 链表里所以doc_id 数目(有重
复)
这个union 包括 同时有3个word的doc_id, 也有只有1个或2个 的doc_id,
2>求交集 intersect(p = m) = H(word1) 交 H(word2) 交 H(word3), 得到的 集合就是
同时含有3个word的doc_id 数目,
3>结果 sum (p < m) = union(m) - 3 * intersect( p = m) (去掉所有 同时含3个
word的doc_id) |
j****a 发帖数: 1277 | 13 这个怎么做啊 如果p是m的subset 那我觉得挺难的 有2^n subsets
code
【在 w***y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : -a query has m words : -n documents : how to find documents that contains at least p (p: 讲出算法并implement : 我知道是一个简易版的document selection, 但是不知道选什么data structure/code : 怎么写。 : production里面用heap做的,面试写起来不容易啊, 而且我还不知道java 内置的那个 : priorityqueue实现的heap, 怎么对element做cnt++的运算//囧
|