文档章节

一道大数据处理的面试题

YKIT
 YKIT
发布于 2015/02/05 19:16
字数 577
阅读 417
收藏 27
点赞 0
评论 4

有一个日志文件,每行记录了一次调用信息,其中包括时间和来源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>

© 著作权归作者所有

共有 人打赏支持
YKIT

YKIT

粉丝 14
博文 41
码字总数 8403
作品 3
苏州
后端工程师
加载中

评论(4)

noprom
noprom
nice
sunday12345
sunday12345

引用来自“ericsoul”的评论

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

手里拿着锤子,看什么都像钉子。
ericsoul
ericsoul
既然都是大数据了。整个一千台x86装个hadoop集群。再来玩,不是so easy。解决方案不一定是算法,架构同样重要。
谢彬
谢彬
好东西,先收藏了。
2018 前端面试准备

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

掘金官方 ⋅ 2017/12/14 ⋅ 0

2018最新版本的spark面试题及答案

Spark是一个围绕速度、易用性和复杂分析构建的大数据处理框架,Spark提供了一个全面、统一的框架用于管理各种有着不同性质(文本数据、图表数据等)的数据集和数据源(批量数据或实时的流数据)...

嘿你好夏天 ⋅ 04/03 ⋅ 0

大数据面试题,99%会机率碰到的海量题

三月已过去5天了,现在全国各省正处于招聘的高峰期,面试者也越来越紧张,都希望有高人指点一二,倘若有面试题能提示一下,那面试能拿到offer的机会便大的多,下面就是一些常见的大数据面试题...

mkkm1314 ⋅ 04/10 ⋅ 0

18届清华硕士狂拿18家互联网公司offer

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

野梦M ⋅ 2017/12/18 ⋅ 1

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

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

文心雕码 ⋅ 2014/02/11 ⋅ 7

HR怎么从面试中了解程序员的真实水平?

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

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

小米面经-技术岗(编程小白如何进阶)

先介绍下背景,我本科专业是硬件转软件方面,所以一开始算法基础比较差,没有做过系统设计,为了能得到好的面试机会,我一直都有努力准备,还在网上关注了各种能提高编程能力的攻略,我觉得打...

coderer ⋅ 2017/05/08 ⋅ 0

微软SDE面经(电面+onsite)

本人工作1年多了,正在准备跳槽中。刚刚参加完微软西雅图的面试,来分享一下自己的面试过程。一共7轮面试,其中1轮电面,6轮Onsite。 第一轮 电面1 第一轮是电面,先是让自我介绍,然后根据简...

abcdd1234567890 ⋅ 2017/06/14 ⋅ 0

面试--字符串中去掉多余的空格

上周jd面试中,面试官出了一道题--去掉字符串中多余的空格,如"abc ert gg e dkhi"中,ert和gg之间有多余的空格,去掉空格变为"abc ert gg e dkhi"。要求:不能用系统函数,不能新建空间。(...

混绅士 ⋅ 2014/07/31 ⋅ 0

30个常见的大数据面试题 让你的薪资提升一个等级

经历了水深火热的大数据学习,终于拨开云雾见天明了,但你离成功总是还差了一步,那就是拿到大数据工程师的Offer。 在电脑旁奋斗了无数个日夜,代码敲了无数遍,项目整改了无数遍,只为了得到...

嘿你好夏天 ⋅ 04/26 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

两道面试题,带你解析Java类加载机制

在许多Java面试中,我们经常会看到关于Java类加载机制的考察,例如下面这道题: class Grandpa{ static { System.out.println("爷爷在静态代码块"); }} cl...

1527 ⋅ 19分钟前 ⋅ 0

SpringCloud(Data Flow)

dataflow-server

赵-猛 ⋅ 30分钟前 ⋅ 0

深入理解Java虚拟机

这本书我读到第8章,之后就是在读不下去了。 读到后面是一种痛苦的体验,太多的东西是不全面的,大量的专有名词是没有解释的,读到最后很多东西仅仅是一个侧面,所以我觉得,这本书不适合初学...

颖伙虫 ⋅ 35分钟前 ⋅ 0

B树和B+树的总结

B树 为什么要B树 磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的...

浮躁的码农 ⋅ 38分钟前 ⋅ 0

NanoPi NEO core/ Ubuntu16.04单网卡配置3个IP地址(2个静态,1个动态)

配置 root@NanoPi-NEO-Core:/etc/network# cat interfacesauto loiface lo inet loopbackallow-hotplug eth0iface eth0 inet static address 172.31.188.249 netmask 255.......

SamXIAO ⋅ 今天 ⋅ 0

三步为你的App集成LivePhoto功能

摘要:LivePhoto是iOS9新推出的一种拍照方式,类似于拍摄Gif图或录制视频片段生成图片。如果没有画面感,可以联想《哈利波特》霍格沃茨城堡的壁画,哈哈,很炫酷有木有,但坑爹的是只有iphone6S以...

壹峰 ⋅ 今天 ⋅ 0

centos7 git安装

由于centos中的源仓库中git不是最新版本,需要进行源码安装。 1、查看yum仓库git信息 [root@iZm5e3d4r5i5ml889vh6esZ zh]# yum info gitLoaded plugins: fastestmirrorLoading mirror s...

xixingzhe ⋅ 今天 ⋅ 0

input file 重复上传同一张图片失效的解决办法

解决办法 方法一:来回切换input[type='file']的type属性值,可以是‘text’,'button','button'....,然后再切换回来‘file’ 方法二:每次取消图片预览后,重置input[type='file']的value的...

时刻在奔跑 ⋅ 今天 ⋅ 0

Mahout推荐算法API详解

前言 用Mahout来构建推荐系统,是一件既简单又困难的事情。简单是因为Mahout完整地封装了“协同过滤”算法,并实现了并行化,提供非常简单的API接口;困难是因为我们不了解算法细节,很难去根...

xiaomin0322 ⋅ 今天 ⋅ 0

WampServer默认web服务器根目录位置

安装WampServer之后的web服务器根目录默认位置在WampServer安装目录下的www:

临江仙卜算子 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部