`
mymail
  • 浏览: 17367 次
  • 性别: Icon_minigender_1
  • 来自: 苏州
最近访客 更多访客>>
社区版块
存档分类
最新评论

支付宝笔试题

    博客分类:
  • java
阅读更多

往事看到一道支付宝笔试题,自己做了一下,尽管效率不高,也是个人思考的结果。题目如下:

有一个100G大小的文件里存的全是数字,并且每个数字见用逗号隔开。现在在这一大堆数字中找出100个最大的数出来。

 

做法:

假设数字为4字节整数,逗号为2字节unicode字符,100G文件本人电脑无法容纳,所以取2亿整数,文件大小1.2G

 

1. 生成二进制文件(使用DataOutputStream,使用缓冲区,耗时79秒):

 

                               File file = new File("E:\\test.dat");
		if (!file.exists()) {
			file.createNewFile();
		}
		long time = System.currentTimeMillis();
		DataOutputStream stream = new DataOutputStream(new BufferedOutputStream(new  FileOutputStream(file)));
		Random random = new Random();
		long count = 200000000;
		System.out.println(count+"is max long int in java");
		int temp;
		for (long i = 0; i < count; i++) {
			temp = random.nextInt();
			stream.writeInt(temp);
			stream.writeChar(',');			
		}
		System.out.println("循环完成");
		stream.flush();
		stream.close();
		time = System.currentTimeMillis() - time;
		System.out.println(time+"毫秒");

 

 

2. 分析文件(使用DataInputStream,使用缓冲区,耗时65秒)

     a. 读取前100个整数

     b. 排序,把排序后的数组看成堆,最小值在根节点

     c. 遍历整个文件,把读到的数和最小值比较,如果比最新值小,则丢弃,如果比最小值大则替换最小值重建堆。

     d. 文件读取完毕,堆中的元素就是要找的100个最大值,再执行一次排序。

    

TestRead.java
public static void main(String[] args) throws IOException, InterruptedException {
		File file = new File("E:\\test.dat");		
		long time = System.currentTimeMillis();
		DataInputStream stream = new DataInputStream(new  BufferedInputStream(new FileInputStream(file)));
		int len = 100;
		
		
		long count = 100;
		int arr[] = new int[100];		
		for (int i = 0; i < len; i++) {				
			arr[i] = stream.readInt();
			stream.readChar();			
		}
		
		Arrays.sort(arr);		
		print(arr);		
		int temp = 0;
		while(true) {	
			try {					
			   temp = stream.readInt();
			   stream.readChar();
			   count++;
			   if(temp > arr[0]) {
			   		addToheap(arr,temp);		   		
			   } else {
			   		continue;
			   }
			 } catch(EOFException ioe) {
			 	  break;
		   }
		}
		stream.close();
		time = System.currentTimeMillis() - time;
		System.out.println(time+"毫秒"+":"+count+"个");
		Arrays.sort(arr);
		print(arr);
		
		
	}
	
   static void addToheap(int arr[], int temp){
	   arr[0] = temp;
	   int index = 0;
	   int left = 1; 
	   int right = 2;
	   int minIndex = index;
	   while (left < arr.length) {
		   if (arr[index] > arr[left]) {
			   minIndex = left;
		   }
		   if (right < arr.length && arr[minIndex] > arr[right]) {
			   minIndex = right;
		   }
		   if (minIndex == index) {
			   break;
		   } else {
			   temp = arr[minIndex];
			   arr[minIndex] = arr[index];
			   arr[index] = temp;
			   index = minIndex;
			   left = 2*index + 1;
			   right = 2*index + 2;
		   }
			
		}
			   
	}
static void print(int[] aa) {
  for (int i = 0; i < aa.length; i++) {
   System.out.print(aa[i] + ",");
   if ((i + 1) % 10 == 0) {
    System.out.println();
   }
  }
 }

 

3. 使用内存映射,nio,代替DataInputStream,用时12秒,只能使用MyEclipse6.5jre, 使用jdk1.5,jdk1.6时

    存储空间不足,堆空间不足。

4. 对文件进行分段映射(暂时分为10段),每个线程负责读取一段,找出该段最大的100个,

    在找到10X100个数中找最大的100个,用时10秒,性能没有显著改善。

package test;

import java.io.RandomAccessFile;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;





public class MultiThreadReader {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		long time = System.currentTimeMillis();
		long len = 200000000 * 6;
		int reads = 200;
		LinkedList<RandomReader> randomReaders = new LinkedList<RandomReader>();
	    RandomReader randomReader  = null;
		for(int i = 0; i < reads; i++) {
			randomReader = new RandomReader(i*len/reads, len/reads/6);
			randomReaders.add(randomReader);
			new Thread(randomReader).start();
		}
		int numberNeedFound = 100;
		int firstArr[] = new int[numberNeedFound];
		boolean firstFound = false;
		HashSet<RandomReader> set = new HashSet<RandomReader>();
		try {
			Thread.sleep(100);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	    while(set.size() < reads) {
			for(int i = 0; i < reads; i++) {
				randomReader = randomReaders.get(i);
				if (randomReader.done && !firstFound) {
					firstFound = true;
					firstArr = randomReader.arr;
					set.add(randomReader);
				} else if (firstFound && randomReader.done 
						&& !set.contains(randomReader)) {
					set.add(randomReader);
					for (int j = 0; j < randomReader.arr.length; j++) {
						if (randomReader.arr[j]>firstArr[0]) {
                                                                                                 TestRead.addToheap(firstArr, randomReader.arr[j]);
                                                                                                }		
			                                }
				}
			}
		}
	    time = System.currentTimeMillis() - time;
	    Arrays.sort(firstArr);
	    TestRead.print(firstArr);
	    System.out.printf("使用时间%d秒\n", time);
		

	}

}

class RandomReader implements Runnable {
	long offset = 0;
	long len = 10;
	RandomAccessFile file;
	boolean done = false;
	int numberNeedFound = 100;
	int arr[] = new int[numberNeedFound];
    MappedByteBuffer buffer;
    static int id = 0;
    int sid;
	public RandomReader(long offset, long len) {
		sid = id++;
		this.offset = offset;
		this.len = len;
		try {
			file = new RandomAccessFile("E:\\test.dat", "r");
			buffer = file.getChannel().map(FileChannel.MapMode.READ_ONLY, offset, len*6);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public void run() {
		int count = 0;
		for (int i = 0; i < numberNeedFound; i++) {
			arr[i] = buffer.getInt();
			buffer.getChar();
			count++;
		}
		Arrays.sort(arr);
		try {
			int temp = 0;
			while (count < len) {
				temp = buffer.getInt();
				buffer.getChar();				
				count++;
				if (temp > arr[0]) {
					TestRead.addToheap(arr, temp);
				}
				if(count == len/2) {
					System.out.printf("reader %d completed 50 percent\n", sid);
				}
			}
			done = true;
			System.out.printf("reader %d completed 100 percent count = %d \n", sid,count);

		} catch (Exception e) {
			System.out.printf("reader %d is dead count = %d\n", sid,count);
			e.printStackTrace();
		}
		
	}
}

 

 

 

 

 

 

分享到:
评论

相关推荐

    2010支付宝笔试题

    2010支付宝笔试题.rar2010支付宝笔试题.rar

    2010支付宝笔试题.rar

    2010支付宝笔试题.rar 2010支付宝笔试题.rar

    支付宝招聘笔试题

    在深入探讨支付宝招聘笔试题的知识点之前,我们需理解,此类题目主要考察应聘者在IT领域的专业技能、逻辑思维能力和解决问题的能力。虽然给定的部分内容并未提供具体题目,但基于支付宝作为全球领先的数字支付和生活...

    20091015支付宝的笔试题

    阿里巴巴旗下的支付宝 于2009年10月15日在成都的校园招聘笔试题 全是选择题,分成4个部分 一、计算机基础知识 17个单选题 二、逻辑推理 15个单选题 三、网络及系统 9个单选题 四、数据库及SQL 7个单选题

    支付宝Java工程师笔试题

    ### 支付宝Java工程师笔试题解析 #### 智力部分 1. **烧绳问题** **题目:** 烧一根不均匀的绳子需要一个小时,如何利用这根绳子判断出半小时的时间? **解答:** 将绳子的两端同时点燃,由于燃烧不均匀,无法...

    支付宝2010笔试题

    特别声明一下,我发上去的是去年的技术类笔试题。但本人参加了武汉地区支付宝2011的笔试,做过以后发现总体情况差不多,题型基本类似,考数据结构比较多,没算法的题,有逻辑推理题、编译原理的后缀表达式、数据库、...

    支付宝2011 笔试题

    【支付宝2011 笔试题】涉及到的IT知识点涵盖了计算机网络、数据库管理、软件工程、数据结构与算法、操作系统等多个领域。以下是这些知识点的详细解释: 1. **计算机网络**:笔试题可能包含了TCP/IP协议栈的理解,如...

    2010年支付宝最新笔试题A卷

    因此,我无法直接提供与"2010年支付宝最新笔试题A卷"相关的具体IT知识点。不过,我可以分享一些关于支付宝以及可能在笔试中出现的IT主题的一般性知识。 支付宝是中国领先的第三方在线支付平台,由阿里巴巴集团于...

    移动公司笔试试题和答案

    - **移动互联网业务**:如微信、支付宝等应用的网络架构和挑战。 - **物联网(IoT)**:NB-IoT、eMTC等窄带物联网技术的应用场景。 通过学习移动公司笔试试题和答案,不仅可以了解移动通信的基本原理和技术,还能...

    蚂蚁金服社招java笔试题目-coding-interview-study-guide:此存储库包含我为准备编码面试而收集的笔记

    蚂蚁金服社招java笔试题目编码面试学习指南 该存储库包含我为准备编码面试而收集的笔记。 这些笔记基于流行的书籍:和。 第 1 章:数组和字符串 笔记哈希表:一种将键映射到值以实现高效查找的数据结构。 ArrayLists...

    百度校招产品岗笔试题(1)_互联网 产品经理求职 校招 面试笔试题.docx

    在百度这样的大型互联网公司中,产品岗位的校招笔试题往往旨在评估应聘者的行业理解、产品思维、分析能力和创新意识。以下是根据题目内容解析的相关知识点: 1. **互联网金融产品的应用分析**: - 使用经历:此题...

    2014支付宝面试题 笔试和面试

    根据给定的信息,我们可以推断出这份文档包含了2014年支付宝面试的相关知识点,包括笔试题目和面试问题。下面将对这些知识点进行详细的解析。 ### 1. Cookies与Session Cookies是一种存储在用户浏览器上的小文本...

    阿里校招面试笔试题

    阿里作为中国顶尖的互联网巨头,其校招面试笔试题历来备受关注,因为它反映了公司对人才的需求和期望。这些试题不仅测试应聘者的编程能力,还考察逻辑思维、问题解决、团队协作以及对公司业务的理解等多个方面。以下...

    淘宝2010,2011,2012年笔试题

    针对“淘宝2010,2011,2012年笔试题”这一主题,我们可以深入探讨历年笔试题中可能涉及的IT知识点,帮助准备应聘者了解淘宝对技术人才的期望和要求。 首先,淘宝笔试题目通常会涵盖计算机基础,包括数据结构、算法、...

    c++笔试题总汇(百度,IBM,淘宝,华为,中兴,支付宝等)

    根据给定文件的信息,我们可以提炼出以下几个重要的C++知识点: ### 1. 字符串比较问题 #### 问题描述: 给定了三个字符串比较的例子,并询问它们的比较结果。 ```cpp char str1[] = "abc";...char str2[] = "abc";...

    支付宝在线测评题

    通过以上分析,我们可以看出支付宝2011年的校园招聘在线测评题覆盖了逻辑推理、数字规律、图形推理等多个方面,旨在全面考察应聘者的基本素质和能力。对于应聘者来说,除了具备相应的知识技能外,还需要在实际操作中...

    百度2016校园招聘 产品岗笔试题.pdf

    2016年百度的校园招聘中,产品岗位的笔试题便聚焦在对互联网产品的理解和分析上,这对于我们理解产品设计的思路以及人性的洞察具有极大的启示。 首先,题目的第一部分涉及到对互联网金融产品的实际应用和分析。...

    2016年阿里巴巴校园招聘笔试题杭州站-研发类.doc

    【阿里巴巴2016年校园招聘研发类笔试题解析】 阿里巴巴作为全球知名的技术驱动型企业,其校园招聘笔试题历来备受关注,尤其是对于技术研发类岗位。这些题目不仅考察候选人的技术基础,还涉及到逻辑思维、问题解决...

Global site tag (gtag.js) - Google Analytics