`
kmplayer
  • 浏览: 508693 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

一些常见的海量数据处理题目

阅读更多
很长时间没有更新blog了,先唠叨两句.
这段时间发生了几件不大不小的事吧.
(1)工作暂时签tencent了,会不会有变数谁也不知道.也许通向网易的路还没有完全堵死.
(2)javaeye一度居然真的上不去了,于是正在考虑是否该有个新家了.
(3)知道了云风,对网易更加的有爱了.

言规正传,开始正式的内容.

1,给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url?
方案1:
可以估计每个文件安的大小为50G×64=320G,远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

(1)遍历文件a,对每个url求取hash(url)%1000,然后根据所取得的值将url分别存储到1000个小文件(a0,a1,...,a999)中。这样每个小文件的大约为300M。
(2)遍历文件b,采取和a相同的方式将url分别存储到1000各小文件。这样处理后,所有可能相同的url都在对应的小文件(b0,b1,...,b999)中,不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
(3)求每对小文件中相同的url时,可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url,看其是否在刚才构建的hash_set中,如果是,那么就是共同的url,存到文件里面就可以了。

方案2:
如果允许有一定的错误率,可以使用Bloom filter(布隆过滤器)。
4G内存大概可以表示340亿bit,将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。


2,有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照query的频度排序。

方案1:
(1)顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件中。这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。
(2)找一台内存在2G左右的机器,依次对每个文件用hash_map(query, query_count)来统计每个query出现的次数。
(3)利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件。
(4)对这10个文件进行归并排序(内排序与外排序相结合)。

方案2:
一般query的总量是有限的,只是重复的次数比较多而已,可能对于所有的query,一次性就可以加入到内存了。这样,我们就可以采用trie树/hash_map等直接来统计每个query出现的次数,然后按出现次数做快速/堆/归并排序就可以了。

定义一个全局数组: char word[MAXLEN]; word[0] = '\0';
struct node
{
char val;
int cnt;
node* child[26];
}
接口:
void Traverse(node* root, int depth)
{
if (root == NULL)
return;
word[depth] = root->val;
word[depth+1] = '\0';
cout << word << ": " << root->cnt << endl;
for (int i = 0; i < 26; i++)
Traverse(root->child[i], depth+1)
}

3,有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。

(1)顺序读文件中,对于每个词x,取hash(x)%5000 ,然后按照该值存到5000个小文件中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小,还可以按照类似的方法继续往下分,知道分解得到的小文件的大小都不超过1M。
(2)对每个小文件,统计每个文件中出现的词以及相应的频率(可以采用trie树/hash_map等),并取出出现频率最大的100个词(可以用含100个结点的最小堆),并把100词及相应的频率存入文件,这样又得到了5000个文件。
(3)下一步就是把这5000个文件进行归并(类似与归并排序)的过程了。


4,在2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数。

方案:
(1)采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32*4bit=1G字节内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。
(2)所描完事后,查看bitmap,把对应位是01的整数输出即可。

5, 一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。

方案:这题是考虑时间效率。
用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平准长度)。然后是找出出现最频繁的前10个词,可以用堆来实现,前面的题中已经讲到了,时间复杂度是O(n*lg10)。所以总的时间复杂度,是O(n*le)与O(n*lg10)中较大的哪一个
分享到:
评论

相关推荐

    10道海量数据处理题目.zip

    10道海量数据处理题目.zip

    10道海量数据处理题目.pdf

    以下将详细讨论给定文件中提到的四个海量数据处理题目及其解决方案。 1. 提取出某日访问百度次数最多的IP 这是一个典型的分布式计算问题。首先,通过对IP地址取模将海量日志分散到多个小文件中,例如模1000,生成...

    十道海量数据处理面试题

    海量数据处理是互联网公司技术面试中的一个重要环节,它主要考察应聘者处理大规模数据集的能力,以及对各种存储、计算、排序算法的理解和应用。以下针对提供的文件内容,提炼出相关的知识点。 首先,海量数据处理的...

    海量数据处理(互联网公司面试题目)

    海量数据处理是互联网公司面试的题目,因为大的互联网公司需要!

    大数据量_海量数据_处理方法总结

    下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目...

    面试题目-大数据量海量数据处理

    包含各类大数据处理时的面试题目及答案,可参考此文档,对各种大数据处理技术有更深了解。

    IT常见面试题-海量数据处理面试题集锦

    IT常见面试题-海量数据处理面试题集锦,根据实际的面试经验,总结了网上的面试题目,并给出了详细解析

    常用大数据量、海量数据处理方法__算法总结

    大数据量的问题是很多面试笔试中经常出现的问题,比如百度,谷歌,腾讯这样的一些涉及到海量数据的公司经常会问到。 本文的一些问题基本直接来源于公司的面试笔试题目。包括Bloom filter,Hashing,bit-map,双层桶...

    大数据量,海量数据 处理方法总结.pdf

    这些技术是大数据量和海量数据处理的基石,在数据科学、网络分析、搜索引擎优化等众多领域有着广泛的应用。在实际使用过程中,可以根据数据的特性和处理需求灵活选择合适的处理方法,并结合问题实例进一步理解和掌握...

    面试题目-大数据量海量数据处理.pdf

    这些面试题目聚焦于大数据量和海量数据的处理,涵盖了各种挑战,包括数据过滤、去重、排序、频率统计和热门元素提取。以下是对这些题目的详细解析和相关知识点: 1. **URL共现问题**:这是一个典型的集合交集问题,...

    海量 数据 处理 面试题 与 方法大总结

    ### 海量数据处理面试题与方法大总结 ...以上是关于海量数据处理的一些典型面试题目及解决方案的大致介绍。这些方法和技术在实际应用中都非常实用,可以帮助工程师们解决大数据处理中的许多挑战。

    海量数据处理方法总结

    大数据量的问题是很多面试笔试中经常出现的问题,下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。...

    海量数据处理问题汇总及方法总结

    以下是对题目中给出的几种典型海量数据处理问题及其解决策略的详细解析: 1. **查找共同URL**: - 方案1:采用分治策略,将大文件切分为小文件,然后通过哈希函数将URL分散存储,之后对比每对小文件,使用哈希集合...

    十道海量数据处理面试题与十个方法大总结 面试必备

    ### 十道海量数据处理面试题与十个方法大总结 #### 第一部分:十道海量数据处理面试题 **1. 提取某日访问百度次数最多的那个IP** **问题描述**:给定一天内的大量日志数据,需要从中提取出访问百度次数最多的那个...

    数据挖掘的一些题目

    本文总结了五个数据挖掘笔试题目,涵盖了数据处理、排序、统计、频率分析等多方面的知识点。 1. 数据去重复:给定两个文件,各存放 50 亿个 URL,每个 URL 各占 64 字节,内存限制是 4G,要求找出共同的 URL。解决...

    十道海量数据处理面试题与十个方法大总结

    ### 十道海量数据处理面试题与十个方法大总结 #### 第一部分:十道海量数据处理面试题 **1. 海量日志数据,提取出某日访问百度次数最多的那个IP。** - **背景**: 在处理大规模网络日志时,经常需要分析用户行为...

    十道海量数据处理面试题(卷).docx

    这些题目覆盖了海量数据处理的关键技术,包括数据结构(如Trie树、Bloom Filter、Bitset)、排序算法(如基数排序、快速排序)、分布式计算框架(如MapReduce)、空间效率优化(如Top-K、布隆过滤器)等。...

    十七道海量数据处理面试题与Bit-map详解

    ### 十七道海量数据处理面试题与Bit-map详解 #### 第一部分:十五道海量数据处理面试题 **题目一**:给定a、b两个文件,各存放50亿个URL,每个URL各占64字节,内存限制是4GB,让你找出a、b文件共同的URL。 - **...

Global site tag (gtag.js) - Google Analytics