笔试题统计人数

时间：2024-07-28 15:30:52 资料大全我要投稿

笔试题（统计人数）

笔试题：统计论坛在线人数分布

笔试题（统计人数）

　　求一个论坛的在线人数，假设有一个论坛，其注册ID有两亿个，每个ID从登陆到退出会向一个日志文件中记下登陆时间和退出时间，要求写一个算法统计一天中论坛的用户在线分布，取样粒度为秒，

。

　　分析：

　　一天总共有 3600*24 = 86400秒。

　　定义一个长度为86400的整数数组int delta[86400]，每个整数对应这一秒的人数变化值，可能为正也可能为负。开始时将数组元素都初始化为0。

　　然后依次读入每个用户的登录时间和退出时间，将与登录时间对应的整数值加1，将与退出时间对应的整数值减1。

　　这样处理一遍后数组中存储了每秒中的人数变化情况。

　　定义另外一个长度为86400的整数数组int online_num[86400]，每个整数对应这一秒的论坛在线人数。

　　假设一天开始时论坛在线人数为0，则第1秒的人数online_num[0] = delta[0]，

《笔试题（统计人数）》(https://www.unjs.com)。第n+1秒的人数online_num[n] = online_num[n-1] + delta[n]。

　　这样我们就获得了一天中任意时间的在线人数。

　　笔试题：从10G个数中找到中数

　　在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。

　　分析：

　　不妨假设10G个整数是64bit的。

　　2G内存可以存放256M个64bit整数。

　　我们可以将64bit的整数空间平均分成256M个取值范围，用2G的内存对每个取值范围内出现整数个数进行统计。这样遍历一边10G整数后，我们便知道中数在那个范围内出现，以及这个范围内总共出现了多少个整数。

　　如果中数所在范围出现的整数比较少，我们就可以对这个范围内的整数进行排序，找到中数。如果这个范围内出现的整数比较多，我们还可以采用同样的方法将此范围再次分成多个更小的范围(256M=2^28，所以最多需要3次就可以将此范围缩小到1，也就找到了中数)。

【笔试题统计人数】相关文章：