去哪儿网面试题:对100亿行数据排序

一个文本文件里面有100亿行无序的数据,将这些数据从小到大排列并输出前100个数据。

http://www.manong1024.com/q/205

0

4个回答

这是典型的bitmap排序。也就是创建一个4294967296元素的数组,然后遍历这100亿数据,如果某个数据等于12,就让数组下标为12的那个元素+1,以此类推。
最后从数组0开始输出,如果这个元素对应的值是1,就输出1次,如果是2就输出2次,直到100为止。

0

如果用bitmap排序,那有重复数据怎么办

0
caozhy
贵阳挖掘机马善福,自备车辆专业挖游泳池 重复没有关系。每个数组元素用一个int表示,可以让它累加。如果超过了int的上限,置-1,然后用一个稀疏字典存储。
4 年多之前 回复

你只取小端的 100 个数据,所以只需开辟 100个元素的链表就可以了
遍历这100亿数据,有序的插入结果链表(溢出时丢弃)

0

位图隐射,然后遍历。
回或者小根堆

0
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
大数据算法面试:1亿数据在有限内存上如何排序
相信大家或多或少都看过一些算法类的面试题,其中比较常出现的就有大数据排序问题。因为目前的内存仍无法处理TB级的数据,只能通过不同的算法优化以及I/O来进行尽可能快速的排序。对于这类题目,我总结了以下几种排序方法,同时也提出了自己的一些疑问,希望大家可以一起讨论。这里只讨论nlogn级别的算法,其他的不列入讨论范围。题型:亿级别数据(同型且有重复),统计其中出现次数最多的前N个数据两种情况:可一次读...
一亿条数据的排序处理
假设场景:rn某大型网站,活跃用户上亿个。(当然不是指同时在线人数,这里指的是再一段时间内有访问操作的用户数量,比如一个小时内)。rn现在要每隔1小时,统计一次活跃用户排行榜(用户点击本网站的一个连接,活跃度就加1,按活跃度进行排名)。rnrnrn首先,在此场景下,解决此问题不涉及数据库操作(也不可能用户点击一下,就更新一下数据库!),访问记录就是记录在日志文件中,例如:rnzhangsan, h
大数据算法:对5亿数据进行排序
0.前言:nn在大数据研究的路上,我们总要对一些很大的数据进行各种各样的操作。比如说对数据排序,比如说对数据统计,比如说对数据计算。而在大量的数据面前,我们总是束手无策,因为我们无法在限定时间的情况下,在效率上做到让人满意,也无法在限定空间的情况下,能够快速解决问题。可能我们在一些日常的开发过程中,没有遇到过这些问题。不过,现在是时候来考虑一下这样的问题了。因为,现在正值大数据的时代。nn在本文中...
hive中数据排序
(1)order by对全局数据的排序,只有一个reduceselect * from emp order by id desc;(2)sort by对每个reduce内部数据进行排序,对于全局数据结果来说不是排序的。//设置reduce的个数nset mapreduce.job.reduces=3;nselect * from emp sort by id desc;(3)distribute b
对含有一亿数据的大文件进行排序,要求使用内存小于32MB
大文件排序nn题目:有10个文件,每个文件有1000万行,文件内容的每一行为一个整型数字;需要,写一个程序,将所有数字排序,分为10个文件输出,如0号文件包含前1000万个数字,1号文件文件包含1千万-2千万之间的数字,依次类推。n限制:如果使用java,-Xmx需要设置为32MB;其它语言也需限制内存为32MB。 要求:正确输出 使用多线程加分编写时长:24。n小时。提供可运行的程序,以及实现说...
如何排序10亿个数--外排小试
0.思路10亿个32位整数需要4G左右的内存,一次性载入内存是不现实的,必须要采用外排。第一次接触,当然是从最简单的办法入手。 我们可以利用大容量的外存作为中转,将10亿个数切分成小块,每一块排序好后写入外存。 n切分完成后,对这些小块进行归并排序。同时在归并排序过程中,获得最大(小)值将实时写入文件,这样就可以保证低内存占用。n 注:下面的例子为升序排序n1.切分10亿个数假设’billion’
如何给1000万条记录排序,每条记录都是7位的整数
1. 问题描述rn输入: 一个最多包含n个不重复的正整数的文件,其中每个数都小于n,每个数是一个7位的整数, n=10^7。rn条件: 最多有1MB的内存可用, 排序最多只允许执行几分钟,10s是比较理想的运行时间.有充足的磁盘存储空间可用.rn输出: 按升序排列的输入整数的列表.rn2. 解决方案rn2.1 归并排序rn由于内存的限制, 只能采用多路归并的方法来解决这个问题.rn排序方法; 把这
去哪儿测试工程师笔试面试总结
10月10号参加了去那儿的笔试,参加笔试的人非常多,有种参加联考的感觉。n笔试统一一套卷子,前三道是编程题,其中前两道题是研发类必做题。后面的题目是针对不同的开发职位选做的。由于本人技术基础不是特别扎实。只做了前两道必做题和测试类题目。下面看题目:n1.把“welcome to qunar”转换为“Welcome To Qunar”单词之间以“\t,\n,\r,\v”分隔。n2.从20万个酒
大量数据如何排序
数据量很大的排序问题rnrnhttp://blog.csdn.net/guyuealian/article/details/51151674
2017去哪儿网前端面试心得
第一次面试,还专门租了一身正装,紧张满满的去参加面试了。结果到了酒店发现只有我一个人穿了正装,这个尴尬啊!nnn由于提前到了20分钟,于是等了10分钟后有负责人让我去27楼开始一面。找到房间后,面试官是一个中年男子,面试官:数据结构和算法学的如何?我:学的还可以,一些常用的排序算法比较熟练。很自然的,他让我手写快速排序,由于事先有准备,大概5分钟我就写出来了。大概是我写的快速排序不是网上的常
10亿个IP地址排序、10亿年龄排序
(一).nn注意:IPV4 的IP地址2^32位约42亿个,占空间4Gnn(二).哈希函数nn1.哈希函数即散列函数nn哈希函数的输入域可以是非常大的范围,但是输出域是固定范围。nn2.哈希函数的性质:nna.典型的哈希函数都有无线的输入值域 nb.输入值相同时,返回值相同,返回值即哈希值 nc.输入值不同时,返回值可能一样,也可能不一样 nd.不同输入值得到的哈希值
去哪儿网前端面试
通知的下午五点二十去现场面,然后可能人比较多,等到六点多去面试。还是常规的自我介绍 n1. 看我介绍还不错,说难度升高一些问,先是问一个二叉树?有神特点 n2. 主要二叉树解决什么问题? n3. 数据库索引了解吗? n4. 平衡二叉树了解吗? n5. 看我答得不是特别理想,说降点难度。jQuery源码整体架构是怎么样的? n4. 讲一讲你熟悉的一部分jQuery源码(当时说的是延迟对象和回调对象)
记:去哪儿网前端面试失败的惨痛经历~~
首先,感谢去哪儿网给我这次笔试的资格,楼主不是211、985.有幸通过笔试~好吧,废话不多说 直接进入正题本来安排下午五点,但是楼主接到了一个神秘电话知道了人少,所以下午早早的就去了,大概三点半吧到达面试所在的酒店。。。。。。 n首先进行签到,知道前面还有一位,排队大概等了几分钟吧就到楼主了,楼主很紧张啊 毕竟第一次面试。。。。。。 n指路的小哥哥告诉楼主在21。。。。。。上面有2001.2002.
10G数据,1G内存排序问题
将数据切分成n段,保证每段数据的大小在内存中放得下,然后将n个段的数据放到n个节点上进行并行计算,对计算的结果做多路归并,或者维护一个大小为n的小根堆,第一次从n个数据段中取第一个数据放入堆中,然后拿出最小的元素放入最终的文件中,然后从刚才从堆中取出值的文件中再取一个值,循环,直到将所有的数据排完。但是这样做存在一个问题,每次从n段文件中取数据比较耗时,这些数据可能来自于网络传输或者文件,通常可以...
堆排序实现百万级数据取若干数量的最大数字(java)
      这些天看到了一道题,是一道比较出名的面试题,题目字面上比较简单。      输入若干个float数字(百万级以上) ,编写一个算法从中取出指定数量(100个以内)的最大的数字。      我们先分析一下这道题,从一堆数字里取出几个最大的数,以我们通常的思想去考虑,首先想到的是对这堆数字进行倒序排序,取出前几个就是我们要的结果,这样实现是没错的。可是注意看括号中的注释,输入的数字量级是百...
海量数据面试题(位图、布隆过滤器、哈希切割)
对于处理海量数据,内存中放不下的数据一般有两种方法: n1.考虑特殊数据结构(位图、布隆过滤器) n2.切割(哈希切割、平均切割) n对于这类问题可以画图+文字+伪代码说明问题。 n一:哈希切割topK问题: n给一个超过100G大小的log file,log中存放着IP地址,设计算法找到出现次数最多的IP地址?如何找到top K的IP? n对于本题采用哈希切割: n n二:位图应用: n**给定...
阿里笔试:去重和排序,重新输出Markdown格式
#include n#include n#include n#include n#include nnnusing namespace std;nnint main()n{n string str;n map j_1_mp, j_2_mp, content;n while (cin >> str)n {nn if (str[0] == '#'&&str[1] != '#')n {
Pandas100秒处理一亿行数据
Python数据处理心得--Pandas100秒处理一亿行数据nnn1. 背景-为啥要用pandasn公司的日常运营数据通过大数据平台(HIVE SQL)通过汇总后,推送给业务部门进行日常分析的数据仍然非常大。从数据量从PB&TB级降到了GB级,一般主要通过Mysql进行存储&聚合分析。n日或周的数据,mysql处理还是可以的。到月数据,超过10GB(1亿行),处理起来就开始吃力,数据吞
100亿个整数,找出中位数
100亿个整数,内存足够,如何找到中位数?内存不足,如何找到中位数?n(1)当内存足够时:采用快排,找到第n大的数。n • 随机选取一个数,将比它小的元素放在它左边,比它大的元素放在右边 n • 如果它恰好在中位数的位置,那么它就是中位数,直接返回 n • 如果小于它的数超过一半,那么中位数一定在左半边,递归到左边处理(还是第几大) n • 否则中位数一定在右半边,根据左半边的元素个数
java -- 超大量数据排序
njava -- 超大量数据排序rn rn可以参考下别人的方法:rnhttp://mp.weixin.qq.com/s/K94xtyTA50vU6UGG_ho23Qn
mysql一亿条数据如何排序存储到另外一张表
1、分治nn2、字典树nn字典树是可以压缩数据量的一种数据结构n
去哪儿网2019秋招笔试题
1.题目描述: n给出一个由[-100,100]之间整数组成的数组,求其相加和最大的连续子数组nn输入 n一个连续整数组成的数组nn输出 n子数组相加的最大值nn样例输入 n-1 2 3 -2 4 -6 n样例输出 n7nnnn2.题目描述: n骑士只能在3X2的格子中以对角线的形式走,给定棋盘的大小为8x8,题目输入起点和终点,求骑士从起点走到终点所需的最少步数。nn为了简化题目,将棋盘上的64...
阿里中间件笔试题---大数据排序
一,题目概要nn题目:有10个文件,每个文件有1000万行,文件内容的每一行为一个自然数;需要,写一个程序,将所有数字排序,分为10个文件输出,如0号文件包含前1000万个数字,1号文件文件包含第1千万-2千万之间的数字,依次类推。nn限制:如果使用java,-Xmx需要设置为32MB;其它语言也需限制内存为32MB。nn要求:正确输出使用多线程加分nn编写时长:24小时。提供可运行的程序,以...
JAVA快速排序——亿级体量数据
算法真的是太强大了,今天测试了给一亿个随机数据进行排序,花了67秒不到!不多说,直接见代码:rnrnrnrn  import java.util.Random;rnrnrnrnpublic class sort {rn   rnrnrn    public static void main(String[] args) {rn        rn       rn        int[] dat
设计一个100亿计算器
题目:请设计一个100亿计算器:实现步骤:实现代码:nimport java.util.ArrayList; nimport java.util.regex.Matcher; nimport java.util.regex.Pattern; public class MyBigInteger { n private char sign = '0'; // 0 表示正数 - 表示负
BAT面试题:解决有40亿数据,新增加数据是否重复问题
今天偶然看到一篇文章,说的是BAT的面试题,面试官问有40亿数据在文件中,当在进来一个数据的时候,这个数据是否在40亿数据里存在,本人本着,好奇的心去看了一下。当然没有看他所给的答案,自己解答了一下,下面请看思路:nn首先很多人能够想到的是,40亿数据需要多大的内存,nn40 * 10^8 * 4B = 16GB (大约值,因为不是按照2的幂来做单位换算)咱们来做一下计算nn假设用 2 GB的内存...
超大数据量排序
美团电话面试题:10亿个short类型的数在内存有限的机器上排序。两种思路分享:1.计数排序;2.分而治之
100亿个数字找出最大的10个
1、首先一点,对于海量数据处理,思路基本上是确定的,必须分块处理,然后再合并起来。rnrn2、对于每一块必须找出10个最大的数,因为第一块中10个最大数中的最小的,可能比第二块中10最大数中的最大的还要大。rnrn3、分块处理,再合并。也就是Google MapReduce 的基本思想。Google有很多的服务器,每个服务器又有很多的CPU,因此,100亿个数分成100块,每个服务器处理一块,1亿...
去哪儿网前端面试题-附答案
题目地址:https://www.cnblogs.com/jarson-7426/archive/2014/09/23/3989208.htmlnn1.写一个函数padstare(string str1,min_lenthg,string str2),然后就是用英文解释每个参数的意思,看了半天没看懂,然后看了下他的示例,一下就明白了。nn例:padstare(‘5’,3,‘0’)返回的是‘005’...
[京东面试问题] 求n=100w个数里面的前k=100个
# 基本思路rn  最复杂的方法莫过于全部排序, 复杂度nlgn. 结合求100w个数里面最大的一个数(即求max), 不需全排序, 只需开一个变量, 遍历一次记录最大值即可.那么很自然的想到, 求前k个就是开一个k大小的数组, 把历史最大/次大/次次大存起来. 也就是说, 在遍历n的时候, 对于新元素需要和k数组进行对比, 最差的方式是每次遍历k, 总体复杂度在n*k. 如果k数组是已排序的,
一亿以上数据几种排序算法运行时间比较
一亿以上数据几种排序算法运行时间比较rn运行结果如下图(单位ms)rnrnrninsert:只排了8万及以下数据rnheap:参考算法导论,maxHeapify采用迭代取代递归rnshell:增量递减序列采用1/2(3k−1)1/2(3^k-1)1/2(3k−1)形式rnshell-IS:Incerpi-Sedgewick提出的增量递减序列rn[ 1391376, 463792, 198768, 86961, 3...
去哪儿网面试 -- HR面跪了
前几天去西安邮电笔试,三道程序题。昨天早上去 去哪儿网 面试,一共两轮技术面,一轮hr面。3个小时内面完。nn         一面:nn        自我介绍。nn        进程通信方式,sql语句优化,数据库索引内部原理,两个算法题。nn        然后根据项目问了数据挖掘和搜索引擎的知识。nn        面完的时候才知道面试官是无线端搞数据挖掘和搜索引擎的
[原创]从1亿个数据中找出前100个最大值
从一亿个数据中找出前100个最大值nn方法一:nn> 新建一100个红黑树节点,将输入前100个保存进去,然后全部插入红黑树Tnn> 遍历剩下的所有输入,对每一个输入值,如果值大于红黑树中最小值,则删除最小值节点,然后修改被删除节点的值为当前输入,然后插入红黑树。nn复杂度为n*lg(m), n为输入数据条数,m为输出数据条数nn方法二:将红黑树替换成最小堆,每插入一条数据,只需要运行...
求100亿个数的中位数
1、题目描述nn 给定100亿个无符号的乱序的整数序列,如何求出这100亿个数的中位数(中位数指的是排序后最中间那个数)。nn2、解题思路一nn 一个无符号整数的大小为4B,则100亿个数的大小为40GB,如果内存够大的话可以对这100亿个数加载到内存中,然后使用堆排序或者快速排序进行排序,取出中位数即可。使用快排时,每次划分之后只需要比较枢纽值的索引和50亿比较,然后只对两个划分中的...
2019《去哪儿》春季校招第一站(含笔试题)
PS:点进来的小伙伴,我想先声明,标题中的去哪儿指的是517Na这家公司。nn离职已经过去了4天,这几天算是过上了悠闲而轻松的日子。瞌睡也睡了(忘记了早餐存在的价值),篮球也打了(下午一个人在小区里打篮球,唉以前的伙伴已经有更重要的事情要去忙碌了),游戏也玩了(炉石传说输的我卸载了游戏)。nn突然感觉生活都迷失了方向感。不知道该干点什么了。只好重拾起前端书籍,视频看看。借此来打破我这无聊的寂静。n...
100亿数据量1万属性数据库架构设计
诉求 •100亿的数据量 •10万的幵发 •1万属性 •任意字段都可能进行组合查询
去哪儿网校园招聘笔试面试题合集
去哪儿网校园招聘笔试面试题合集....
测试开发面试题
1.删除文件夹及文件夹中的所有内容,即删除文件和子文件夹nn给定一下三个方法,编写方法remove删除文件夹中的所有内容nnnpublic boolean isFile(String path)//判断给定路径是否是文件nnnpublic boolean deleteFile(String path)//删除文件及空文件夹nnnpublic String[] getChild(String pat...
面试题-100万个数据前100大的数据
先取出前100个数,维护一个100个数的最小堆,遍历一遍剩余的元素,在此过程中维护堆就可以了。具体步骤如下: step1:取前m个元素(例如m=100),建立一个小顶堆。保持一个小顶堆得性质的步骤,运行时间为O(lgm);建立一个小顶堆运行时间为m*O(lgm)=O(m lgm); step2:顺序读取后续元素,直到结束。每次读取一个元素,如果该元素比堆顶元素小,直接丢弃 如果大于堆顶元素,则用该元
100亿数据找出最大的1000个数字
100亿数据找出最大的1000个数字
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 大数据基础面试题 ios视频开发的面试题