一道腾讯面试题:从大量数字中取出 top 100

最近有同事去腾讯面试,其中一个排序算法题:从1亿个数字中取出最大的100个. 我感觉用位图排序是比较合适的.位图排序的特点是用内存空间换取CPU时间.代码如下:

 

import java.util.Random;

 

public class Top100 {

public static int[] getTop100(int[] inputArray) {

 

int maxValue = Integer.MIN_VALUE;

for (int i = 0; i < inputArray.length; ++i) {

if (maxValue < inputArray[i]) {

maxValue = inputArray[i];

}

}

byte[] bitmap = new byte[maxValue+1];

for (int i = 0; i < inputArray.length; ++i) {

int value=inputArray[i];

bitmap[value] = 1;

}

 

int[] result = new int[100];

int index = 0;

for (int i = maxValue; i >= 0 & index < 100; --i) {

if (bitmap[i] == 1) {

result[index++] = i;

}

}

return result;

}

 

public static void main(String[] args) {

int numberCount = 90000000;

int maxNumber = numberCount;

int inputArray[] = new int[numberCount];

Random random = new Random();

for (int i = 0; i < numberCount; ++i) {

inputArray[i] = Math.abs(random.nextInt(maxNumber));

}

System.out.println("Sort begin...");

long current = System.currentTimeMillis();

int[] result = Top100.getTop100(inputArray);

System.out.println(System.currentTimeMillis() - current);

for (int i = 0; i < result.length; ++i) {

System.out.print(result[i] + ",");

}

}

}

 

我的机子是配置是CPU:Intel(R) Pentium(R) M processor 1.60GHZ,512M内存. 运行结果如下

1千万:1.297秒

2千万: 2.906秒

3千万:4.578秒

4千万:6.203秒

5千万:7.875秒

6千万:9.953秒

7千万:11.407秒

8千万:26.921秒

9千万:31.953秒

 

当运行到1亿数据时,机子几乎就没有反应了,这可能是物理内存已经耗尽,用虚拟内存了.

 

欢迎交流!

评论

79 楼 pclfs1983 2010-04-02  

楼主这样做是不对的 ，数据量一大的话，直接内存溢出

78 楼 lwf_software 2010-04-02  

Jameslyy 写道

joeycn 写道

请问这真的是道对亿级数据的排序题吗？
取一百个最大值而已的话，就没那么复杂了吧
先对头一百个数排序， 然后一个个比较，在最大值最小值之外的数直接抛弃，中间值参与二分查找法定位并替换
最后得到的就是要的东西了

应该是这个思路!

------------------------------------------

有那么复杂吗？还扯什么多线程，引用这位的思路正解.昨晚上回家试了下，1亿数据502ms,奔腾T2330 CPU 1.6G,Linux JDK1.6.

77 楼 zoutm 2010-04-02  

1亿个数据，单独用一种数据结构恐怕吃不消，我认为可以这样处理，让1个线程从文件或DB中读一定批量的数据，分配到N个队列，而每个队列有一个相应的线程进行排序，取前100，而每个线程处理好排序后把前N*100个交给另一个独立线程再去处理前100个的排序，有点归并排序的意味

76 楼 ansjsun 2010-04-02  

做一个链表结构..左右链接.....等下给你代码

75 楼 Jameslyy 2010-04-02  

joeycn 写道

请问这真的是道对亿级数据的排序题吗？
取一百个最大值而已的话，就没那么复杂了吧
先对头一百个数排序， 然后一个个比较，在最大值最小值之外的数直接抛弃，中间值参与二分查找法定位并替换
最后得到的就是要的东西了

应该是这个思路!

74 楼 抛出异常的爱 2010-04-02  

传个iterator进去吧。用数组构造就得100秒以上
这个算法是排重的。
如果不想排重就复杂了

	
	
	public Iterator<Integer> naverEnd(){
		
		return new Iterator<Integer>() {
			int i =0;
			private Random r = new Random();
			public void remove() {}
			public Integer next() {
				i++;
				if(i%10==0){
					Math.abs(r.nextInt(200));
				}
				return Math.abs(r.nextInt(100));
			}
			public boolean hasNext() {
				return i<1000000000;
			}
		};
	}

			public Set<Integer> getMax100(Iterator<Integer> it){
		TreeSet<Integer> set = new TreeSet<Integer>();
		int temp = 0;

		while(it.hasNext()){
			temp = it.next();
			if(set.contains(temp)){
				continue;
			}else if(set.size()<RETURN_SIZE){
				set.add(temp);
			}else if(set.first()< temp){	
				set.remove(set.first());	
				set.add(temp);
			}else{
				/* do nothing */
			}
			
		}
		return set;
	}

73 楼 paohui01 2010-04-02  

taojingrui 写道

这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。

方法1
基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。
提示：
1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8<12M，就是10亿数字，也不到120M
2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小）
3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次）

方法2
建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间）

int[] nums = new int[100000000];
内存溢出拉？
java  int占32位  相当于4个字节
1亿个int占4亿个字节....
4亿个字节 差不多相当于380M 能溢出？1G的内存就够用    

第一种方法 看不懂

使用TreeSet感觉是最好解决方法拉(参考skzr.org的代码)
如果觉得内存会不够用的话
数据放到文件里面读取好拉
内存永远不会溢出

72 楼 超级潜水员 2010-04-01  

SB腾讯的那帮人喜欢装 B,喜欢出些整人的问题.

71 楼 chs1987 2010-04-01  

建议还是不要使用多线程，我用1000个线程和2个线程相比，这两个时间简直就不再一个数量级上，花费在线程上的开销占了绝大多数的时间

70 楼 pubx 2010-04-01  

bit[]应该是比较好解决办法。

69 楼 ansjsun 2010-04-01  

大哥我看了下你的代码..内存不溢出就见鬼了

68 楼 realcbb 2010-04-01  

taojingrui 写道

这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。

方法1
基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。
提示：
1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8<12M，就是10亿数字，也不到120M
2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小）
3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次）

方法2
建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间）

对于方法1, bit的确是解决很多问题的好方法. 但是我有一点疑问, 在这个问题中用bit数组, 数据如何初始化呢, i如何才能取到?
另外, 对于非整形数据, 这样就不适用了.

67 楼 J-catTeam 2010-04-01  

<div class="quote_title">taojingrui 写道</div>
<div class="quote_div">
<div class="quote_title">wilddonkey 写道</div>
<div class="quote_div">
<div class="quote_title">taojingrui 写道</div>
<div class="quote_div">这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。<br><br>方法1<br>基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。<br>提示：<br>1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8&lt;12M，就是10亿数字，也不到120M<br>2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小）<br>3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次）<br><br>方法2<br>建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间）<br><br>
</div>
<br>楼上的方法第一个没看懂怎么能实现这个要求的；<br>第二个感觉不现实，你随便找一个数据库试试，插入1亿条要花多长时间<br>开头的分析很像一回事</div>
<p> </p>
<p>其实第二种方法在实际应用中是经常存在的，似想一下，腾讯要在所有QQ用户（上亿用户）中找到某类的top100用户，该怎么找，怎么排序？QQ用户的信息早就存在数据库里了。方法二不是我想的，是当年考我类似这种题目的考官告诉我的，目的是要告诉我，面试的考题有些时候不仅仅是考算法能力，还考察一个人的发散思维。考官告诉我，10个人考这样的题，9个人拿起题就考虑怎样去通过自己写程序实现，但是其实很多东西用现成的就好。题目要求的是考“如何从大量数字中取出 top 100”，不是考如何导入数据。</p>
<p>至于第一种方法是针对内存处理的。类似QQ这样的系统，有上亿用户，平时在线的都有上千万，如果要在内存中保存上亿用户的登陆状态，该如何保存？要快速查找到某一个用户的登陆状态（或更改登陆状态）该如何处理？方法一就是解决办法之一。快速查找用户，和题目要求的取top100，实质上是要解决如何在大数据总量下快速查找特定数据。</p>
<p>其实方法二，不算特别了，我还见过更有趣的方法。怎么算？一个候选人说道，一般的算法都解决不了这么大的数目（内存不够），所以随便找一个算法（能处理1千万大小的排序就行），然后采用分布式，把1亿数字分成10份，起10个应用分别排序，每个应用算出自己的top100，然后将10个top100放到一起，再排序一次。候选人还补充说，他的方法别说1亿，就是1万亿的数目，都能处理，当然速度方面就另说了。至少我老板就非常欣赏这个候选人的想法，这个候选人也被成功录用了。</p>
</div>
<p><br>第二个说的是mapreduce吧..分离。再汇总</p>

66 楼 taojingrui 2010-04-01  

<div class="quote_title">wilddonkey 写道</div>
<div class="quote_div">
<div class="quote_title">taojingrui 写道</div>
<div class="quote_div">这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。<br><br>方法1<br>基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。<br>提示：<br>1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8&lt;12M，就是10亿数字，也不到120M<br>2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小）<br>3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次）<br><br>方法2<br>建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间）<br><br>
</div>
<br>楼上的方法第一个没看懂怎么能实现这个要求的；<br>第二个感觉不现实，你随便找一个数据库试试，插入1亿条要花多长时间<br>开头的分析很像一回事</div>
<p> </p>
<p>其实第二种方法在实际应用中是经常存在的，似想一下，腾讯要在所有QQ用户（上亿用户）中找到某类的top100用户，该怎么找，怎么排序？QQ用户的信息早就存在数据库里了。方法二不是我想的，是当年考我类似这种题目的考官告诉我的，目的是要告诉我，面试的考题有些时候不仅仅是考算法能力，还考察一个人的发散思维。考官告诉我，10个人考这样的题，9个人拿起题就考虑怎样去通过自己写程序实现，但是其实很多东西用现成的就好。题目要求的是考“如何从大量数字中取出 top 100”，不是考如何导入数据。</p>
<p>至于第一种方法是针对内存处理的。类似QQ这样的系统，有上亿用户，平时在线的都有上千万，如果要在内存中保存上亿用户的登陆状态，该如何保存？要快速查找到某一个用户的登陆状态（或更改登陆状态）该如何处理？方法一就是解决办法之一。快速查找用户，和题目要求的取top100，实质上是要解决如何在大数据总量下快速查找特定数据。</p>
<p>其实方法二，不算特别了，我还见过更有趣的方法。怎么算？一个候选人说道，一般的算法都解决不了这么大的数目（内存不够），所以随便找一个算法（能处理1千万大小的排序就行），然后采用分布式，把1亿数字分成10份，起10个应用分别排序，每个应用算出自己的top100，然后将10个top100放到一起，再排序一次。候选人还补充说，他的方法别说1亿，就是1万亿的数目，都能处理，当然速度方面就另说了。至少我老板就非常欣赏这个候选人的想法，这个候选人也被成功录用了。</p>

65 楼 J-catTeam 2010-04-01  

J-catTeam 写道

这个题的条件应该不足吧
1.这1亿的数据在哪里？ 如果在内存里面。红黑树就够了
2.如果数据不在内存里，那说明有可能内存是肯定装不下的。如果在数据库里面。·给一个1亿的数据建个索引那是相当恐怖的。如果没有索引。就不要建索引了。采用分批的方式。比如每次取100w的数据红黑树。最后合并。如果有索引的话··直接取就是了吧。

64 楼 J-catTeam 2010-04-01  

这个题的条件应该不足吧
1.这1亿的数据在哪里？ 如果在内存里面。红黑树就够了
2.如果数据不在内存里，那说明有可能内存是肯定装不下的。如果在数据库里面。·给一个1亿的数据建个索引那是相当恐怖的。如果没有索引。就不要建索引了。采用分批的方式。比如每次取100w的数据红黑树。最后合并。如果有索引的话··直接取就是了吧。

63 楼 rails2007 2010-04-01  

luke_kai的TreeSet的思路是正确的。

62 楼 siemon 2010-04-01  

感觉像是一道智力题。
最好的办法是数据拆分，分布式计算。
比如像前面有人所说的拆分成10W*1000这种形式的。
每次读取10W个数字到内存中进行排序，取出top100保存，然后释放刚刚读取的10W数字数组。如此，总共需要做1000次。最后会得到1000个包含top100的数组，将这些数组合并成一个总共为10W个数字的数组，最后再取top100。
这种算法应该是最有效率，最节约资源的。

61 楼 wilddonkey 2010-04-01  

taojingrui 写道

这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。

方法1
基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。
提示：
1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8<12M，就是10亿数字，也不到120M
2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小）
3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次）

方法2
建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间）

楼上的方法第一个没看懂怎么能实现这个要求的；
第二个感觉不现实，你随便找一个数据库试试，插入1亿条要花多长时间
开头的分析很像一回事

60 楼 taojingrui 2010-04-01  

这样的考题，我遇过多次了。其实这类题，考官考的东西并不完全是算法。完全追求算法，就陷进去了。考题考的是两方面，一是考虑内存，纯粹用排序算法是不可能的，光int[] nums = new int[100000000];这一句就可能导致内存不够。（增加内存根本不是考官希望的，这么个小程序就要增加内存？）二是考虑在内存许可的情况下，尽量提高速度。

方法1
基本上，这道题如果不考虑数据录入，调用两次循环，上亿的数字中找top100，用不到1秒应该就够了。
提示：
1.考虑用位（bit）数组，1亿bit需要多少内存？100000000/1024/1024/8<12M，就是10亿数字，也不到120M
2.一个bit的数组大小为1亿，bit[i]=0,表示i数据不存在，bit[i]＝1，表示i数据存在。（循环1次1亿数据，不用比较数据大小）
3.最后找到bit数组中，bit[i]＝1且top100 i（循环1次）

方法2
建立一张数据库表，把上亿数据录入数据库，有索引的情况下，在上亿数据中找top100，也是很快的（不考虑数据录入数据库的时间）