求问一道去年阿里秋招的C++笔试大题思路

2014/8/25镜像同步11 回复

求问阿里去年秋招的一道c++题，一遇到这种题就一点思路也没有，求大牛们指点一下思路~~~~这种题要怎么入手的说~~~~~~ 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>）请描述你的方法里面用到的关键的数据结构和算法，估算这个方法需要的内存空间、网络流和运算时间，并说明你的推导过程。

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

FromSixToTen机器人#1 · 2014/8/25

遇到大数据的问题一般用哈希。就是这些。关键看哈希表如何构建。

panchao机器人#2 · 2014/8/25

同问

spicewolf机器人#3 · 2014/8/25

小白疑问：为什么提到12块硬盘？题目的意思是计算机一次只能访问一个硬盘么？

wdjwxh机器人#4 · 2014/8/26

求指点.

anna07机器人#5 · 2014/8/26

完全不明白…… 【在 spicewolf 的大作中提到: 】 : 小白疑问：为什么提到12块硬盘？题目的意思是计算机一次只能访问一个硬盘么？

anna07机器人#6 · 2014/8/26

一般不是分文件的时候就用hash么，这个已经给分好了，不知道分了有什么用【在 FromSixToTen 的大作中提到: 】 : 遇到大数据的问题一般用哈希。就是这些。关键看哈希表如何构建。

FromSixToTen机器人#7 · 2014/8/26

【在 anna07 的大作中提到: 】 : 一般不是分文件的时候就用hash么，这个已经给分好了，不知道分了有什么用接下来依然需要哈希来自「北邮人论坛手机版」

keita1314机器人#8 · 2014/8/26

说说自己的思路，没考虑算法，会比较慢，应该还有算法优化的方法。 1.对a,b切分的每一个小文件其每一行都为key,value,对每一行的的key进行hash(key),根据hash出来的值写到各个结果文件里面 2.这个时候每个结果里面的每一行都： key,a_valule ..... key,b_value 3.再用awk或者perl可以对每个结果文件进行处理可以得到key,a_value,b_value。当然这种思路是完全没考虑时间，不过结果应该是正确的我觉得如果要考虑时间快可能还是要考虑一下Bloom Filter这些

nuanyangyang机器人#9 · 2014/8/27

感觉瓶颈是IO。那么多核不知道有没有用。