外企一变态笔试题，高分求牛人解答!!!!!

Given an array of integers stored in a file with one number per line, 
find all the pairs of integers that add up to 8. The output will also needs 
to be stored in a file with one pair per line.
>
> An example input array looks like this:
> 3
> 2
> 4
> 6
> 5
> 7
> 20
> 1
>
> The output will be like this:
> 3 5
> 2 6
> 7 1
>
>You need to do the following.
>
>a) Write a simple design document to outline your approach.
>
>b) Write a java program to implement your design with proper comments. 
Please note that the input array of integers might be very large. For 
example, what about 10 million numbers? Also, what about there are some 
negative numbers?
>
>c) Write some junit test cases so that someone else could test your 
program.

87 个解决方案

#1

> 3 + 5 = 8  
> 2 + 6 = 8
> 7 + 1 = 8

#2

好象不是很难啊,就是找能加一起得8的俩数,打出来就可以了

#3

循环 readLine

#4

a
b
c
呢
大家做题怎么不看题目哦？

#5

题描述的是这样的问题：一个文件中存储了一个整数数组。存储格式为每行一个数字。要求是：找出能加起来等于8的一对数字，并按格式输出，存储到文件当中。
问题A;写出一个简要的设计文档描述你的方法。
问题B：编写一个JAVA程序实现算法。并标注适当的注释。提醒：存储的数字量可能非常大。如数亿的数字。怎么处理。如果当中出现 负数呢。又如何处理？
问题C：写出一个关于这个程序的JUNIT测试用例。

#6

它这个数据量可能很大,有点难道.
如果有一亿行的数据,而且还有负数
确实要考虑性能的.

#7

够变态了

#8

是啊。考虑到很多方面，思路很简单。但写出一个健壮，高效率的算法，确实有点难度。看似简单。做到却很难

#9

完全同意

#10

是很bt

#11

扔笔,曰:变态,88

#12

bt, JUnit Test Case 向来用jbuilder直接生成的，自己只要改几个参数就好了， 现在要写出来。。。。我反正不会。。。

#13

一个字:烦

#14

我靠,招开发还是招测试啊?谁他妈的没准备能写出来啊??

#15

关键是怎么写高效的算法。而且是读写文件。

#16

在大也没关系啊！java提供了BigDecimal 足够处理了吧，不管有负数没负数
循环读取行，作为BigDecimal   设 读取的数为y,要求的数为x 结果为 8
y + x =8 =>  x = 8 -y


数亿的数字
也没什么关系，分批读取，一次读取1000个，计算了保存，在读取1000个。

#17

10 million=1亿？

马克
路过闪人

#18

等会儿做一个试试

#19

数亿的数字
也没什么关系，分批读取，一次读取1000个，计算了保存，在读取1000个。
***************************************************************
前1000个和后1000就没有关系了吗

#20

首先有一个问题 是否包括负整数

1. 如果不包括负整数 那么所有有效的数字在0-8之间 而且当0-8之间的数字都出现一遍之后就不用继续读取了
2. 如果包括负整数 那就麻烦咯

#21

to CAYU(中原)： 不好意思。可能是我没有说清楚 。你说的X，Y都应该出现在文件中的数组中，而不是读取X。直接求得Y就行了。Y值也要求是其中的一个数字吧。所以分批读取，计算再存这样的思路是错的。 涉计到 的算法可能会有排序和查找。

#22

NB

#23

相差最大才8吗,前面不管多少位,超过3位以上(含三位),正的就到负的里找,负的当然就要到正的里找,除了后两位,前面不管多少位,必须要一模一样.

   那就分三步,(1).先判断是否大于100,(2).然后找位数相同的,不同的肯定不行(3)从前面开始到倒数第三位结束,一位一位比较,找一模一样的.

   要是数组是按大小排序的那自然好办的多,要是没顺序,就象楼上的人说的,10000个数里找,找到了几个就列出来几个,并踢出去,找了一遍之后,再一万一万的分.

#24

是的。所以我的思路 是这样子的。首先全部读取出来 并排序，分成3组。负数组。0-8成一组，大于8的成一组。那么针对负数组 ，对其计算8-(负数) 结果 应该到大于的组中去找，找到后放到一个MAP中，同样针对0-8的这组 ，在自身中查找。得到结果 放到MAP中，最后输出到文件中。你们说。这个算法怎么样？ 我不会写JAVA程序 。求一JAVA程序实现

#25

waiting.....

#26

先站个坐，吃了饭再说

#27

把所有的数都存到ArrayList（或者别的List）中
ArrayList A = { new BigDecimal（从文件读出的数字） }
然后做一个循环，判断A中的数字 + 8 或者 - 8 的数在A中存在不存在。
如果存在， 则把两个数输出出来，并且从A中删除这2个数，
直到循环存在。

其实这道题的条件有问题，如果数字非常大，
文件里的数非常多，则无论采取什么算法都是非常费内存的。
因为必须把文件的书全都读到内存中进行操作

#28

是啊。分组排序只是减小查找范围。 也不是条件有问题。这是很现实 的一个问题。 存在很多可能性。有可能存在重复的数字

#29

不用想的那么恐怖，直接System.out.println();
就OK了，

#30

按8取余写数据到8个临时文件中，8n+1的数去8n+7的文件里去找，然后8n+2，8n+3，8n+4，最后8n。算五次就行了。

#31

只看个位数的话：
0--->2
1--->3
2--->4
3--->5
.......
这样可以节省一些比较的时间。

#32

按8取余写数据到8个临时文件中，8n+1的数去8n+7的文件里去找，然后8n+2，8n+3，8n+4，最后8n。算五次就行了。?
怎么理解？

#33

mark

#34

waiting ..

#35

应该主要是考i/o吧，我写了个简单的，没有考虑性能方面，读取文件两个两比较，不知道合不合要求
import java.io.*;
import java.util.*;

public class FindPars{

public void findPars(String file1,String file2,int number)throws Exception{

RandomAccessFile in=new RandomAccessFile(file1,"r");
RandomAccessFile out=new RandomAccessFile(file2,"rw");

int index=3;

        String value="";
while ( (value=in.readLine())!=null )
{

            String next="";
            while ( (next=in.readLine())!=null)
            {

                           int a1=0;
   int a2=0;

   if( !value.equals("")&&!next.equals("") ){
  a1=Integer.parseInt(value);
  a2=Integer.parseInt(next);
   }

if((a1+a2)==number){
  String output=value+" "+next;
          out.writeBytes(output);
  out.writeBytes("\n");
}
            }
in.seek(index);
index=index+3;


}
in.close();
out.close();
}
public static void main(String[] args)throws Exception{

String in="E:/a.txt";
String out="E:/b.txt";

new FindPars().findPars(in,out,8);
}
}

#36

java我不会，但是这个题目估计是算法了。
和其他楼得一样，BT得题目

#37

上面我没有考虑负数的情况，可以判断一下:
sum=0;
if ( a1<0 && a2<0)
  sum=-(Math.abs(a1)+Math.abs(a2));
else if(a2<0){
  sum=a2+a1;
}
else{
  sum=a1+a2;
}
if (sum==number){
................


我发现当记录多的时候，效率非常的底，也可以用一个List保存比较过的，以后的每个元素先查List看是否比较过，这样可以避免很多重复的比较，但是i/o，不断的读和写，始终性能底

  等待看到更好的实现

#38

嗯。思考。。。。

#39

mark!

#40

11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

#41

utterly stupid

#42

变态
看不懂

#43

有翻译：题描述的是这样的问题：一个文件中存储了一个整数数组。存储格式为每行一个数字。要求是：找出能加起来等于8的一对数字，并按格式输出，存储到文件当中。
问题A;写出一个简要的设计文档描述你的方法。
问题B：编写一个JAVA程序实现算法。并标注适当的注释。提醒：存储的数字量可能非常大。如数亿的数字。怎么处理。如果当中出现 负数呢。又如何处理？
问题C：写出一个关于这个程序的JUNIT测试用例

#44

mark

#45

看起来主要是考算法,不过题目要求也不是很明确,会不会有重复数字?
而且读文件操作,有上亿的数据,性能怎么都不高.
同意楼上的,果然很BT````
飘走````

#46

我想出来的算法：

1: 只有个位数(len==1)
   '0'对应'8','1'找'7'...
2: 大于10(len > 1)
       假设:A+B=8
            A>0,B< 0
  2.1:  A的个位是8,9,则
A.length == B.length
且A.substring(0, A.length -1) 与 B.substring(0,A.length-1)相等
        且B的最后一字符是'0',或者'1'
  2.2   A的个位是0..7
    2.2.1  十位大于'0'
           如: A=11111 B=11103;A=11 B=3
           特点:
           A.length == B.length 或者 A.length == B.length+1
           A.substring(0, A.length -2) 与 B.substring(0,A.length-2)相等
           若A的个位是'0',则B的个位是'2',若A的个位是'1',则B的个位是'3'.......
           若A的十位是'1',则B的个位是'0'('1'-1)...   (若A长度为2且十位为'1'单考虑)

    2.2.2  十位是'0'
            （说起来挺麻烦的）
   如: A=8100000
             则B=8099992
            特点:   则A.length == B.length 或者 A.length == B.length+1
                    个位数'0',对应'2'
                    A的3-6(从十位开始连续为'0'的一段)的位置全是'0',B的3-6位全是'9'
    A的第二位(第一个不是'0'的位置)是'1',则B的相应第二位是'0'('1'-1)
                    A和B第二位以前的字符相同

to wizardblue() ：
   大家学习的地方，有想法就说出来，管他对不对呢，没有什么stupid的。

#47

不会有重复的

#48

先排序,再来

#49

up

#50

同意 caimaohua(杨白劳) ，先排序,再来

快速排序，最好能在二分的过程中排除一组。

两个指针，一指头（最小），一指尾（最大），加起来>8,则尾指针向小移动，<8,头指针向大移动。

可以用 二分查找 大幅移动指针。

如果有重复，可以直接在数组内重复。如果数字会重复很多次，可以加一个表示，重复几次。