`
hikelee
  • 浏览: 8061 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
最近访客 更多访客>>
luliangy
文章分类
社区版块
存档分类
最新评论

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

腾讯面试算法QQJ# 
阅读更多

最近有同事去腾讯面试,其中一个排序算法题:从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亿数据时,机子几乎就没有反应了,这可能是物理内存已经耗尽,用虚拟内存了.

 

欢迎交流!

分享到：
| Portlet标准:JSR168/JSR286/WSRP
评论
39 楼 mblmh2008 2010-03-31  
你自己那个不就是自己构造了一个有序树,难道你自己都不知道的吗?
38 楼 zwhc 2010-03-31  
ldinh 写道
public class AppMain {

    private final static Random rnd = new Random();

    public static int[] top(int[] data, int count) {
        LinkedList<Integer> topNums = new LinkedList<Integer>();
        topNums.add(Integer.MIN_VALUE);

        for (int i : data) {

            if (topNums.getLast() > i) {
                if (topNums.size() < count) {
                    topNums.add(i);
                }
                continue;
            }

            for (ListIterator<Integer> iter = topNums.listIterator(); iter.hasNext();) {
                if (i > iter.next()) {
                    iter.previous();
                    iter.add(i);
                    if (topNums.size() > count) {
                        topNums.removeLast();
                    }
                    break;
                }
            }
        }

        int[] result = new int[count];
        for (ListIterator<Integer> iter = topNums.listIterator(); iter.hasNext();) {
            result[iter.nextIndex()] = iter.next();
        }

        return result;
    }

    public static void main(String[] args) {
        int n = 100000000;
        int[] ia = new int[n];
        for (int i = 0; i < n; i++) {
            ia[i] = rnd.nextInt(n);
        }

        long start = System.currentTimeMillis();
        int[] result = top(ia, 100);
        System.out.println(System.currentTimeMillis() - start + "ms");
        for (int i : result) {
            System.out.println(i);
        }
    }
}


你。。。这是冒泡吧。。。
如果取 top 10000 的话，好象很慢啊。
37 楼 breezem 2010-03-31  
用treeset实现 1亿条数据内存不够
1000W条 234ms
36 楼 刃之舞 2010-03-31  
插入数据库，这么多数据不会有存在文件的业务使用环境的
然后嘛
sybase: select top 100 * from table

oracle: select * from table where rownum<100

                  
35 楼 fxsjy 2010-03-31  
cat test.txt | sort -nr | head -n10
34 楼 caibinbupt 2010-03-31  
哈哈，拿MapReduce做啦
33 楼 ldinh 2010-03-31   
public class AppMain {

    private final static Random rnd = new Random();

    public static int[] top(int[] data, int count) {
        LinkedList<Integer> topNums = new LinkedList<Integer>();
        topNums.add(Integer.MIN_VALUE);

        for (int i : data) {

            if (topNums.getLast() > i) {
                if (topNums.size() < count) {
                    topNums.add(i);
                }
                continue;
            }

            for (ListIterator<Integer> iter = topNums.listIterator(); iter.hasNext();) {
                if (i > iter.next()) {
                    iter.previous();
                    iter.add(i);
                    if (topNums.size() > count) {
                        topNums.removeLast();
                    }
                    break;
                }
            }
        }

        int[] result = new int[count];
        for (ListIterator<Integer> iter = topNums.listIterator(); iter.hasNext();) {
            result[iter.nextIndex()] = iter.next();
        }

        return result;
    }

    public static void main(String[] args) {
        int n = 100000000;
        int[] ia = new int[n];
        for (int i = 0; i < n; i++) {
            ia[i] = rnd.nextInt(n);
        }

        long start = System.currentTimeMillis();
        int[] result = top(ia, 100);
        System.out.println(System.currentTimeMillis() - start + "ms");
        for (int i : result) {
            System.out.println(i);
        }
    }
}
32 楼 zwhc 2010-03-31  
luke_kai 写道
zwhc 写道
luke_kai 写道
zwhc 写道
luke_kai 写道
不可能吧，我写的那段程序，亿级的数据花销 2.3秒
Spend time:2375


要将初始化的时间 int inputArray[] = new int[numberCount]; 计算在内啊。

算进去，大概是 10 秒左右。在我机子上。

初始化时间不能算啊，我们讨论的是算法的时间。楼主的也没算，这样才好对比嘛。


应该要算的。题目没有要求你初始化这么大的一个数组啊。别人不用初始化大数组的方式，怎么对比？

你这种说法有点投机取巧啊。实际应用中，数据应该另有来源。
我改了一下，不初始化数组，也是6秒多。


import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class TestSF {

public static Set<Integer> getTop100(int inputCount) {

TreeSet<Integer> top100 = new TreeSet();
Random random = new Random();

for (int i = 0; i < inputCount; i++) {
int numb = random.nextInt(inputCount);
if (top100.size()<100){
top100.add(numb);
}else if ((Integer)top100.first()<numb){
Object obj = top100.first();
top100.remove(obj);
top100.add(numb);
}

}

return top100;

}

public static void main(String[] args) {

int numberCount = 100000000;

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();

Set<Integer> result = TestSF.getTop100(numberCount);

System.out.println("Spend time:"+(System.currentTimeMillis() - current));

// for (Integer i :result) {
// System.out.print(result+ ",");
// }

}

}


top100.first() 操作次数太多了。我刚才试了一下你这代码，9 秒多。加个中间变量就变成 6 秒左右了。
看来 top100.first() 很花时间。

另外，我测了一下，random.nextInt 一亿次，是 5 秒多，也就是说，实际的排序，只要半秒多。
31 楼 faylai 2010-03-31  
luke_kai 写道
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class TestSF {

public static Set<Integer> getTop100(int[] inputArray) {

TreeSet<Integer> top100 = new TreeSet();
for (int i = 0; i < inputArray.length; i++) {

if (top100.size()<100){
top100.add(inputArray[i]);
}else if ((Integer)top100.first()<inputArray[i]){
Object obj = top100.first();
top100.remove(obj);
top100.add(inputArray[i]);
}

}

return top100;

}

public static void main(String[] args) {

int numberCount = 100000000;

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();

Set<Integer> result = TestSF.getTop100(inputArray);

System.out.println("Spend time:"+(System.currentTimeMillis() - current));


}

}


这个是比较快我的机器上一亿才用2.7秒
30 楼 yilv99 2010-03-31  
据我所知，这个原题是从一亿个数当中取出top 10000吧。。
29 楼 joeycn 2010-03-31  
请问这真的是道对亿级数据的排序题吗？
取一百个最大值而已的话，就没那么复杂了吧
先对头一百个数排序， 然后一个个比较，在最大值最小值之外的数直接抛弃，中间值参与二分查找法定位并替换
最后得到的就是要的东西了
28 楼 luke_kai 2010-03-31  
zwhc 写道
luke_kai 写道
zwhc 写道
luke_kai 写道
不可能吧，我写的那段程序，亿级的数据花销 2.3秒
Spend time:2375


要将初始化的时间 int inputArray[] = new int[numberCount]; 计算在内啊。

算进去，大概是 10 秒左右。在我机子上。

初始化时间不能算啊，我们讨论的是算法的时间。楼主的也没算，这样才好对比嘛。


应该要算的。题目没有要求你初始化这么大的一个数组啊。别人不用初始化大数组的方式，怎么对比？

你这种说法有点投机取巧啊。实际应用中，数据应该另有来源。
我改了一下，不初始化数组，也是6秒多。


import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

public class TestSF {

public static Set<Integer> getTop100(int inputCount) {

TreeSet<Integer> top100 = new TreeSet();
Random random = new Random();

for (int i = 0; i < inputCount; i++) {
int numb = random.nextInt(inputCount);
if (top100.size()<100){
top100.add(numb);
}else if ((Integer)top100.first()<numb){
Object obj = top100.first();
top100.remove(obj);
top100.add(numb);
}

}

return top100;

}

public static void main(String[] args) {

int numberCount = 100000000;

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();

Set<Integer> result = TestSF.getTop100(numberCount);

System.out.println("Spend time:"+(System.currentTimeMillis() - current));

// for (Integer i :result) {
// System.out.print(result+ ",");
// }

}

}
27 楼 zwhc 2010-03-31  
luke_kai 写道
zwhc 写道
luke_kai 写道
不可能吧，我写的那段程序，亿级的数据花销 2.3秒
Spend time:2375


要将初始化的时间 int inputArray[] = new int[numberCount]; 计算在内啊。

算进去，大概是 10 秒左右。在我机子上。

初始化时间不能算啊，我们讨论的是算法的时间。楼主的也没算，这样才好对比嘛。


应该要算的。题目没有要求你初始化这么大的一个数组啊。别人不用初始化大数组的方式，怎么对比？
26 楼 luke_kai 2010-03-31  
zwhc 写道
luke_kai 写道
不可能吧，我写的那段程序，亿级的数据花销 2.3秒
Spend time:2375


要将初始化的时间 int inputArray[] = new int[numberCount]; 计算在内啊。

算进去，大概是 10 秒左右。在我机子上。

初始化时间不能算啊，我们讨论的是算法的时间。楼主的也没算，这样才好对比嘛。
25 楼 zwhc 2010-03-31  
luke_kai 写道
不可能吧，我写的那段程序，亿级的数据花销 2.3秒
Spend time:2375


要将初始化的时间 int inputArray[] = new int[numberCount]; 计算在内啊。

算进去，大概是 10 秒左右。在我机子上。
24 楼 JE帐号 2010-03-31  
对于单CPU,这个题目使用多线程没意义.应该是多CPU才对
23 楼 magnesium 2010-03-31  
怎么没看到用数据库排序的。。。
22 楼 zwhc 2010-03-31  
另外，用 TreeSet 写了个程序，内存占用量是个优势，比较平稳。但速度只快一些，楼主的算法，速度大概是 16 秒左右。我这个是 6 秒左右。楼主的，速度不是线性相关的，我这个是线性相关的。
应该有其它的方式，6秒可能还是太高。

嗯嗯，要注意一下，现在这个代码，是 10 亿个数取 top100。

package test;

import java.util.Iterator;
import java.util.Random;
import java.util.TreeSet;

/**
* http://www.iteye.com/topic/628707
* 排序算法题:从1亿个数字中取出最大的100个
*
*/
public class Top100_02 {

/**
* 如果数字不在 treeset 里，则加入，并返回 true。
* 如果数字在 treeset 里，则不加入，并返回 false。
* @param ts
* @param newData
* @return
*/
private static boolean doTop(TreeSet<Integer> ts, int newData)
{
if(ts.contains(newData))
{
return false;
}

ts.remove(ts.first());
ts.add(newData);

return true;
}

private static void test(int numberCount, int topNum)
{
System.out.println("L36: Sort begin...");

long current = System.currentTimeMillis();

int min = 0;

int maxNumber = numberCount;
Random random = new Random();
random.setSeed(System.currentTimeMillis());
//int[] result = new int[topNum];
TreeSet<Integer> ts = new TreeSet<Integer>();

for (int i = 0; i < topNum; ++i)
{
int newData = random.nextInt(maxNumber);
//System.out.println("L51:newData:" + newData);
ts.add(newData);
}
min = ts.first();
//System.out.println("L55 min:" + min);
for (int i = topNum; i < numberCount; ++i)
{
int newData = random.nextInt(maxNumber);
//System.out.println("L59:newData:" + newData);
if(newData>min)
{
if(doTop(ts, newData))
{
min = ts.first();
//System.out.println("L65 min:" + min);
}
}
}

System.out.print(numberCount);
System.out.print(":");
System.out.println(System.currentTimeMillis() - current);

// Iterator<Integer> it = ts.iterator();
// while(it.hasNext())
// {
// System.out.print(it.next() + ",");
// }

}

public static void main(String[] args) {
//test(20, 5);
//test(100000, 100);

for(int i=0; i<25; i++)
{
test(900000000, 100);
}


}

}
21 楼 zwhc 2010-03-31  
将楼主的代码做了点修改，方便测试。

一千万的数据就跑不动了。后来调了内存设置。

另外，将计时更改了一下，楼主的计时不对，要将数据初始化的时间算进去。

package test;

import java.util.Random;

public class Top100 {

private 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;
}

private static void test(int numberCount) {
int maxNumber = numberCount;
System.out.println("Sort begin...");

long current = System.currentTimeMillis();

int inputArray[] = new int[numberCount];

Random random = new Random();

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

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

}


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

System.out.print(numberCount);
System.out.print(":");
System.out.println(System.currentTimeMillis() - current);

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

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

}

}

/**
* @param args
*/
public static void main(String[] args) {
// int numberCount = 90000000;
// test(90000000);
//test(20000000);
// for(int i=1; i<=10;i++)
// {
// test(10000000 * i);
// }
// for(int i=1; i<=10;i++)
// {
// for(int j=0; j<20;j++)
// {
// test(1000000 * i);
// }
// }

//test(1000000 );
test(100000000);

}

}
20 楼 luke_kai 2010-03-31  
这个错误是在初始化数组的时候产生的，你要加参数-Xms128M -Xmx1024M。排序的时候内存又不会增加多少。
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    一道腾讯面试题

    这道2011年腾讯校招的面试题虽然没有明确的问题描述，但从标签中我们可以推测，它可能涉及C++、.NET、Java这三种编程语言中的某一方面，或者是关于算法设计与分析。面试题通常旨在考察候选人的思维能力、编程基础...

    腾讯面试题解析.pdf

    腾讯面试题解析.pdf 本资源是一份详细的腾讯面试题解析文档，涵盖了 Android 面试题、网络基础、常用三方库、算法基础等多个方面的知识点。下面是对该文档的详细解析： 计算机基础面试题 在计算机基础面试题部分...

    腾讯面试题 + 笔试题(全)

    《腾讯面试题与笔试题详解》 在求职的道路上，面试和笔试是必不可少的环节，尤其是对于技术人才来说，能够顺利通过大公司的面试更是彰显个人实力的重要标志。本压缩包包含两份珍贵的资料——“腾讯笔试题专辑(含...

    腾讯研究院：PDF 腾讯数字生活报告

    腾讯研究院：PDF 腾讯数字生活报告

    腾讯PHP面试题_腾讯php面试题_

    最新腾讯PHP面试题1. php 的垃圾回收机制 PHP 可以自动进行内存管理，清除不需要的对象。 PHP 使用了引用计数 (reference counting) GC 机制。 每个对象都内含一个引用计数器 refcount，每个 reference 连接到对象，...

    2021最新大厂AI面试题：107题（含答案及解析）.pdf

    腾讯的面试题则关注了SVM的优化函数公式、随机森林的原理、XGBoost的优势等。SVM的优化函数是二次规划问题，随机森林通过构建多棵决策树来提高模型的鲁棒性。 蔚来和虾皮的面试题则包含了链表问题、二叉树遍历和数...

    最快的排序算法 腾讯算法面试题：64匹马8个跑道需要多少轮才能选出最快的四匹（详解）？，排序算法数据结构

    在腾讯算法面试题中，要求选出64匹马中最快的四匹，需要使用排序算法来解决这个问题。排序算法是计算机科学中的一种算法，用于对一组数据按照特定的顺序进行排序。排序算法的应用场景非常广泛，在数据分析、机器学习...

    阿里面试题 腾讯面试题 百度面试题 华为面试题 京东面试题 头条面试题 经典面试题 程序员 IT经理 项目经理 面试题

    阿里面试20题 百度面试10题 华为面试10题 京东面试13题 腾讯面试37题 头条面试10题 项目经理面试常遇问题 经典面试题 程序员 IT经理 项目经理 面试题 研发经理 高级程序员 经典面试题

    微软腾讯百度阿里面试 100 题系列-共330题

    一年之前的10月14日，一个名叫July （头像为手冢国光）的人在一个叫csdn的论坛上开帖分享微软等公司数据结构+算法面试100题，自此，与上千网友一起做，一起思考，一起解答这些面试题目，最终成就了一个名为：结构之...

    腾讯历年面试试题汇总

    以下是一些具体的面试题及其解析： 1. 宏定义比较大小：`#define BIG_THAN(a, b) (((b) – (a)&(0x1))&gt;&gt;31)` 这个宏利用了二进制的位运算来比较两个数的大小。当a大于b时，b-a会产生负数，而负数的最高位（符号位）...

    腾讯面试题笔试题

    ### 腾讯面试题笔试题解析 #### 领域背景 在IT行业中，面试题目不仅是对求职者技能的一种考验，也是企业筛选合适人才的重要工具。本篇将基于提供的标题、描述、部分问题及其答案，深入分析这些知识点，帮助读者更...

    互联网校招题库资料笔试面试真题具体面试问题回答技巧腾讯阿里培训资料.zip

    ava工程师面试题大全-100%公司笔试题你都能碰到几个.docx Java开发工程师上机笔试题.docx Java开发求职面试题.docx Java开发笔试题.docx Java数据结构类面试题.docx Java数据结构题.docx Java笔试面试宝典.docx Java...

    腾讯前端面试题

    在腾讯的前端面试中，面试官可能会关注一系列关键知识点，这些知识点涵盖了前端开发的基础到进阶内容。以下是对这些知识点的详细解释： 1. **JSONP原理**：JSONP（JSON with Padding）是一种解决跨域数据获取的问题...

    腾讯09年测试面试题（亲身经历）

    【腾讯09年测试面试题解析】 面试题1：QQ登陆号码边界值测试有哪些 边界值测试是一种重要的软件测试方法，主要针对输入或输出范围的边界条件进行测试。对于QQ登录号码，边界值可能包括最小值（如0，因为QQ号通常从0...

    腾讯Java面试题

    【腾讯Java面试题】 在Java领域，面试是评估求职者技术实力的重要环节，而腾讯作为中国互联网巨头之一，其Java面试题往往具有很高的参考价值。这些题目不仅涵盖基础语法、数据结构、算法、多线程、JVM优化等多个...

    腾讯研究院：2019腾讯数字生活报告-2019.5-48页.pdf

    腾讯研究院发布的《2019腾讯数字生活报告》深入分析了数字技术在人们日常生活中的渗透和应用，揭示了它们是如何满足人类的生存、关系以及发展需求，并进一步塑造个人生活路径的。报告基于马斯洛的需求层次理论，将...

    腾讯：中小企业数字化转型路径报告.pdf

    报告“腾讯：中小企业数字化转型路径报告”探讨了在全球新冠疫情背景下，数字化转型对于中小企业的重要性，以及中国在此过程中的挑战和机遇。数字化转型不仅是企业适应新环境的必然选择，也是国家经济发展的重要推动...

    前端面试题（包括百度阿里腾讯面试题）.txt

    网盘下载pdf文件，包括常见前端面试题汇总，百度、阿里、腾讯校招面试题汇总，网盘下载pdf文件，65个文件

    10道腾讯的Java面试题

    10道腾讯的Java面试题10道腾讯的Java面试题10道腾讯的Java面试题10道腾讯的Java面试题10道腾讯的Java面试题10道腾讯的Java面试题

    2022年最新(腾讯)前端面试题真题解析

    本资源“2022年最新(腾讯)前端面试题真题解析”汇聚了最新的腾讯前端面试题，旨在帮助求职者更好地准备面试，提升成功入职的可能性。 面试题的解析通常会涵盖以下几个关键领域： 1. **基础概念**：面试题会涉及...

Magicbox
Global site tag (gtag.js) - Google Analytics