[zz]腾讯面试题：腾讯服务器每秒有2w个QQ号同时上线，找出5min内重新登入的qq号并打印出来。
腾讯面试题：腾讯服务器每秒有2w个QQ号同时上线，找出5min内重新登入的qq号并打印出来。
解答:&如果空间足够大,可以定义一个大的数组&
&&&&&&&&a[qq号],初始为零,然后这个qq号登陆了就a[qq号]++&
&&&&&&&&最后统计大于等于2的QQ号&
&&&&&&&&这个用空间来代替时间
不成熟的想法：&
<font STYLE="Line-HeiGHT: 21 WorD-WrAp: WorD-BreAK: normal" COLOR="#w x 300s&
所以用 6,000,000 个桶。删除超时的算法后面说，所以平均桶的大小是 1
假设 qq 号码一共有 10^10 个，所以每个桶装的 q 号码是 10^10 / (6 * 10^6)
个，这个是插入时候的最坏效率（插入同一个桶的时候是顺序查找插入位置的）。&
qq的节点结构和上面大家讨论的基本一样，增加一个指针指向输出列表，后面说。&
struct QQstruct {&
&&num_type&&&&
&&timestamp&&last_logon_&
&&QQstruct&&&*&
&&QQstruct&&&*&
&&OutPutList
节点的时候，顺便更新一下输出列表。&
另外增加两个指针列表。&
第一个大小 300 的循环链表，自带一个指向 QQStruct 的域，循环存 300
秒内的qq指针。时间一过&
就 free 掉， 所以保证所有桶占用的空间在 2w X 300
输出列表，就是存放题目需要输出的节点。&
如果登陆的用户，5分钟内完全没有重复的话，每秒 free 掉 2w
不过在 free
的时候，要判断一下时间是不是真的超时，因为把节点入桶的时候，遇到重复的，会更&
新一下最后登陆的时间。当然啦，这个时候，要把这个 qq
号码放到需要输出的列表里面。
---------------------------------------------------分割线-----------------------------------------
首先把网上的答案贴出来，就是看这个答案了：
用 6,000,000 个桶。
qq的节点结构和上面大家讨论的基本一样，增加一个指针指向输出列表，后面说。&
struct QQstruct {&
&&&num_type
&&&timestamp
&&last_logon_&
&&&QQstruct
&&&QQstruct
&&&OutPutList
用于 free 节点的时候，顺便更新一下输出列表。&
增加两个指针列表。&
第一个大小 300 的循环链表，自带一个指向 QQStruct 的域，循环存 300
秒内的qq指针。时间一过&
就 free 掉， 所以保证所有桶占用的空间在 2w X 300
第二个是 输出列表， 就是存放题目需要输出的节点。&
如果登陆的用户，5分钟内完全没有重复的话，每秒 free 掉 2w
不过在 free
的时候，要判断一下时间是不是真的超时，因为把节点入桶的时候，遇到重复的，会更&
新一下最后登陆的时间。当然啦，这个时候，要把这个 qq 号码放到需要输出的列表里面。
---------------------------------------------------分割线-----------------------------------------
首先，我们考虑，如果是给定600w个QQ号，是静态的，那麽使用位图应该是最好的方法了。由于QQ号码最多有10^10个≈10G，那麽每个QQ号用2bit存放，也就是需要2.5GB的内存空间，可以找到。
其次，考虑还是动态的，如果记录每个QQ号码的时间戳，在添加时进行对比，如果存放时间戳的数据结构为4字节，那麽需要的空间为40GB，过大。
-----------------------------------------------------分割线---------------------------------------
在回过头来之前的解法，QQstruct结构的大小为20B，600W个这个结构的大小为120MB，相对于40GB，降低了很多。
首先，插入的规则。将每秒中的2w个QQ，构造成QQstruct结构，hash之后存放在桶中，同一桶中的QQstruct按照qqnum大小进行排序。同时声明一个指针，将这2w个QQ链接起来。如果在插入时，发现相同的QQ号之前已经登录过了，那麽不再生成新的QQstruct结构，而只是更新last_logon_time字段。
比如说head_t1指向在在t1登录的所有QQ号，head_t2类似，如果qqnum1在t1和t2（t1
t2）都登入过，那麽head_t1和head_t2会有同样一个结构，结构中，qqnum=qqnum1，last_logon_time=t2。
其次，删除的规则。由于始终存放600w个条目，超时之后，就应该将之前的条目删除。比如在第t1+300秒，就应该将head_t1指向的QQstrcut结构删除。删除之前，需要做一个判断，即last_logon_time是否等于t1，即这个QQ号码在之后的时间是否登入过。当删除qqnum1时，发现last_logon_time不等于t1，证明这个QQ号码在5min钟内重复登入了，将它打印出来，但是不删除。如果发现last_logon_time是等于t1的，就将对应的QQstruct结构释放掉。
整个算法就是这个样子了，而我对于这个QQstruct结构还是有些疑问的，对于OutPutList
*out这个成员很陌生，而且对于任意一个QQ号，既会存在于某个桶的链中，也存在于某个时间点的链中，所以需要进行修改：
struct QQstruct {&
timestamp last_logon_&
QQstruct *pre_&
QQstruct *next_&
QQstruct *pre_&
QQstruct *next_&
重新计算下需要的空间，桶结点本身可能需要占用空间，假设每个桶结点是8B，那麽桶结点需要8B
* 600w ≈ 48MB；剩下的就是QQstruct结构的大小了，最多为24B * 600w ≈
144MB，所有的空间加起来也就200MB了。
当然插入删除时，相较于时间戳策略要耗时，也属于用时间换空间的想法吧，呵呵~~
————————————————————————————————————————————————
一个文件中有40亿个整数，每个整数为四个字节，内存为1GB，写出一个算法：求出这个文件里的整数里不包含的一个整数
方法一: 4个字节表示的整数，总共只有2^32约等于4G个可能。
为了简单起见，可以假设都是无符号整数。
分配500MB内存，每一bit代表一个整数，刚好可以表示完4个字节的整数，初始值为0。基本思想每读入一个数，就把它对应的bit位置为１，处理完40G个数后，对500M的内存遍历，找出一个bit为0的位，输出对应的整数就是未出现的。
算法流程：
１）分配５００ＭＢ内存buf，初始化为０
２）unsigned&int&x=0x1;
&&&for&each&int&j&in&file
&&&buf=buf
(3)&for(unsigned&int&i=0;&i&&&=&0&i++)
&&&&&&&if&(!(buf&&&x
&&&&&&&&&&&output(i);
&&&&&&&&&&&
以上只是针对无符号的，有符号的整数可以依此类推。
文件可以分段读啊，这个是O（2n）算法，应该是很快的了，而且空间也允许的。
不过还可以构造更快的方法的，更快的方法主要是针对定位输出的整数优化算法。
思路大概是这样的，把值空间等分成若干个值段，比如值为无符号数，则
FFFFF000H-FFFFFFFFH
这样可以订立一个规则，在一个值段范围内的数第一次出现时，对应值段指示值Xn=Xn+1，如果该值段的所有整数都出现过，则Xn=1000H，这样后面输出定位时就可以直接跳过这个值段了，因为题目仅仅要求输出一个，这样可以大大减少后面对标志数值的遍历步骤。
理论上值段的划分有一定的算法可以快速的实现，比如利用位运算直接定位值段对应值进行计算。
——————————————————————————————————————
题目：在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可（内存限制为
2G的意思就是，可以使用2G的空间来运行程序，而不考虑这台机器上的其他软件的占用内存）。
关于中位数：数据排序后，位置在最中间的数值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=(N+1)/2
; 当样本数为偶数时，中位数为N/2与1+N/2的均值（那么10G个数的中位数，就第5G大的数与第5G+1大的数的均值了）。
分析：&既然要找中位数，很简单就是排序的想法。那么基于字节的桶排序是一个可行的方法&
思想：将整形的每1byte作为一个关键字，也就是说一个整形可以拆成4个keys，而且最高位的keys越大，整数越大。如果高位keys相同，则比较次高位的keys。整个比较过程类似于字符串的字典序。
第一步:把10G整数每2G读入一次内存，然后一次遍历这536,870,912个数据。每个数据用位运算"&&"取出最高8位(31-24)。这8bits(0-255)最多表示255个桶，那么可以根据8bit的值来确定丢入第几个桶。最后把每个桶写入一个磁盘文件中，同时在内存中统计每个桶内数据的数量，自然这个数量只需要255个整形空间即可。
10G数据依次读入内存的IO代价(这个是无法避免的，CPU不能直接在磁盘上运算)。(2)在内存中遍历536,870,912个数据，这是一个O(n)的线性时间复杂度。(3)把255个桶写会到255个磁盘文件空间中，这个代价是额外的，也就是多付出一倍的10G数据转移的时间。
第二步：根据内存中255个桶内的数量，计算中位数在第几个桶中。很显然，2,684,354,560个数中位数是第1,342,177,280个。假设前127个桶的数据量相加，发现少于1,342,177,280，把第128个桶数据量加上，大于1,342,177,280。说明，中位数必在磁盘的第128个桶中。而且在这个桶的第1,342,177,280-N(0-127)个数位上。N(0-127)表示前127个桶的数据量之和。然后把第128个文件中的整数读入内存。(平均而言，每个文件的大小估计在10G/128=80M左右，当然也不一定，但是超过2G的可能性很小)。
代价：(1)循环计算255个桶中的数据量累加，需要O(M)的代价，其中m&255。(2)读入一个大概80M左右文件大小的IO代价。
注意，变态的情况下，这个需要读入的第128号文件仍然大于2G，那么整个读入仍然可以按照第一步分批来进行读取。
第三步：继续以内存中的整数的次高8bit进行桶排序(23-16)。过程和第一步相同，也是255个桶。
第四步：一直下去，直到最低字节(7-0bit)的桶排序结束。我相信这个时候完全可以在内存中使用一次快排就可以了。
整个过程的时间复杂度在O(n)的线性级别上(没有任何循环嵌套)。但主要时间消耗在第一步的第二次内存-磁盘数据交换上，即10G数据分255个文件写回磁盘上。一般而言，如果第二步过后，内存可以容纳下存在中位数的某一个文件的话，直接快排就可以了。
————————————————————————————————————
从《&》中我们知道：全依赖“比较”操作的排序算法时间复杂度的一个下界O(N*logN)。但确实存在更快的算法。这些算法并不是不用“比较”操作，也不是想办法将比较操作的次数减少到
logN。而是利用对待排数据的某些限定性假设&，来避免绝大多数的“比较”操作。桶排序就是这样的原理。
桶排序的基本思想
&&&&&&&假设有一组长度为N的待排关键字序列K[1....n]。首先将这个序列划分成M个的子区间(桶)&。然后基于某种映射函数&，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标
，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]....B[M]中的全部内容即是一个有序序列。
[桶—关键字]映射函数
&&&&&&bindex=f(key)&&&其中，bindex
为桶数组B的下标(即第bindex个桶),
k为待排序列的关键字。桶排序之所以能够高效，其关键在于这个映射函数，它必须做到：如果关键字k1&k2，那么f(k1)&=f(k2)。也就是说B(i)中的最小数据都要大于B(i-1)中最大数据。很显然，映射函数的确定与数据本身的特点有很大的关系，我们下面举个例子：
假如待排序列K= {49、&38&、&35、&97&、&76、&73&、&27、&49&}。这些数据全部在1—100之间。因此我们定制10个桶，然后确定映射函数f(k)=k/10。则第一个关键字49将定位到第4个桶中(49/10=4)。依次将所有关键字全部堆入桶中，并在每个非空的桶中进行快速排序后得到如下图所示：
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
对上图只要顺序输出每个B[i]中的数据就可以得到有序序列了。
桶排序代价分析
桶排序利用函数的映射关系，减少了几乎所有的比较工作。实际上，桶排序的f(k)值的计算，其作用就相当于快排中划分，已经把大量数据分割成了基本有序的数据块(桶)。然后只需要对桶中的少量数据做先进的比较排序即可。
对N个关键字进行桶排序的时间复杂度分为两个部分：
(1) 循环计算每个关键字的桶映射函数，这个时间复杂度是O(N)。
利用先进的比较排序算法对每个桶内的所有数据进行排序，其时间复杂度为&&∑
O(Ni*logNi) 。其中Ni 为第i个桶的数据量。
很显然，第(2)部分是桶排序性能好坏的决定因素。尽量减少桶内数据的数量是提高效率的唯一办法(因为基于比较排序的最好平均时间复杂度只能达到O(N*logN)了)。因此，我们需要尽量做到下面两点：
(1) 映射函数f(k)能够将N个数据平均的分配到M个桶中，这样每个桶就有[N/M]个数据量。
尽量的增大桶的数量。极限情况下每个桶只能得到一个数据，这样就完全避开了桶内数据的“比较”排序操作。&当然，做到这一点很不容易，数据量巨大的情况下，f(k)函数会使得桶集合的数量巨大，空间浪费严重。这就是一个时间代价和空间代价的权衡问题了。
对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为：
&&&&&&&&&&&&&O(N)+O(M*(N/M)*log(N/M))=O(N+N*(logN-logM))=O(N+N*logN-N*logM)
当N=M时，即极限情况下每个桶只有一个数据时。桶排序的最好效率能够达到O(N)。
总结：&桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。&当然桶排序的空间复杂度&为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。
其实我个人还有一个感受：在查找算法中，基于比较的查找算法最好的时间复杂度也是O(logN)。比如折半查找、平衡二叉树、红黑树等。但是Hash表却有O(C)线性级别的查找效率(不冲突情况下查找效率达到O(1))。大家好好体会一下：Hash表的思想和桶排序是不是有一曲同工之妙呢?
桶排序在海量数据中的应用
一年的全国高考考生人数为500&万，分数使用标准分，最低100&，最高900&，没有小数，你把这500&万元素的数组排个序。
分析：对500W数据排序，如果基于比较的先进排序，平均比较次数为O(5000000*log5000000)≈1.112亿。但是我们发现，这些数据都有特殊的条件：&&100=&score&=900。那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。
方法：创建801(900-100)个桶。将每个考生的分数丢进f(score)=score-100的桶中。这个过程从头到尾遍历一遍数据只需要500W次。然后根据桶号大小依次将桶中数值输出，即可以得到一个有序的序列。而且可以很容易的得到100分有***人，501分有***人。
实际上，桶排序对数据的条件有特殊要求，如果上面的分数不是从100-900，而是从0-2亿，那么分配2亿个桶显然是不可能的。所以桶排序有其局限性，适合元素值集合并不大的情况。
#include&iostream.h&&&&
#include&malloc.h&&&&
typedef&struct&node{
&&&&struct&node&*&
void&inc_sort(int&keys[],int&size,int&bucket_size){
&&&&KeyNode&**bucket_table=(KeyNode&**)malloc(bucket_size*sizeof(KeyNode&*));
&&&&for(int&i=0;i&bucket_i++){
&&&&&&&&bucket_table[i]=(KeyNode&*)malloc(sizeof(KeyNode));
&&&&&&&&bucket_table[i]-&key=0;&//记录当前桶中的数据量&&&
&&&&&&&&bucket_table[i]-&next=NULL;
&&&&for(int&j=0;j&j++){
&&&&&&&&KeyNode&*node=(KeyNode&*)malloc(sizeof(KeyNode));
&&&&&&&&node-&key=keys[j];
&&&&&&&&node-&next=NULL;
&&&&&&&&//映射函数计算桶号&&&
&&&&&&&&int&index=keys[j]/10;
&&&&&&&&//初始化P成为桶中数据链表的头指针&&&
&&&&&&&&KeyNode&*p=bucket_table[index];
&&&&&&&&//该桶中还没有数据&&&
&&&&&&&&if(p-&key==0){
&&&&&&&&&&&&bucket_table[index]-&next=
&&&&&&&&&&&&(bucket_table[index]-&key)++;
&&&&&&&&}else{
&&&&&&&&&&&&//链表结构的插入排序&&&
&&&&&&&&&&&&while(p-&next!=NULL&&p-&next-&key&=node-&key)
&&&&&&&&&&&&&&&&p=p-&&&&&&&
&&&&&&&&&&&&node-&next=p-&
&&&&&&&&&&&&p-&next=
&&&&&&&&&&&&(bucket_table[index]-&key)++;
&&&&//打印结果&&&
&&&&for(int&b=0;b&bucket_b++)
&&&&&&&&for(KeyNode&*k=bucket_table[b]-&&k!=NULL;&k=k-&next)
&&&&&&&&&&&&cout&&k-&key&&"&";
&&&&cout&&
void&main(){
&&&&int&raw[]={49,38,65,97,76,13,27,49};&&&&&&
&&&&int&size=sizeof(raw)/sizeof(int);&&&&&&
&&&&inc_sort(raw,size,10);
&上面源代码的桶内数据排序，我们使用了基于单链表的直接插入排序算法。可以使用基于双向链表的快排算法提高效率。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。