文档章节

一道大数据处理的面试题

MPRO
 MPRO
发布于 2015/02/05 19:16
字数 577
阅读 417
收藏 27

有一个日志文件,每行记录了一次调用信息,其中包括时间和来源IP。每天的记录数目大约10亿条左右。现在需要:
1)获取日访问次数最高的1000个来源IP,按照访问量从高到低排序。
2)获取连续一周内访问次数最高的1000个来源IP,按照访问量从高到低排序。
请给出能得到精确(非近似)结果,并且效率尽可能高的计算方法,并给出主要部分伪代码。

 <span style="font-size: 18px;">#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <string.h>
/*
目的:建立大根堆,也可以变成小根堆,
核心:堆的调整
输入:一系列来自文件的整数。文件中整数以空格隔开
输出:大根堆
*/
void Swap(uint32_t* array, uint32_t i, uint32_t j)
{
 assert(array);
 uint32_t tmp;
 tmp = array[j];
 array[j] = array[i];
 array[i] = tmp;
}
/*大根堆调整*/
void MaxHeapify(uint32_t* array, uint32_t heapSize, uint32_t currentNode)
{
 uint32_t leftChild, rightChild,  largest;
 leftChild = 2*currentNode + 1;
 rightChild = 2*currentNode + 2;
 if(leftChild < heapSize && array[leftChild] > array[currentNode])
  largest = leftChild;
 else
  largest = currentNode;
 if(rightChild < heapSize && array[rightChild] > array[largest])
  largest = rightChild;
 if(largest != currentNode)
 {
     Swap(array, largest, currentNode);
  MaxHeapify(array, heapSize, largest);
 }
}
/*构建大根堆*/
void MaxHeapCreat(uint32_t* array, uint32_t heapSize)
{
 int i;
 for(i = heapSize/2; i >= 0; i--)
 {
  MaxHeapify(array, heapSize, i);
 }
}
/*小根堆调整*/
void MinHeapify(uint32_t* array, uint32_t heapSize, uint32_t currentNode)
{
 uint32_t leftChild, rightChild,  minimum;
 leftChild = 2*currentNode + 1;
 rightChild = 2*currentNode + 2;
 if(leftChild < heapSize && array[leftChild] < array[currentNode])
  minimum = leftChild;
 else
  minimum = currentNode;
 if(rightChild < heapSize && array[rightChild] < array[minimum])
  minimum = rightChild;
 if(minimum != currentNode)
 {
     Swap(array, minimum, currentNode);
  MinHeapify(array, heapSize, minimum);
 }
}
/*构建小根堆*/
void MinHeapCreat(uint32_t* array, uint32_t heapSize)
{
 int i;
 for(i = heapSize/2; i >= 0; i--)
 {
  MinHeapify(array, heapSize, i);
 }
}
int main()
{
 uint32_t tmp;
 uint32_t *array;
 array = malloc(sizeof(uint32_t));
 int i, heapSize = 0;
 /*从文件中读出待排序数据*/
    char* filePathway = "C:/Users/Administrator/Desktop/data.txt";
    FILE* fp;
 fp = fopen(filePathway, "rb");
 if(!fp)
 {
     fprintf(stderr, "Can not open file correctly\n");
 }
 while(!feof(fp))
 {
     fscanf(fp, "%d", &tmp);
     heapSize++;
     array = realloc(array, sizeof(uint32_t) * (heapSize ));
     if(array == NULL)
     {
         fprintf(stderr, "realloc error!\n");
         return 1;
     }
     array[heapSize - 1] = tmp;
    }
    printf("The origen dataset:\n");
    for(i = 0; i < heapSize; i++)
    {
        printf("%d\t", array[i]);
    }
    printf("\n");
    /*构建小根堆并输出*/
    MinHeapCreat(array, heapSize);
    printf("Output the MinHeap:\n");
    for(i = 0; i < heapSize; i++)
    {
        printf("%d\t", array[i]);
    }
    printf("\n");
    /*构建大根堆并输出*/
    MaxHeapCreat(array, heapSize);
    printf("Output the MaxHeap:\n");
    for(i = 0; i < heapSize; i++)
    {
        printf("%d\t", array[i]);
    }
    free(array);
 fclose(fp);
 return 0;
}
</span>

本文转载自:

共有 人打赏支持
MPRO

MPRO

粉丝 15
博文 47
码字总数 9718
作品 3
徐汇
后端工程师
私信 提问
加载中

评论(4)

noprom
noprom
nice
sunday12345
sunday12345

引用来自“ericsoul”的评论

既然都是大数据了。整个一千台x86装个hadoop集群。再来玩,不是so easy。解决方案不一定是算法,架构同样重要。

手里拿着锤子,看什么都像钉子。
ericsoul
ericsoul
既然都是大数据了。整个一千台x86装个hadoop集群。再来玩,不是so easy。解决方案不一定是算法,架构同样重要。
谢彬
谢彬
好东西,先收藏了。
Java面试题:如何处理大数据,如何在10s内应对10M个用户搜索?

一道Java面试题: 如何处理大数据,如何在10s内应对10M个用户搜索? 应该怎么答?

文心雕码
2014/02/11
1K
7
2018 前端面试准备

前端面试常见问题按知识点分类整理 前端面试常考问题整理,按模块知识点分类,持续完善中... Front-end-Developer-Questions by Modules and knowledge 前端面试经典问题:CSS 中居中的几种方...

掘金官方
2017/12/14
0
0
18届清华硕士狂拿18家互联网公司offer

2018校招总结(外企,国内大公司,国内创业公司) 本篇是我参加2018春招实习和秋招的求职经历,除了笔试面试中遇到的一些问题,更多的是一些个人想法。 春招和秋招面了不少公司,实习offer有...

野梦M
2017/12/18
0
1
远程面试的问题

因为地点不同,所以面试先安排远程面试,就是他们出题,自己这边做,写好程序后截图给他看源码。 HR发了3道面试题,都是算法面试题。一道一道发的,算法面试题网上都有答案。 但是都没有拿网...

盲人摸象
2015/02/09
3K
21
HR怎么从面试中了解程序员的真实水平?

HR肯定不懂或至少不太懂专业技术,这点,是一定的。 一个外行,怎么面试内行,很多求职者会很好奇。 其实,HR初试,更多的是看“人怎么样”,对“能力行不行”的观察,只是一个大概的情况,后...

明哥聊求职
2017/11/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

PHP生成CSV之内部换行

当我们使用PHP将采集到的文件内容保存到csv文件时,往往需要将采集内容进行二次过滤处理才能得到需要的内容。比如网页中的换行符,空格符等等。 对于空格等处理起来都比较简单,这里我们单独...

豆花饭烧土豆
53分钟前
1
0
使用 mjml 生成 thymeleaf 邮件框架模板

发邮件算是系统开发的一个基本需求了,不过搞邮件模板实在是件恶心事,估计搞过的同仁都有体会。 得支持多种客户端 支持响应式 疼彻心扉的 outlook 多数客户端只支持 inline 形式的 css 布局...

郁也风
57分钟前
4
0
让哲学照亮我们的人生——读《医务工作者需要学点哲学》有感2600字

让哲学照亮我们的人生——读《医务工作者需要学点哲学》有感2600字: 作者:孙冬梅;以前读韩国前总统朴槿惠的著作《绝望锻炼了我》时,里面有一句话令我印象深刻,她说“在我最困难的时期,...

原创小博客
今天
3
0
JAVA-四元数类

public class Quaternion { private final double x0, x1, x2, x3; // 四元数构造函数 public Quaternion(double x0, double x1, double x2, double x3) { this.x0 = ......

Pulsar-V
今天
17
0
Xshell利用Xftp传输文件,使用pure-ftpd搭建ftp服务

Xftp传输文件 如果已经通过Xshell登录到服务器,此时可以使用快捷键ctrl+alt+f 打开Xftp并展示Xshell当前的目录,之后直接拖拽传输文件即可。 pure-ftpd搭建ftp服务 pure-ftpd要比vsftp简单,...

野雪球
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部