北京大数据培训
达内北京中关村中心

010-62126400

热门课程

大数据求职必看面试问题

  • 时间:2017-07-28
  • 发布:北京大数据培训
  • 来源:企业面试题

问题一:什么是大数据?

大数据(big data,mega data),或称巨量资料,指的是需要新处理模式才能具有更强的决策力、洞察力和流程优化能力的海量、高增长率和多样化的信息资产。 在维克托·迈尔-舍恩伯格及肯尼斯·库克耶编写的《大数据时代》中大数据指不用随机分析法(抽样调查)这样的捷径,而采用所有数据进行分析处理。大数据的4V特点:Volume(大量)、Velocity(高速)、Variety(多样)、Value(价值)。

问题二:给一个超过100G大小的log file,log中存着IP地址 ,设计算法找到出现次数最多的IP地址?

答:

首先看到100G的日志文件,我们的第一反应肯定是太大了,根本加载不到内存,更别说设计算法了,那么怎么办呢?既然装不下,我们是不是可以将其切分开来,一小部分一小部分轮流进入内存呢,答案当然是肯定的。

在这里要记住一点:但凡是大数据的问题,都可通过切分来解决它。

粗略算一下:如果我们将其分成1000个小文件,每个文件大概就是500M左右的样子,现在计算机肯定轻轻 松松就能装下。

那么,问题又来了,怎样才能保证相同的IP被分到同一个文件中呢?

这里我想到的是哈希切分,使用相同的散列函数(如 BKDRHash)将所有IP地址转换为一个整数key,再利用 index=key%1000就可将相同IP分到同一个文件。

依次将这1000个文件读入内存,出现次数最多的IP进行统计。

最后,在1000个出现次数最多的IP中找出最大的出现次数即为所求。

用到的散列函数:

问题三:与上题条件相同,如何找到TOP K的IP?

答:

这倒题说白了就是找前K个出现次数最多的IP,即降序排列IP出现的次数。

与上题类似,我们用哈希切分对分割的第一个个小文件中出现最多的前K个IP建小堆,

然后读入第二个文件,将其出现次数最多的前K个IP与 堆中数据进行对比,

如果包含大于堆中的IP出现次数,则更新小堆,替换原堆中次数的出现少的数据

再读入第三个文件,以此类推……

直到1000个文件全部读完,堆中出现的K个IP即是出现 次数最多的前K个IP地址。

问题四:给定100亿个整数,设计算法找到只出现一次的整数 ?

答:

看到此题目,我的第一反应就是估算其占用内存的大小:100亿个int,一个int4个字节,100亿*4=400亿字节

又因为42亿字节约等于4G,所以100亿个整数大概占用的内存为40G,一次加载到内存显然是不太现实的。

反过来想,所有整数所能表示的范围为2^32,即16G, 故给出的数据有很多数据是重复的。

解法1:哈希切分

与第一题类似,用哈希切分将这些数据分到100个文件 中,每个文件大约400M,将每一个文件依次加载到内存中,利用哈希表统计出现一次的整数,将100个文件中出现一次的整数汇总起来即为所求。

解法2:位图变形

我们知道,位图是利用每一位来表示一个整数是否存在来节省空间,1表示存在,0表示不存在。

而上题对于所有整数而言,却有三种状态:不存在、 存在一次、存在多次。

故此,我们需要对传统位图进行扩展,用两位来表示一个整数的状态:00表示不存在、01表示存在一次, 10表示存在多次,11表示无效状态。

按照上述表示,两位表示一个整数状态,所有整数只需要1G即可表示其存在与否。

解法3:

众所周知,一个整数占32位,那么我们可对每一位按照0和1将其分为两个文件,直到划分到最低位,如果被分的文件中哪个文件只包含一个数据,那么,此数据即为只出现一次的整数。

如下图:

给两个文件,分别有100亿个整数,我们只有1G内存 ,如何找到两个文件交集?

答:100亿*4字节 = 400亿字节 = 40G

解法1:普通查找

将其中的一个文件分为100个小文件,每一份占400M, 将每一小份轮流加到内存中,与第二个文件中的数据进行对比,找到交集。此种算 法时间复杂度为O(N*N)。

解法2:哈希切分

对两个文件分别进行哈希切分,将其分为100个小文件 ,index=key%100(index为文件下标)。

将两个文件中下标相同的小文件进行对比,找出其交集。将100个文件的交集汇总起来即为所给文件的文件交集 。此种算法时间复杂度为O(N)。

上一篇:没有上一篇了
下一篇:数据挖掘面试题总结
选择城市和中心
贵州省

广西省

海南省