发布于 2014-10-19 09:57:02 | 601 次阅读 | 评论: 0 | 来源: 网友投递
腾讯
腾讯控股有限公司（腾迅）是一家民营IT企业，成立于1998年11月29日，总部位于中国广东深圳，是中国最大的互联网综合服务提供商之一，也是中国服务用户最多，最广的互联网企业之一。
1、在一个文件中有10G 个整数，乱序排列，要求找出中位数。内存限制为2G。只写出思路即可。
海量数据处理的问题。10G个数，中位数就是第5G、第5G+1个数。回想一下，一般情况下求中位数的做法：类似于快排的partition，找到一个 数，使比它小的数的个数占到总数的一半就行。所以，可以把数值空间分段，然后统计每一段中数据的个数，这样就可以很容易的确定中位数在那一段。找个该段 后，数据量已经急剧减小了，剩下的问题就好处理了。这种方法可以说是桶排序的思想，也可以说是hash的思想。下面具体分析一下：
因为要统计每一段中数据的个数，所以可以用一个unsigned int型。unsigned int一般占4个字节，可以计数到2^32-1，大约是4G。题目中有10G个数，如果有很多数落在同一个段中，unsigned int肯定不够用。所以，这里的计数用要8字节的long long。即，相当于有一个数组，数组是long long性，数组的每一个元素，代表了一个数据段内的数据个数。这个数组有多大？为了充分利用2G内存，数组大小2G/8 = 256M。即，有数组long long cnt[256M].
假设题目中的10G个数都是4字节的int。如何把这10G个整数，映射到cnt[256M]的数组中。可以使用计算机中的虚拟地址到物理地址的转换。取int的高28位作为数组下标的索引值，这样就可以完成映射。
整个算法的流程：
扫描10G个整数，对每个整数，取高28位，映射到数组的某个元素上
给数组的这个元素加1，表示找到一个属于该数据段的元素
扫描完10G个整数后，数组cnt中就记录了每段中元素的个数
从第一段开始，将元素个数累计，直到值刚好小于5G，则中位数就在该段
这时对10G个整数再扫描一遍，记录该段中每个元素的个数。直至累计到5G即可。
2、一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数。
方法一：
使用位图。4字节的int，有4G个不同的值。每个值，对应1bit，则共需 4G/8 = 512M 内存。初始状态，对512M的位图清零。然后，对这40亿个整数进行统计。如果某个值出现了，那么就把这个值对应的bit置位。最后，扫描位图，找到一个 没有被置位的bit即可。
方法二：
分段统计。Long long cnt[512M/8=64M]对应数值空间的64M个数据段。每个数据段包含64个不同值，用一个long long作为这个数据段内的位图，位图占64M*8=512M。
这样扫描一遍40亿个整数后，从数组中找到一个计数小于64的元素，然后查看它的位图，找出未出现的元素。
方法二平均性能应该比方法一快，但它占的内存很恐怖。其实，这两种方法都不是很实际，总共1G的内存，算法就消耗512M甚至1G，那剩下的系统程序怎么办？OS都跑不起来了吧。
3、腾讯服务器每秒有2w个QQ号同时上线，找出5min内重新登入的qq号并打印出来。
这应该是道面试题，面试官随口问了一下。主要是看思路吧。
最简单的想法：直接用STL的set。从某一时刻开始计时，每登陆一个QQ，把它放入set，如果已存则直接打印。直到5min后，就可以over了。下面来简单分析一下算法的复杂度：
空间复杂度：用str存储每个QQ号，假设QQ号有20位，理想情况下每个QQ占20Byte。则5min内的QQ：2w * 60 * 5 = 600w个，需要的存储空间600w * 20byte = 12000w byte = 120M，这样的存储应该可以忍受吧。
时间复杂度：STL的set是用二叉树（更确切的说是：红黑树）实现的，查找效率是O( lgn )，应该还是挺快的吧。
呃，有人说不让用STL。那就自己设计一个数据结构呗。该用什么数据结构呢？想了想，还是继续用树，这里用一个trie tree吧。节点内容包括QQ号、指向子节点的指针（这里有10个，认为QQ由0---9的数字组成）。登陆时间要不要？考虑这样一个问题：是否需要把所 有的QQ都保存在内存中？随着时间的增加，登陆的QQ会越来越多，比较好的方法是把长时间不登陆的QQ释放掉。所以需要记录登陆时间，以便于释放长期不登 陆的QQ。
struct TrieNode
{
string qq;
int lastLoginTime;
TrieNode *next[10];
};
我们的trie上的操作主要有两个：查找并插入、删除。也就是说，这颗树是不断动态变化的，我们需要维护它。