一道题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

一道题

一道题# JobHunting - 待字闺中

p*o2012-06-04 07:06

1 楼

某家on-site的一道题。
Find the most frequent character in a string.
Data: strings are composed of Unicode charaters, stored in 10 sets of 5GB
files on 10 different servers each with 2GB of memory.
Constraints: network communication is expensive.
Question: find the best algorithm.

m*g2012-06-04 07:06

2 楼

hadoop word count?

Z*Z2012-06-04 07:06

3 楼

MapReduce的思路吧，10台机器，每个负责数一个区间内的数。
基本算法就是每个机器读自己的文件，然后发送每个字符到相应的机器上。
要是想save network communication cost，可以每台机器把要发送的字符cache起来，
这样每个机器生成10个文件，然后把其中的9个发送到相应的主机上去。

【在 p*****o 的大作中提到】

: 某家on-site的一道题。
: Find the most frequent character in a string.
: Data: strings are composed of Unicode charaters, stored in 10 sets of 5GB
: files on 10 different servers each with 2GB of memory.
: Constraints: network communication is expensive.
: Question: find the best algorithm.