文档章节

一道大数据处理的面试题

YKIT
 YKIT
发布于 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>

本文转载自:

共有 人打赏支持
YKIT

YKIT

粉丝 14
博文 42
码字总数 8404
作品 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
0
2018最新版本的spark面试题及答案

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

嘿你好夏天
04/03
0
0
18届清华硕士狂拿18家互联网公司offer

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

野梦M
2017/12/18
0
1
Java面试题:如何处理大数据,如何在10s内应对10M个用户搜索?

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

文心雕码
2014/02/11
1K
7
大数据面试题,99%会机率碰到的海量题

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

mkkm1314
04/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

你为什么在Redis里读到了本应过期的数据

一个事故的故事 晚上睡的正香突然被电话吵醒,对面是开发焦急的声音:我们的程序在访问redis的时候读到了本应过期的key导致整个业务逻辑出了问题,需要马上解决。 看到这里你可能会想:这是不...

IT--小哥
今天
2
0
祝大家节日快乐,阖家幸福! centos GnuTLS 漏洞

yum update -y gnutls 修复了GnuTLS 漏洞。更新到最新 gnutls.x86_64 0:2.12.23-22.el6 版本

yizhichao
昨天
5
0
Scrapy 1.5.0之选择器

构造选择器 Scrapy选择器是通过文本(Text)或 TextResponse 对象构造的 Selector 类的实例。 它根据输入类型自动选择最佳的解析规则(XML vs HTML): >>> from scrapy.selector import Sele...

Eappo_Geng
昨天
4
0
Windows下Git多账号配置,同一电脑多个ssh-key的管理

Windows下Git多账号配置,同一电脑多个ssh-key的管理   这一篇文章是对上一篇文章《Git-TortoiseGit完整配置流程》的拓展,所以需要对上一篇文章有所了解,当然直接往下看也可以,其中也有...

morpheusWB
昨天
5
0
中秋快乐!!!

HiBlock
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部