b********e
发帖数: 43 | 1 1. Multiple threads can publish and receive each other's message: whenever a
thread publishes a message, all the other threads can receive and print out
that message; if multiple message get published, the messages should be
queued or whatever recorded and other threads can print out the message one
by one; no published message should be missed by any other threads.
2. Give a list of documents, find the minimal document set that cannot be
covered by the other documents, like
“a b c h j”, "c d”, “a b c” “a f g” “a h j”
the result should be "a b c h j" "c d" and "a f g"
3. Design a system to return the top 10 Google query that occurred before
certain time. |
p*****2
发帖数: 21240 | 2 好问题，第一题用Go应该可以轻松搞定。
第三题要求real time吗？如果不要求用Map/reduce就可以搞定。 |
g**********y
发帖数: 14569 | 3 第二题看例子的意思跟Set cover problem一样，后者是NP-Complete problem。
http://en.wikipedia.org/wiki/Set_cover_problem
如果像题目描述的，"c d"就是minimum了，没有其它任何一个串里有d.
a
out
one
【在 b********e 的大作中提到】
: 1. Multiple threads can publish and receive each other's message: whenever a
: thread publishes a message, all the other threads can receive and print out
: that message; if multiple message get published, the messages should be
: queued or whatever recorded and other threads can print out the message one
: by one; no published message should be missed by any other threads.
: 2. Give a list of documents, find the minimal document set that cannot be
: covered by the other documents, like
: “a b c h j”, "c d”, “a b c” “a f g” “a h j”
: the result should be "a b c h j" "c d" and "a f g"
: 3. Design a system to return the top 10 Google query that occurred before
|
r******d
发帖数: 308 | 4 第一题感觉把message放到threads公共的部分， 再实现lock之类的
请问一下这题是要当场些程序吗？
第二题
先给每一个document排序（count sort）。 然后再一个一个比较有没有互相cover？
怎么都是n*n了
第三题
max heap sort － 10*O（n）。 |
f******p
发帖数: 173 | 5 Q2根据例子来看，应该就是找 word duplicate吧。输出所有含有只出现一次的word的
docs |
r******d
发帖数: 308 | 6 if input = {abcd, ab, cd}
output should be abcd?
【在 f******p 的大作中提到】
: Q2根据例子来看，应该就是找 word duplicate吧。输出所有含有只出现一次的word的
: docs
|
f******p
发帖数: 173 | 7 2. Give a list of documents, find the minimal document set that cannot be
covered by the other documents, like
“a b c h j”, "c d”, “a b c” “a f g” “a h j”
the result should be "a b c h j" "c d" and "a f g"
楼主描述里，a or b or c .. 应该代表一个doc里的一个word，只是为了描述方便所以
用char代替了。granularity是word。
所以你的例子应该是这样吧：
doc1: abcd,
doc2: ab,
doc3: cd
如果这样应该全输出。
如果我理解错了请指出。。
【在 r******d 的大作中提到】
: if input = {abcd, ab, cd}
: output should be abcd?
|
l*n
发帖数: 529 | 8 就算法上来讲，应该是个dp问题：通过用或者不用d[i]来进行递归，最后比较大小给出
set数最小的。每次选定一个后，对剩下的可以进行coverage计算和过滤。
【在 g**********y 的大作中提到】
: 第二题看例子的意思跟Set cover problem一样，后者是NP-Complete problem。
: http://en.wikipedia.org/wiki/Set_cover_problem
: 如果像题目描述的，"c d"就是minimum了，没有其它任何一个串里有d.
:
: a
: out
: one
|
b********e
发帖数: 43 | 9
二爷第一题如果不用Go的话 Java怎么做？
第三题 他说先不要求real time, 我用hash table做的，估算how many query a
server can process: 100 per second. The amount of query each server can
process per day should be: 100 * 40 bytes * 3600 * 24 is about 350Mb, so it
can be stored in one server’s memory.
完成之后时间不够了, 感觉他更期望real-time的答案。
【在 p*****2 的大作中提到】
: 好问题，第一题用Go应该可以轻松搞定。
: 第三题要求real time吗？如果不要求用Map/reduce就可以搞定。
|
b********e
发帖数: 43 | 10
对 ， 第一题是要当场写白板的。
【在 r******d 的大作中提到】
: 第一题感觉把message放到threads公共的部分， 再实现lock之类的
: 请问一下这题是要当场些程序吗？
: 第二题
: 先给每一个document排序（count sort）。 然后再一个一个比较有没有互相cover？
: 怎么都是n*n了
: 第三题
: max heap sort － 10*O（n）。
|
|
|
b********e
发帖数: 43 | 11
不好意思之前的描述有误， 请看新的修改。
【在 g**********y 的大作中提到】
: 第二题看例子的意思跟Set cover problem一样，后者是NP-Complete problem。
: http://en.wikipedia.org/wiki/Set_cover_problem
: 如果像题目描述的，"c d"就是minimum了，没有其它任何一个串里有d.
:
: a
: out
: one
|
b********e
发帖数: 43 | 12
对， 其实就是set cover problem， 我之前的描述有误请看新的修改. 这题当场写白
板有些复杂啊， 哪位大神有好方法？
【在 g**********y 的大作中提到】
: 第二题看例子的意思跟Set cover problem一样，后者是NP-Complete problem。
: http://en.wikipedia.org/wiki/Set_cover_problem
: 如果像题目描述的，"c d"就是minimum了，没有其它任何一个串里有d.
:
: a
: out
: one
|
g**e
发帖数: 6127 | 13 给每个thread分一个blocking queue就完了。这题延伸开来是个很好的设计题, pubsub
, messaging framework etc.
【在 b********e 的大作中提到】
:
: 对， 其实就是set cover problem， 我之前的描述有误请看新的修改. 这题当场写白
: 板有些复杂啊， 哪位大神有好方法？
|
l*n
发帖数: 529 | 14 http://www.mimuw.edu.pl/~malcin/dydaktyka/2012-13/fpt/fpt_04_FS
还是dp。不过建memo的方式应该不止这一种思路。
【在 b********e 的大作中提到】
:
: 对， 其实就是set cover problem， 我之前的描述有误请看新的修改. 这题当场写白
: 板有些复杂啊， 哪位大神有好方法？
|
z*********5
发帖数: 3 | 15 有大牛能讲讲这里的第一题应该怎么做吗？
每个thread有一个blocking queue来放这个thread需要打印的message? 可这样的话某
个thread的queue满时，要publish message的calling thread就会被block在那，这样
其他的operation就被block了。。
a
out
one
【在 b********e 的大作中提到】
: 1. Multiple threads can publish and receive each other's message: whenever a
: thread publishes a message, all the other threads can receive and print out
: that message; if multiple message get published, the messages should be
: queued or whatever recorded and other threads can print out the message one
: by one; no published message should be missed by any other threads.
: 2. Give a list of documents, find the minimal document set that cannot be
: covered by the other documents, like
: “a b c h j”, "c d”, “a b c” “a f g” “a h j”
: the result should be "a b c h j" "c d" and "a f g"
: 3. Design a system to return the top 10 Google query that occurred before
|
