腾讯手机QQ实习C++一面面经

自己上腾讯校招投的简历，过了两天腾讯打电话过来面试。

由于没有指定部门，只选了C++后台，这次是手机QQ的深圳部门打过来，问的都是海量数据问题。

问题一：现在所有的qq号共40亿个，假设有1000亿条登录记录，怎么样找到出现过的qq号，内存消耗多大。

参考答案：哈希表，把40亿个放进哈希表中，遍历100亿条就好了。消耗大概是 40亿*4Byte=160亿Byte=160*10^8Byte<16G

问题二：现在只有8个G的内存，怎么实现这个操作。

参考答案：位图，用一位来代表一个数据是否出现。开一个40亿/8Byte+1Byte=5亿Byte<500M空间的数组（char NUMS[]），40亿个数字映射对应的num 1~40亿，对应的数组项为NUMS[num/8]，需要修改的位是num%8。这样消耗的空间只需要500M不到。

问题三：如果需要统计每个qq号出现过的次数，该怎么解决（开放）。

参考答案：把每个数映射到每个char类型，每个char类型可以统计256个登录记录，那么共需要40亿Byte=4G空间。因为实际应用场景中，登录记录应该符合正态分布，所以假设超过256次登录的qq号不多，把多出来的qq号用hash_map来存储大于登录次数大于256的qq号次数。

总结：

1. 该部门一面主要考察海量数据思路，这和一般的C++面试不一样，应该是部门场景需要。

2. 需要对存储空间、存储单位换算等基础知识比较敏感，比如int 是 4Byte ，10亿Byte是1G。

3. 解题无方就结合应用场景。