阿里巴巴集团2014秋季校园招聘笔试题(4)

C++选做题
Part I
假设你有一台计算机，配置如下：
48GB内存
16核CPU，3.0GHz
12块2TB SATA硬盘
有两个数据文件A和B，A的大小是40GB，B的大小是2TB，A和B的文件格式一样，都包含等长的100字节的记录，记录的前20个字节表示key，后80个字节表示value，所有的key和value都由数字和大小写字母组成（0-9 A-Z a-z），同一个文件中的key没有排序，也没有重复。
文件A和B都切成了1GB（1*10^9字节）的数据块（名为A000001、A000002......A000010、B000001、B000002......B002000），均匀分布在6块硬盘上。
请问如何用最快的方法找到A和B之间共同的key，以及他们对应的value值（建议输出格式如下所示：<key><空格><A中对应value><空格><B中对应value>）


请描述你的方法里面用到的关键的数据结构和算法，估算这个方法需要的内存空间和运算时间，并说明你的推导过程。


Part II
如果你有100台服务器，每台配置如上描述，它们通过千兆网络组成一个集群，任意两台之间的带宽可以达到1000Mbps，同时假设文件A和B的大小也放大100倍（各位4TB和200TB），并且被切分成1GB的碎片，均匀分布在100台服务器上。
请问如何用最快的方法找到A和B之间共同的key，以及他们对应的value值（建议输出格式如下所示：<key><空格><A中对应value><空格><B中对应value>）


请描述你的方法里面用到的关键的数据结构和算法，估算这个方法需要的内存空间、网络流和运算时间，并说明你的推导过程。