Redian新闻
>
问几道Google onsite 的问题
avatar
问几道Google onsite 的问题# JobHunting - 待字闺中
b*e
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.
avatar
p*2
2
好问题,第一题用Go应该可以轻松搞定。
第三题要求real time吗?如果不要求用Map/reduce就可以搞定。
avatar
g*y
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

avatar
r*d
4
第一题感觉把message放到threads公共的部分, 再实现lock之类的
请问一下这题是要当场些程序吗?
第二题
先给每一个document排序(count sort)。 然后再一个一个比较有没有互相cover?
怎么都是n*n了
第三题
max heap sort - 10*O(n)。
avatar
f*p
5
Q2根据例子来看,应该就是找 word duplicate吧。输出所有含有只出现一次的word的
docs
avatar
r*d
6
if input = {abcd, ab, cd}
output should be abcd?

【在 f******p 的大作中提到】
: Q2根据例子来看,应该就是找 word duplicate吧。输出所有含有只出现一次的word的
: docs

avatar
f*p
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?

avatar
l*n
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

avatar
b*e
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就可以搞定。

avatar
b*e
10

对 , 第一题是要当场写白板的。

【在 r******d 的大作中提到】
: 第一题感觉把message放到threads公共的部分, 再实现lock之类的
: 请问一下这题是要当场些程序吗?
: 第二题
: 先给每一个document排序(count sort)。 然后再一个一个比较有没有互相cover?
: 怎么都是n*n了
: 第三题
: max heap sort - 10*O(n)。

avatar
b*e
11

不好意思之前的描述有误, 请看新的修改。

【在 g**********y 的大作中提到】
: 第二题看例子的意思跟Set cover problem一样,后者是NP-Complete problem。
: http://en.wikipedia.org/wiki/Set_cover_problem
: 如果像题目描述的,"c d"就是minimum了,没有其它任何一个串里有d.
:
: a
: out
: one

avatar
b*e
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

avatar
g*e
13
给每个thread分一个blocking queue就完了。这题延伸开来是个很好的设计题, pubsub
, messaging framework etc.

【在 b********e 的大作中提到】
:
: 对, 其实就是set cover problem, 我之前的描述有误请看新的修改. 这题当场写白
: 板有些复杂啊, 哪位大神有好方法?

avatar
l*n
14
http://www.mimuw.edu.pl/~malcin/dydaktyka/2012-13/fpt/fpt_04_FS
还是dp。不过建memo的方式应该不止这一种思路。

【在 b********e 的大作中提到】
:
: 对, 其实就是set cover problem, 我之前的描述有误请看新的修改. 这题当场写白
: 板有些复杂啊, 哪位大神有好方法?

avatar
z*5
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

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。