mastercard 可以在walmart ATM load 蓝鸟吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

mastercard 可以在walmart ATM load 蓝鸟吗？

mastercard 可以在walmart ATM load 蓝鸟吗？# Money - 海外理财

w*y2013-07-30 07:07

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++的运算//囧

m*i2013-07-30 07:07

2 楼

现在情况如何？

k*r2013-07-30 07:07

3 楼

难道不是用inverted indexing做?

w*y2013-07-30 07:07

4 楼

是这个思路，但是不知道面试的时候具体怎么写code啊
好比inverted index这个 word 到docID的map 怎么实现; 每个docID 包含word个数的
count存、怎么increase.........
答用两个hashtable做的同学已经fail了，囧

【在 k*******r 的大作中提到】

: 难道不是用inverted indexing做?

b*g2013-07-30 07:07

5 楼

heap

code

【在 w***y 的大作中提到】

: -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*e2013-07-30 07:07

6 楼

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 的大作中提到】

l*a2013-07-30 07:07

7 楼

你是希望找到一组document, 其中每个都包含at least p words
还是说找到document的组合,使得每个组合含at least p words

code

【在 w***y 的大作中提到】

w*y2013-07-30 07:07

8 楼

今天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 的大作中提到】

: 你是希望找到一组document, 其中每个都包含at least p words
: 还是说找到document的组合,使得每个组合含at least p words
:
: code

j*u2013-07-30 07:07

9 楼

如果按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*y2013-07-30 07:07

10 楼

我想这个思路应该是正确的，因为当时面试的人也提示我考虑p=1 （union）或者p=m
(intersection) 的情况
但是我想不明白，如果 p 介于1~m之间，怎么做。。。。。

【在 j***u 的大作中提到】

: 如果按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*x2013-07-30 07:07

11 楼

倒排索引, 要先做预处理.
然后用一个map, map的pair是
1. 遍历一便句子的每一个不重复的词, 把这个词对应的文件号key的value加1.
2. 便利map, 找出频率>=p的文件

w*m2013-07-30 07:07

12 楼

你这个就是forward index啊，和inverted index有什么关系

【在 w****x 的大作中提到】

: 倒排索引, 要先做预处理.
: 然后用一个map, map的pair是
: 1. 遍历一便句子的每一个不重复的词, 把这个词对应的文件号key的value加1.
: 2. 便利map, 找出频率>=p的文件

j*u2013-07-30 07:07

13 楼

就是
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)