博客访问： 80691
博文数量： 58
博客积分： 0
博客等级： 民兵
技术积分： 600
注册时间：
认证徽章：
从linux了解世界
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： Java
大数据处理：(求最大的n个用小根堆，最小的n个用大根堆)
使用mapreduce统计文章中单词出现个数，首先对文章预处理，去掉标点，对连字符-处理，对缩写处理，大小写转换。然后对每个单词进行hash映射，假设映射为10组，对每组中同一种单词进行合并，然后把每组的结果进行合并。
对40亿的ip地址进行排序，每个ip只出现一次可以用bitmap，该map单元个数2的32次方，每个单元只占1bit。jdk1就有了bitset类，但是其中有些方式是jdk4才有的，线程不安全。
有一个包含20亿个全是32位整数的大文件，在其中找到出现最多的数，内存限制2g。对20亿个数使用哈希函数分流，假设分成20个小文件，对每个小文件使用hashmap得到出现最多的数，再从20个文件的20个最多的数中选出最多的。
32位无符号整数最大为42亿多，有一个包含40亿个无符号数的文件，所以必然在32位整数的范围中有没出现的数，最多使用10m内存找到任意一个没出现过的数。可以将42亿的范围分成64个区间，将大文件分成64个小文件，小文件中不足2的32次方/64就说明在该区间有没出现的数。用bitmap统计该区间上的数的出现情况
百亿数据中找到出现最多的100个。同样使用hash函数分流成假设64个子文件，对每一个子文件统计每个数据的次数，然后利用小根堆进行top100的筛选。
工程师常使用服务器集群来设计和实现数据缓存，将数据的id通过哈希函数转换成哈希值，为key。如果机器有n台，key%n就是该数据所属机器的编号。分析这种缓存策略可能带来的问题，并提出改进方案。增加或者删除机器时，数据迁移的代价很大。用一致性哈希算法解决。从0到2的32次方成环，每个数据的key都对应在环中。根据机器id计算出的hash值也在该换中，数据的哈希值顺时针碰到的第一个机器id哈希值，就是对应的机器。
布隆过滤器：使用k个哈希函数对每个要过滤数据，在m范围的bitmap内进行映射。当其它数据经过布隆过滤器的k个哈希函数映射时，每个映射在之前的bitmap中都有，则说明该数据应该被过滤。
PS：全部内容来自牛客网左老师的讲座
阅读(805) | 评论(0) | 转发(0) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。想进入大数据领域？先了解这几个常见的大数据面试题
(window.slotbydup=window.slotbydup || []).push({
id: '2611110',
container: s,
size: '240,200',
display: 'inlay-fix'
您当前位置： &
[ 所属分类
| 时间 2017 |
作者 红领巾 ]
　　现在全国各省正处于招聘的高峰期，面试者也越来越紧张，都希望有高人指点一二，倘若有面试题能提示一下，那面试能拿到offer的机会便大的多，下面就是一些常见的大数据面试题，希望能帮助你们一二:　　在说整体之前，我们先了解下大数据，曾经哈佛大学社会学教授加里·金(崇拜/崇拜)说：“这是一场革命，庞大的数据资源使得各个领域开始了量化进程，无论学术界、商界还是政府，所有领域都将开始这种进程。”　　百度百科也说过大数据对现在社会的影响是这样概述的：　　随着云时代的来临，大数据(Big data)也吸引了越来越多的关注。大数据(Big data)通常用来形容一个公司创造的大量非结构化和半结构化数据，这些数据在下载到关系型数据库用于分析时会花费过多时间和金钱。大数据分析常和云计算联系到一起，因为实时的大型数据集分析需要像MapReduce一样的框架来向数十、数百或甚至数千的电脑分配工作。　　看到这，你是不是觉得大数据真的很神奇也很厉害，也许你肯定会想大数据肯定很难，但不要被这些吓到了：　　咱们接下来说说一些大数据面试常见的面试题：　　1、你处理过的最大的数据量?你是如何处理他们的?处理的结果。　　2、在处理大数据过程中，如何保证得到期望值?　　3、如何让一个网络爬虫速度更快、抽取更好的信息以及更好总结数据从而得到一干净的数据库?　　4、点击流数据应该是实时处理?为什么?哪部分应该实时处理?　　5、你最喜欢的编程语言是什么?为什么?　　6、如何把非结构化的数据转换成结构化的数据?这是否真的有必要做这样的转换?把数据存成平面文本文件是否比存成关系数据库更好?　　7、如何判别mapreduce过程有好的负载均衡?什么是负载均衡?　　8、Spark和Hive的区别，以及Spark和Hive的数据倾斜调优问题?　　9、Hive和Hbase的区别?　　10、MapReduce的思想，以及MapReduce调优问题?　　11、你所了解的开源网站?　　12、有两个集群，每个集群有3个节点，使用hive分析相同的数据，sql语句完全一样，一个集群的分析结果比另外一个慢的多，给出造成这种现象的可能原因?　　13、Hbase的优化?　　14、集群的版本，以及集群的瓶颈问题?　　15、CRM项目，怎么跟Spark结合?　　16、如何创建一个关键字分类?　　17、海量日志数据，提取出某日访问百度次数最多的那个IP?　　18、Hadoop和Spark处理数据时，出现内存溢出的处理方法?　　19、有一个1G大小的一个文件，里面每一是一个词，词的大小不超过16字节，内存大小限制大小1M，返回频率最高的50个词。　　20、你是如何处理缺少数据的?你是推荐使用什么样的处理技术，或者说你是用什么样的技术处理呢?　　. . . . .　　问题的数量要比你想象的多的多，但是这些问题都是可以通过学习或者是工作经验得到解决方法，真正的强者都是不会被这些给吓到的，小编相信你的可以的!
转载请注明本文标题：本站链接：
分享请点击：
1.凡CodeSecTeam转载的文章,均出自其它媒体或其他官网介绍,目的在于传递更多的信息,并不代表本站赞同其观点和其真实性负责；
2.转载的文章仅代表原创作者观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,本站对该文以及其中全部或者部分内容、文字的真实性、完整性、及时性，不作出任何保证或承若；
3.如本站转载稿涉及版权等问题,请作者及时联系本站,我们会及时处理。
登录后可拥有收藏文章、关注作者等权限...
CodeSecTeam微信公众号
决定你人生高度的不是你的才能，而是你的态度！
手机客户端大数据：面试题总结(1)
1、给出一个超过100G的log file，log中存着ip地址，设计算法找到出现次数最多的ip地址?
由于文件超过100G，所以我们必须先对文件进行切分，然后再利用数据结构的知识求解。关键是如何切分效率最高？？？
解决方法：
我们可以使用哈希切分，将同一个ip都分割到同一个文件中，注意同一个ip经过同一个散列函数 一定会进入到同一个文件中，然后再统计每一个文件中出现最多的ip的次数，最后再将这些结果放到一起再经过比较就能得出结果。
最极端的情况是经过哈希切分后有一个ip出现次数特别多，切分后存放这个ip的文件还是太大加载不到内存中，这时候应该怎么办呢？？？
这时候可以将这个文件再切分(普通的切分)成若干个小文件，将每一个文件加载到内存中使用hash表求出ip出现的次数，最后再将这些小文件的结果汇总后在求出出现次数最多的ip。
2、与上题条件相同，如何找到top K的ip?
与第1题一样，我们统计出每个文件中每个ip出现的次数然后再利用最小堆分别求出每个文件中出现次数最多的前k个ip，最后再将这些文件的结果汇总到一起再利用最小堆求出出现次数最多的前K个ip。
3、给定100亿个整数，设计算法找到只出现一次的整数？
分析：100亿个整形大约需要40G才能存下，一次性读入到内存中是不现实的。
方法1：切分文件+数据结构
把这100亿个整数分成100份，这样算下来平均每份大约占400M左右。再把每一份加载到内存中，使用哈希表进行查找只出现一次的数，最后再将这100份的结果汇总到一起再进行查找。
方法2：bitmap
对于这个题，需要对位图做一点扩展，因为这些数有可能出现0次、1次、多次，只用一个bit位是无法表示的，所以我们需要用两个bit位来表示一个整数的存在状态即：00表示没出现，01表示只出现1次，10(或11)表示出现多次。
因为整型大约能表示42亿9千万个数，至少要16G才能存下这些数字，如果换成两个bit位表示的话只需要1G的内存就足够了。因为这些整数有可能有负数，所以我们可以将负数映射到位图的后半部分，也就是将这些负数当做无符号的数看待。
bitmap:http://blog.csdn.net/lf_2016/article/details/
整数有32位，我们先按最高位0和1将这些数据划分成两个数据，然后拿要查找的数的最高位比较看要去哪个文件中找，一次类推，直到划分到最低位。这样的话最多进行32次划分就能判断出这个数在不在这100亿个整数里面。
4、给定两个文件，分别有100亿个整数，只提供1G内存，如何找出两文件交集？
分析：100亿个整形大约需要40G才能存下，一次性读入到内存中是不现实的。
把一个文件切分成100份，分别把每一份加载到内存中，然后用第二个文件中的数据到每一份中都进行查找。这种方法的时间复杂度是O(N^2)。
方法2：哈希切分
先对一个文件进行切分，不过这次切分的时候使用一个散列函数，将相同的数都分割到一个文件中去，注意相同的数一定会进入同一个文件，并给这些文件进行编号。再对第二个文件中的数据也使用这个散列函数，并给切分后的文件也进行编号。最后，如果两个文件有交集的话，一定会在编号相同的文件中产生交集，这时候只需要把他们编号相同的文件进行比较即可。这种方法的时间复杂度是O(N).
方法3：bitmap
将一个文件中的数据映射到位图中(大约需要500M)，然后再用第二个文件中的数据到位图中去寻找。这种方法的时间复杂度是O(N)。
bitmap: http://blog.csdn.net/lf_2016/article/details/
5、给定两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件的交集？分别给出精确算法和近似算法？
精确算法:哈希切分
如果要得到精确的结果的话，我们可以使用哈希切分，第四题的方法2是一样的，不过在这个题中要将query转换成一个整形，然后再经过散列函数映射到文件中去。
近似算法:bloomfilter(布隆过滤器)
如果要得到近似结果的话可以使用布隆过滤器，将其中一个文件的内容映射到位图中，然后再用另一个文件中的内容到这个位图中寻找。
BloomFilter: http://blog.csdn.net/lf_2016/article/details/
6、如何扩展BloomFilter使得它支持删除操作？如何扩展BloomFilter使得它支持计数操作？
要支持删除操作，就要用到引用计数的方法。不用一个bit位表示一个数据，该用size_t表示一个数。
BloomFilter: http://blog.csdn.net/lf_2016/article/details/
7、5亿个整数找它们的中位数，只有1G内存。
5亿个整数大约需要2G的内存才能表示的下。我们可以先对整数划分若干个区间，然后每个区间都建立一个小文件，再遍历这个大文件，将里面的数按照大小放到相应的小文件中，最后我们只要统计出每个文件中整数的个数，就可以计算出中位数的位置。
8、有一个词典，包含N个英文单词，现在任意给一个字符串，设计算法找出包含这个字符串的所有英文单词？
方法:字典树
首先把这N个英文单词建立一颗字典树，然后再用给定的字符串到字典树中去找，如果找到就是存在的，找不到就是不存在的。但是如果字典树的深度比较深的话是比较耗费内存的，这时候我们可以使用&字典树+hash表&的方式解决，例如:我们将字典树第10层以后的数据存放到hash表里面。
对于大数据问题，一般都采取分而治之的方法，即：对数据进行分割，之后再利用数据结构的知识求解。可以说这种方法是能够解决绝大多数大数据问题的，但是重点是我怎么划分，有时候如果划分合理的话，就能够极大的提高解决问题的效率。
此外针对某些大数据问题还有其它更优的解决办法，比如bitmap、bloomfilter、Trie树等，所以针对具体问题我们要具体分析，看哪一种方法更优。
针对大数据问题百试不爽的方法就是：切分+数据结构。查看: 114982|回复: 33
hadoop、大数据笔试、面试都会问那些问题
主题帖子积分
本帖最后由 pig2 于
23:41 编辑
1、hdfs原理，以及各个模块的职责
2、mr的工作原理
3、map方法是如何调用reduce方法的
4、shell如何判断文件是否存在，如果不存在该如何处理？
5、fsimage和edit的区别？
6、hadoop1和hadoop2的区别？
1、hdfs中的block默认保存几份？
2、哪个程序通常与nn在一个节点启动？并做分析
3、列举几个配置文件优化？
4、写出你对zookeeper的理解
5、datanode首次加入cluster的时候，如果log报告不兼容文件版本，那需要namenode执行格式化操作，这样处理的原因
6、谈谈数据倾斜，如何发生的，并给出优化方案
7、介绍一下hbase过滤器
8、mapreduce基本执行过程
9、谈谈hadoop1和hadoop2的区别
10、hbase集群安装注意事项
11、记录包含值域F和值域G，要分别统计相同G值的记录中不同的F值的数目，简单编写过程。
信息技术有限公司
1、你们的集群规模？
2、你们的数据是用什么导入到数据库的？导入到什么数据库？
3、你们业务数据量多大？有多少行数据？(面试了三家，都问这个问题)
4、你们处理数据是直接读数据库的数据还是读文本数据？
5、你们写hive的hql语句，大概有多少条？
6、你们提交的job任务大概有多少个？这些job执行完大概用多少时间？(面试了三家，都问这个问题)
7、hive跟hbase的区别是？
8、你在项目中主要的工作任务是？
9、你在项目中遇到了哪些难题，是怎么解决的？
10、你自己写过udf函数么？写了哪些？
11、你的项目提交到job的时候数据量有多大？(面试了三家，都问这个问题)
12、reduce后输出的数据量有多大？
主题帖子积分
高级会员, 积分 1333, 距离下一级还需 3667 积分
高级会员, 积分 1333, 距离下一级还需 3667 积分
对于自学和找工作而言，非常有帮助！
主题帖子积分
注册会员, 积分 130, 距离下一级还需 70 积分
注册会员, 积分 130, 距离下一级还需 70 积分
主题帖子积分
中级会员, 积分 675, 距离下一级还需 325 积分
中级会员, 积分 675, 距离下一级还需 325 积分
谢谢& &受用& &&&
主题帖子积分
高级会员, 积分 2697, 距离下一级还需 2303 积分
高级会员, 积分 2697, 距离下一级还需 2303 积分
谢谢，受用了
主题帖子积分
高级会员, 积分 1614, 距离下一级还需 3386 积分
高级会员, 积分 1614, 距离下一级还需 3386 积分
学习中 加油！
主题帖子积分
高级会员, 积分 1000, 距离下一级还需 4000 积分
高级会员, 积分 1000, 距离下一级还需 4000 积分
好好学习啊
主题帖子积分
新手上路, 积分 44, 距离下一级还需 6 积分
新手上路, 积分 44, 距离下一级还需 6 积分
受教了！！！！！！！
主题帖子积分
新手上路, 积分 9, 距离下一级还需 41 积分
新手上路, 积分 9, 距离下一级还需 41 积分
学习中。。。。。。。。。。。。。。。。。。。。。。。。。
主题帖子积分
注册会员, 积分 81, 距离下一级还需 119 积分
注册会员, 积分 81, 距离下一级还需 119 积分
谢谢&&学习学习
积极上进，爱好学习
经常参与各类话题的讨论，发帖内容较有主见
站长推荐 /4
云计算hadoop视频大全(新增 yarn、flume|storm、hadoop一套视频
等待验证会员请验证邮箱
新手获取积分方法
技术类问答，解决学习openstack，hadoop生态系统中遇到的问题
Powered by