2010支付宝西安最新笔试题..求高手给出算法和思路
有一个100G大小的文件里存的全是数字，并且每个数字见用逗号隔开。现在在这一大堆数字中找出100个最大的数出来。 --------------------编程问答-------------------- 。。求高手解答最效率的解决办法 --------------------编程问答-------------------- 保持一个Number[100]的数组有序，小于最小值不管，大于最小值找到位置插入，排出最小元素。 --------------------编程问答-------------------- 如果全都是正整数的话，可以先比较长度，挑出长度最长的一类，然后再排序挑出前100，如果最长的一类不足100个，就在长度-1的一类里选...........--------------------编程问答-------------------- java 不是有个自动排序的方法吗！ --------------------编程问答-------------------- 3L+2L 更好..
如果可以 扔到 数据库中.. 排序 去前100个 --------------------编程问答-------------------- 由于数据量比较大不易拿到容器再排序，
个人想法就是直接分析文件，先取前100个数排序。
然后再到到文件中取出一个数，把这一个数据有序的插入到100个数中，
删除101个数中最后一个数（最小的），如此循环到结束。
期待高手更好的办法 --------------------编程问答-------------------- --------------------编程问答-------------------- 期待好的办法，期待高手出现
--------------------编程问答-------------------- 思路上 我觉得要分段的！
要不这么大数据，直接派 别说会越界了！
即使不越界也会慢死！
我的思路：
1、分段、分级处理
2、用biginteger！
呵呵 再仔细考虑一下！
--------------------编程问答-------------------- 期待高手 --------------------编程问答-------------------- 感觉6楼的方法可行 --------------------编程问答-------------------- 100G大小存数字能存多少啊？ 显然是要一直最有效的排序方法 --------------------编程问答--------------------
哥们你太聪明了...
不过先得判断该数字是正数还是负数... --------------------编程问答-------------------- 我不知道怎么读取这个文件。 --------------------编程问答-------------------- 定义100大小的数组，先存入100个数，然后排序，之后每取一个数和数组中最小的比较，大于则踢出最小的，然后用插入排序法把新的数插入数组中，依次继续。
文件读取应该用FileChannel读取。 --------------------编程问答-------------------- 为什么把数字依次和100的数组比较 会比较有效率？ 这个和全部数字排序差别在哪里？ --------------------编程问答--------------------
--------------------编程问答-------------------- 上面的程序对小数和负数都进行了测试，但是对于过大的文件没进行测试。
import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.math.BigDecimal;
/**
*100G大小的文件里存的全是数字，并且每个数字间用逗号隔开，找出100个最大的数出来。
* @author imasmallbird </a>
* @version $Revision 1.1 $ 2009-10-13 下午03:02:35
*/
public class Test2 {
public static void main(String[] args) {
// 定义","对应的字节码
final int sep = ',';
// 每次读取一个字节
int tempByte = 0;
// 用于将读出的字节拼接成数字字符串
StringBuffer tempNumberString = new StringBuffer("");
// 初始化一个数组，用于存放100个最大数
BigDecimal[] maxNumbers = getInitMaxNumbers();
try {
InputStream inputStream = new BufferedInputStream(new FileInputStream(new File(
"D:\\1.txt")));
while ((tempByte = inputStream.read()) != -1) {
if (tempByte != sep) {
// 不是分隔符，则继续拼接
char tempChar = (char) tempByte;
tempNumberString.append(tempChar);
} else {
// 是分隔符，则之前拼成的已经是一个完整的数字，与已经有的最大数进行比较
BigDecimal tempNumber = new BigDecimal(tempNumberString.toString());
compare(maxNumbers, tempNumber);
// 准备下一个数的拼接
tempNumberString.delete(0, tempNumberString.length());
}
}
// 最后一个数还要进行排序
BigDecimal tempNumber = new BigDecimal(tempNumberString.toString());
compare(maxNumbers, tempNumber);
// 显示最大的100个数
displayAllMaxNumber(maxNumbers);
} catch (FileNotFoundException e) {
e.printStackTrace();
} catch (IOException e) {
e.printStackTrace();
}
}
/**
* 初始化一个长度为100的数组,初始化的最小值为double的最小值
*/
private static BigDecimal[] getInitMaxNumbers() {
BigDecimal[] maxNumbers = new BigDecimal[100];
for (int i = 0; i < maxNumbers.length; i++) {
maxNumbers[i] = new BigDecimal(Integer.MIN_VALUE);
}
return maxNumbers;
}
/**
* 比对数值,数组中的数始终从大到小排列，若当前比较的数大于其中的一个数，则剩余的数依次向后
*/
public static void compare(BigDecimal[] maxNumbers, BigDecimal compareNumber) {
for (int i = 0; i < maxNumbers.length; i++) {
if (compareNumber.compareTo(maxNumbers[i]) < 0) {
continue;
} else {
BigDecimal temNumber = maxNumbers[i];
maxNumbers[i] = compareNumber;
compareNumber = temNumber;
}
}
}
/**
* 显示所有的数
*/
private static void displayAllMaxNumber(BigDecimal[] maxNumbers) {
for (int i = 0; i < maxNumbers.length; i++) {
System.out.println(maxNumbers[i]);
}
}
}
程序的条件限制：
１、文件不以“，”号结尾，即最后一个数字后无“，”
２、由于初始化的最小值为Integer.MIN_VALUE(上程序中注释错误
（此处向大家请教，如何初始化为最小的数？？）
其他未考虑到的情况，大家指出～～～ --------------------编程问答--------------------
对呀，所以我说“如果都是正整数的话...”。如果有负数，那就把带“-”号的都去掉，只保留正数，然后再选。不过，如果正数不足100个，那就比较麻烦了............-_-! --------------------编程问答--------------------
先定义个长度一百的数组 该数组有序 同时也用你所说的长度的计算方法 当按照长度来的情况下不允许的时候就用数组被.. --------------------编程问答-------------------- 程序未关闭流：inputStream.close(); --------------------编程问答-------------------- 你可以这样回答：
请问：
1，你使用的什么操作系统，100G的文件，NTFS的？vista还是win7的？内存有多少大？
2，如果里面的数字小于100个怎么办？
3，如果里面的第一个数字就是100G-198个字节，那么java是无法处理的，请给我一个可以处理的语言出来。
4，我知道你会说假设，但是，程序员的任务是解决实际问题，一切皆以实际问题出发。任何一个理论都是有实际模型的。
5，不知道是谁命的题，我建议他命题严谨点，我不希望有这样的同事或者上级，更不希望将来贵公司因为这样的人毁了前途。 --------------------编程问答-------------------- 我觉得有以下可优化的点:
1.结果的存储结构最好自己设计一下,需要有以下特性:
a.定长 100;
b.自排序,从大到小
c.快速插入.
d.快速获取最小值,最大值,另外还有个特殊的值---最小值位数
基本上类似LinkedList,稍微封装一下就行.数组不太可取,否则给频繁复制元素.
2.由于是外部存储,避免不了的还需要一个内存缓存区,这个区域的大小需要仔细设定,题目没有限定内存大小,但是我想也不是越大越好,这个感觉是个经验值,应该是存在效率和空间的最优解的,通过几次测试应该可以确定.
3.数据比较策略:
因为是文件,并且数字间有逗号间隔,免不了有个根据逗号分隔数据的动作,此时要根据数据文件的特点来具体处理,如果说这些数字相差很大,也就是比较稀散,那么在识别数字前,先将两个逗号之间的偏移量和当前最小值的位数比较一下非常有必要,毕竟少了转换数字的动作,最后只有在同位数以及位数更大的情况下才考虑比较后插入.
4.这个问题,主要是三部分时间消耗,一个是硬盘读取,这个没什么可优化的,瓶颈在物理上,适当的换粗策略就够了,一个是将文件的数字转为数字类型,这个可优化的余地很大,最理想的是方式是按byte读,然后直接位运算比较,不过这个方式怎么实现还没思路.然后就是当前值向目前最大的100个值的插入,如果数据本身的规律就是越来越大,那么可以预见会有很多次的插入操作,不可避免的就会涉及到自排序的比较,这个优化目前只想到缓存部分有位数跨度的数的index,用来减少插入的比对次数.
--------------------编程问答--------------------
感觉这个回答挺好，我还傻子似的写程序呢
突然感觉处理这种题没多少经验，工作到现在，就两次笔试，结果都成了，第一家没去，第二家成了工作的第一家，也没遇到过这种题，学习了！！ --------------------编程问答-------------------- 关注 --------------------编程问答-------------------- 典型的数据结构题目。
可以先问面试官，确定数字是Integer, Long, or Double. 一般情况下，都是整数的。
然后就是 保存 100个数的问题，有两种解决方案 1:) Red-Black Tree. 2:) Max-Min-Heap.
其实2个方案的思路都是一样的，就是能在 o(1) 的情况下取到 最小值，如果当前数 （第101个起） 超过了最小值，就插入到里面去，并删除最小值。具体实现去 算法导论里面找吧。
然后就要考虑文件大小了， 由于文件很大，需要一个一个读入，遇到逗号，再转化为数字。负数也是一定要考虑的。
如果你的能力足够强，就可以把程序写出来，当然程序里面要处理一些Exception.
如果担心写出来的程序不够理想，可以把思路写出来。
--------------------编程问答-------------------- 因为没有那么大的数据源，所以谁都不好说自己的方法好使。100G啊。。。
抛开楼上提的那些问题（提的挺好的），真的就是把这个文件按照要求摆在你的面前，让你去处理，我想有些点是肯定需要被考虑到的：
1.缓存区
2.多线程
3.初始堆的大小
OR
1.数据库
前面两点不用我多说，第三点的意思是：我想没有谁愿意直接从100G的源中取出100个数，无异易做图捞针。那么肯定实现要读取一段数据，那么这个数据的规模易做图我说的初始堆的大小。结合Java7的性能提升，具体可以参加：http://www.javaeye.com/news/10069。我想合理地划分一下堆得大小是有必要的。
另外，这类问题我一直觉得面试官不是真的要你去写代码，因为现实中这类大数据量的操作，肯定不是一段代码就能解决的。所以我认为他是在考思维能力吧：全面性和拓展性。不知道其他人有什么补充？ --------------------编程问答-------------------- 哦，堆的大小就固定在 100。只是维护100 大小的heap.
其实，就问题本身来说，读取100G 大小的文件是必须的，而且每个数都必须读出来，并进行比较。 所以算法的重点在于如果快速的 判断这个数在100 个最大的heap 里面。
--------------------编程问答-------------------- --------------------编程问答-------------------- 如果是无序的，那只能一个一个的比较了，
N2 --------------------编程问答-------------------- 路过，顶一下 --------------------编程问答-------------------- 关注。。。。。。 --------------------编程问答--------------------
呵呵，这个强 --------------------编程问答-------------------- ding yi xia --------------------编程问答-------------------- 100G那得多大啊，关注 --------------------编程问答-------------------- 这个真不知道 --------------------编程问答-------------------- 不就是100个数的排序、插入、删除问题嘛。数是一个一个的读，100G和1000G没什么区别。
搞什么缓存/多线程/数据库是完全没必要的。 --------------------编程问答-------------------- 这个题的关键还是在于它的大小 100G。抛开100G ，如果是题目是，给你一个文本，里面每个数字的数据量都在可控范围内，内存足够大，每个数字以逗号分开，那么，只需要读取文件，转化为string，然后将string用“逗号”分开。或者，读取文件，读到“逗号”就结束读取，然后将数存入数据库（很大的数，必须这么做，要空出内存空间来）或者collection（数据比较小，可以存100个数在内存空间），最后就是读数，看是否满足100个数，满足的话，先将最小的拿出来（数据库本身有这个功能），『1，看长度 2，若长度相同，则比较头一个数字』。这样分割，应该是个程序员都会做。
值得注意的是，这里有个技巧，可以将读取出来的String的长度做为一个字段存入数据库，考虑上几楼有人说的正负号问题，也可以将正负号比如 正=1 负=0 也作为一个字段存入数据库。这样可以大大提高效率。不要将String转换为数字，那没必要。既然知道2个都是数字，就没必要转换了。（大数据量的转换还是很浪费时间的）。
关于多线程，我个人认为，数据比较小，但是非常多的时候，可行，并且可以大幅度提高效率 ，但是数据很大时，多线程非但不提高效率，而是浪费了一个时间片。会有一定程度的降低效率。
关于本人22楼的回答，可以在面试或者笔试时，真的想不到解决方法时使用，这样可以免除你答不出问题来的尴尬，如果面试官解释了相关的问题，那么你就应该直接回答，不会做。 --------------------编程问答-------------------- 菜鸟支持一下
--------------------编程问答-------------------- --------------------编程问答--------------------
你也说实际点了 你还这么问，如果我是考官我马上就out你了
1，你说能放100g数字的数据库的服务器操作系统会是什么？内存有多大？是不是每道考题都要吧硬件配置报一遍？而且我可以跟你说这题跟内存和操作系统关系不大，如果你这么理解你已经错了
2，你走的都是极端 数字是用来干嘛的 存储数据的。有什么数据能达到1g的长度？那这个数据肯定也会用科学计数法来保存了
3根据你上面的无知理论这点也否定掉。一切按常规你都不懂？
4你也知道解决实际问题 100g的数字数据确实是实际问题 而你的想法确非常不实际。
5你这样说只能表明你的应变能力比别人差而已，还有就是你比较走极端。
这题的思路上面都给出了 实际情况实际改变 内存小就分段小点排的少点 内存大就分段大点排的多点
1g排一次序 查100个最大的 100个数组比较100个最大的还不简单？ --------------------编程问答--------------------
1,首先，论文件，都是以01形式存在的，难道一个1g的文件，里面的数据能逃出01的范围？我奇怪了，你可以用科学计数法来保存文件？看来你可以创建更为强大的压缩技术了嘛！！世界会因你而改变的
2.是谁不懂理论?是谁无知？谁的想法不实际。是谁应变能力差。自己好好想想。
你还是先去学习下基础理论，别以为自己会编程就可以解决一切问题。包括空想的。 --------------------编程问答--------------------
这个可以用最小堆来维护。直接跟堆顶元素比较即可。 --------------------编程问答--------------------
你说数字小于100个 那肯定有1个数字大于1g了 这个数字请问你用来干什么？造宇宙飞船吗？普通数字有那么大吗 还java不能处理的数字 到底谁不实际？到底谁在空想？ --------------------编程问答--------------------
我怎么知道数字用来干嘛的，普通文件也没100G啊，你给了100G的文件却来问我里面的数字用来干嘛，可笑！如果数字比内存还大，那么请问你怎么用java来处理，一处理肯定是内存溢出。
结论：别和我来钻牛角尖，本来就是一个开玩笑性质的答案，偏要和我来搞，你想搞就搞，我也不怕你。就你这种样子，到哪也不会有前途。 --------------------编程问答-------------------- 脑筋急转弯。。。。。 --------------------编程问答-------------------- 逗号， 逗号啊。 有逗号好。 O(∩_∩)O~ --------------------编程问答-------------------- 谁能告诉我100G文件怎么读取啊？？ --------------------编程问答-------------------- 好难啊 --------------------编程问答-------------------- 等高手出来回答大文件数据处理细节 --------------------编程问答-------------------- 我觉得可以用以下思路：
1。 双线程操作，一个读一个处理读来的数据
2。 两个线程操作同一个LIST对象，可以以读一千个数字作为缓存体积，读入的数据追加在LIST对象中。
3。 重写Comparator，用Collections.sort逆序排序，最后删除LIST对象中后1000个数字
4。 用同步控制节奏 --------------------编程问答-------------------- 处理大文件只要注意避免在内存中保留太多闲置数据就行 --------------------编程问答-------------------- 学习了 --------------------编程问答-------------------- up --------------------编程问答-------------------- 这题目直接跳过不做
如果100G只有一个数字 你读得出来吗 --------------------编程问答--------------------
--------------------编程问答-------------------- 内外结合的排序法估计才可以吧。
public class Pick100 {
//TreeSet排序效率最高
private TreeSet<Double> treeSet = null;
public Pick100(){
treeSet = new TreeSet<Double>();
}
/**
* 读取文件并放到集合treeSet中
* @param fileName
*/
public void doPick(String fileName){
File file = new File(fileName);
InputStream is = null;
//一次读1024个字节
byte[] b = new byte[1024];
try {
is = new BufferedInputStream(new FileInputStream(file));
//每次取一定长度字节
while(is.read(b) > 0){
//转换为字符串
String str = new String(b);
//用逗号拆分成数组
String[] numArr = str.split(",");
//为了防止一个数字被截断而不完整，先保留最后一个数字
String lastNum = "";
//把数组中的数值放到集合中
for(int i=0;i<numArr.length;i++){
String numStr = numArr[i];
Double num = new Double(numStr);
if(i == 0){
if(lastNum != null){
numStr = lastNum+numStr;
}
}else if(i == numArr.length-1){
lastNum = numStr;
}else{
treeSet.add(num);
}
if(treeSet.size()>100){
treeSet.remove(treeSet.first());
}
}
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
/**
* 打印treeSet中的数据
*
*/
public void print(){
Iterator<Double> it = treeSet.iterator();
while(it.hasNext()){
Double db = it.next();
System.out.println(db);
}
}
public static void main(String[] args){
Pick100 pick = new Pick100();
pick.doPick("numbers.txt");
pick.print();
}
}
--------------------编程问答-------------------- 上面把数组中的数值放到集合中判断部分貌似写错了，自己承认错误~
--------------------编程问答-------------------- 保持一个Number[100]的数组有序，小于最小值不管，大于最小值找到位置插入，排出最小元素。
--------------------编程问答-------------------- mark --------------------编程问答-------------------- . --------------------编程问答-------------------- 1.用最小值（如Integer.MIN_VALUE）初始化一个大小为100的小顶堆
2.线性扫描这100G的数字，直到最后，遇到当前数字n则：
3.若n小于小顶堆的顶，则返回2步继续扫描，若n大，则：
4.将小顶堆的顶的值修改（或说增加）为n，调整堆使之仍旧符合小顶堆的性质，返回2步继续扫描。 --------------------编程问答-------------------- 最小堆 --------------------编程问答-------------------- d --------------------编程问答-------------------- 学习学习 --------------------编程问答--------------------
就是 --------------------编程问答-------------------- 先分段，比如100段，然后采用冒泡算法，分别取出最大的100个数，组成10000个数组成的序列，在采用冒泡算法，很简单的 --------------------编程问答--------------------
sealed--------------------编程问答--------------------
你可以分成100段，每段1G数据，然后再分100段，每段10M数据
像美国航空航天局的一张最大太空照片就有20+G，怎么办？显然不可能是一个文件，但可以分段 --------------------编程问答--------------------
如果是我，我会这样回答：
1、定义一个byte数组，在知道硬盘扇区大小的情况下该数组的大小和硬盘扇区相同，否则该数组的大小大概为4-8KB;
2、通过二进制读取文件内容，每次读取以上的数组的大小；
3、对读取的内容按顺序进行分析，得到里面包含的所有整数（遇','停止）；
4、通过最小堆保存最大的100个数；
5、还有一些边界处理的（如如果最多的字符并不是','时对byte数组的处理等等；
6、如果是多核的机器，可以开多几个线程一起算（这个问题多线程的程序很容易写的），方法与上面类型，只是到最后再比较每个线程的堆中的100个值。 --------------------编程问答-------------------- 首先将数据分成100块，每块1G，找出每块里面的100个最大数，写在一个配置文件中，然后读取配置文件中的数据进行比较，找出最大的100数。我想应该可以的。 --------------------编程问答-------------------- 学习学习，共同进步！
--------------------编程问答--------------------
顶这个回答~~ --------------------编程问答-------------------- 哎，许多人没看清题目就在那里大放阙词，题目没要求排序， 只要求找出最大的个100个数字，看好这点啊
什么多线程，内存大小都统统不需要考虑的，只需要考虑的是算法。 --------------------编程问答--------------------
这位兄才思路是对的 不过100G的大文件不使这样读取的
我的思路：在这位兄才基础上，对文件读取方法进行优化。将100G的文件分为N段，比如每段100M，用随即流RandomAccessFile每次读取100M大小的文件，这样在比较就可以啦.JDK方法说的很详细
java还提供一种流，内存映射文件 在java.nio包下 哈哈，这才是强大的大文本读取 --------------------编程问答-------------------- 学习了! --------------------编程问答-------------------- 路过 --------------------编程问答-------------------- 貌似是一个很难的问题啊，对我这个菜鸟来说不太懂啊，呵呵 --------------------编程问答--------------------
这位兄弟最有才 呵呵 你不读入内存你怎么判断它哪个大哪个小啊 排序难道不需要比较么 呵呵 --------------------编程问答-------------------- 谁要是能够用C++把它给做出来 我算是服了他！
不要光讲理论，理论大多数人都能讲，问题是你能不能把它给求出来？
空谈大道理是求不出答案的。
呼唤高手解答…… --------------------编程问答-------------------- 期待高手出现 --------------------编程问答-------------------- 先排序吧，然后再找！！ --------------------编程问答-------------------- 至少在内存中操作时不可能的，要是我，先分割存入数据库，然后用select语句配合order直接取出前100个就行啦！ --------------------编程问答--------------------
这题不难吧...整个文件读一次就可以了,没必要排序;至于数据库啥的更不需要.在一堆无序数中找一个最大数不难吧?把1推广到100就行了. --------------------编程问答--------------------
你没看题么?只要你找100个最大的,谁要你排序了?3 1 2不排成1 2 3你就找不出那个3了?
--------------------编程问答--------------------
当然,前提是这些数字最大不能超过使用的语言所能表达的最大数值.否则处理会比较复杂. --------------------编程问答-------------------- 好好厉害啊 --------------------编程问答--------------------
同问！ --------------------编程问答-------------------- --------------------编程问答-------------------- MARK --------------------编程问答-------------------- 我觉得 还是做外部排序 --------------------编程问答-------------------- mark --------------------编程问答-------------------- 留名了。 --------------------编程问答-------------------- 直接告诉他，用100G全存数字，是不是不便于管理！
分级试试！看能不能用下FFT的思想！ --------------------编程问答-------------------- 学习了 --------------------编程问答-------------------- 大家考虑的太多了 这个应该是普通数值，不会出现读不出的数字来，考的不是这点，是你解决问题的思维发散能力。 我觉得有楼上说的比较长度，只要回答这点，考官觉得你考虑问题比较灵活，你就已经通过了。并不是所有问题都要完完全全给出正确答案出来 --------------------编程问答-------------------- 100G的数据，有没有要求说内存多大？之前好像看过类似的问题。 --------------------编程问答-------------------- 1.我觉得首先把特殊情况给人家说明下,只要我们想到了就行了,比如什么一个数字大于1g了这些,暂不考虑.
2.对于分段我觉得不可行,你不能保证这个段中选出的最大数据在别的数据段中就一定够大,指不定这个段中选出的最大数在别的段中是最小的呢.
3.对于建一100的数组,然后将数组中最小数与读入数比较这种方法理论可行,但是考虑到实际的100G数据肯定不可行,要不然得等到什么年月啊.
4.期待高手给出正解......... --------------------编程问答-------------------- --------------------编程问答-------------------- UP
补充：Java , Java SE
