为大家谋福利的我给大家贴个面试题，是今天我一个软件公司面试的。

Question

1. 有一个ArrayList，里面包含N个Integer，其中的Integer都是由1至N+1的数字构成，并且不重复，但是有一个1至N+1的数字对应的Integer不存在ArrayList中，求该数。public static void main(String[] args){ ArrayList list= new ArrayList();
 list.add(Integet(7));
 list.add(Integet(8));
 list.add(Integet(1));
 list.add(Integet(2));
 list.add(Integet(3));
 list.add(Integet(4));
 list.add(Integet(5));
 
}
public int getMissing(ArrayList list){
int len = list.size();
for (int i = 1; i <= len; i++) {
int j = 0;
while (j < len) {
Integer Val = (Integer) list.get(j);
int value = Val.intValue();
if (i == value)
break;
j++;
}
if (j == len) {
return j;
}
}
return -1;
}2. 有一个二叉树类如下。然后写出遍历二叉树的方法printTree。
class BinaryTree{
 class Node{
  String value;
  Node leftNode;
  Node rightNode;
 }
 public void printTree(Node root){
  reDo(root,0);
 } public void reDo(Node node,int depth){
  if(node != null) {
    System.out.println(space()+node.value);
    reDo(node.leftNode,depth+1);
    reDo(node.rightNode,depth+1);
  }
      
 } public String space(int len){
   StringBuffer bs = new StringBuffer();
   for(int i=0; i<bs.length();i++){
    bs.append(" ");
   }
 }
}3. 有int型数字如下，123，1234，12345，123456，1234567，12345678，123456789
求一个方法，输出123 1,234 12,345 123,456 1,234,567 12,345,678 123,456,789public String printComma(int input){
 StringBuffer bs = new StringBuffer(input + "");
 int index = bs.length() - 3;
 while (index > 0) {
  bs.insert(index, ",");
  index = index - 3;
 }
 return bs.toString();
}4.equals(),hasCode()的作用。5.Object对象有哪些方法?
  equals(),clone(),notify(),notifyAll(),wait(),wait(long time),wait(long time,int nanos)
  hasCode(),toString(),getClass()。6.RuntimeException,非RuntimeException的区别和例子。7.Singleton模式8.共享数据在web中的范围
  page,request,seesion,application9.Servlet的生命周期。
  servlet有良好的生存期定义，包括加载，实例化，初始化，处理请求，服务结束。由javax.servlet.Servlet接口以下方法表达
  init(),service(),destroy()。10.abstract和interface的区别。
  abstract中可以有自己方法的定义和说明，interface只是存在变量和方法的定义。当需要的时候，我们可以inplements多个接口，但是只能extends一个类。11.实现多线程有哪几种方法。
第一种，class MyThread extends Thread{..}  MyThread t = new MyThread(); t.start();
第二中，class UrThread implements Runnable{...} Thread t = new Thread(new UrThread()); t.start();12.ArrayList和Vector的区别。
  Vector中的方法是synchronized的，性能上较ArrayList差点。
  当增长时，Vector默认增长原来的一倍，ArrayList默认增长原来的一半。13.java实现序列化的方法是实现serializable接口，具体怎么做。
   
14.String a = "test"; String b = new String("test"); a==b (false)
   String c = "te"+"st"; a==c (true)15.
public synchronized void aMethod1(){}public void b aMethod(){
 synchronized("test"){
  
 }
}A a1 = new A();
A a2 = new A();a1.aMethod1();
a2.aMethod1();//不需要等待a1.aMethod2();
a2.aMethod2();//需要等待16.编程性能方法的讨论，ArrayList，HashMap，StringBuffer。17.Struts的DispatchAction,Action的区别。RequestProcessor的作用。

Answer 1

楼主低于题给的答案不正确：
import java.util.*;
public class IceCream {
public int getMissing(List<Integer> list) { int[] array = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
array[i] = list.get(i).intValue();
}
Arrays.sort(array);
for (int i = 0; i < array.length; i++) {
if ((i + 1) != array[i])
return i + 1;
}
return -1;
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
list.add(new Integer(7));
list.add(new Integer(8));
list.add(new Integer(1));
list.add(new Integer(2));
list.add(new Integer(3));
list.add(new Integer(4));
list.add(new Integer(5));
IceCream ic = new IceCream();
int result = ic.getMissing(list);
System.out.println(result);
}
} // /:~

Answer 2

LZ第一题的答案明显不对
给个简单的方法吧 public static int getMissing(ArrayList list){
Integer[] array = new Integer[list.size()+2];
for(int i=0;i<list.size();i++){
Integer obj = (Integer) list.get(i);
array[obj.intValue()]=obj;
}
for(int i=1;i<array.length;i++){
if(array[i]==null){
return i;
}

}
return -1;
}

Answer 3

我上面给那个方法有点错误，修正如下：
public int getMissing(List<Integer> list) {
int[] array = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
array[i] = list.get(i).intValue();
}
Arrays.sort(array);
for (int i = 0; i < array.length; i++) {
if ((i + 1) != array[i])
return i + 1;
}
return array.length+1;
}

Answer 4

第三题 public void testPrint(int num){
DecimalFormat format = new DecimalFormat("#,###");
System.out.println(format.format(num));
}这样修改可能要简单点.

Answer 5

不好意思，第一题我错了，我面试答的时候也错了，现在谦虚地改正如下：
public int fun05(List list) {
Conica.pl("\nlist:\n"+list);
int N = list.size();
for(int i=1;i<=N+1;i++){
int j=0;
while(j<list.size()){
Integer Int = (Integer)list.get(j);
if(Int.intValue() == i)
break;
else
j++;
}
if(j==N){
return i;
}
}
return -1;
}
测试：
public static void main(String[] args) {
Test1 test = new Test1();
int[] ints0 = {1,2,3,4,5,6,7,8,9};
int[] ints1 = {1,2,3,4,5,6,7,8,10};
int[] ints2 = {1,2,3,4,5,6,7,9,10};
int[] ints3 = {1,2,3,4,5,6,8,9,10};
int[] ints4 = {1,2,3,4,5,7,8,9,10};
int[] ints5 = {1,2,3,4,6,7,8,9,10};
int[] ints6 = {1,2,3,5,6,7,8,9,10};
int[] ints7 = {1,2,4,5,6,7,8,9,10};
int[] ints8 = {1,3,4,5,6,7,8,9,10};
int[] ints9 = {2,3,4,5,6,7,8,9,10};
List list0 = new ArrayList();
List list1 = new ArrayList();
List list2 = new ArrayList();
List list3 = new ArrayList();
List list4 = new ArrayList();
List list5 = new ArrayList();
List list6 = new ArrayList();
List list7 = new ArrayList();
List list8 = new ArrayList();
List list9 = new ArrayList();
for(int i=0 ;i<ints0.length;i++){
list0.add(Integer.valueOf(ints0[i]));
list1.add(Integer.valueOf(ints1[i]));
list2.add(Integer.valueOf(ints2[i]));
list3.add(Integer.valueOf(ints3[i]));
list4.add(Integer.valueOf(ints4[i]));
list5.add(Integer.valueOf(ints5[i]));
list6.add(Integer.valueOf(ints6[i]));
list7.add(Integer.valueOf(ints7[i]));
list8.add(Integer.valueOf(ints8[i]));
list9.add(Integer.valueOf(ints9[i]));
}
Conica.pl("i:"+test.fun05(list0));
Conica.pl("i:"+test.fun05(list1));
Conica.pl("i:"+test.fun05(list2));
Conica.pl("i:"+test.fun05(list3));
Conica.pl("i:"+test.fun05(list4));
Conica.pl("i:"+test.fun05(list5));
Conica.pl("i:"+test.fun05(list6));
Conica.pl("i:"+test.fun05(list7));
Conica.pl("i:"+test.fun05(list8));
Conica.pl("i:"+test.fun05(list9));
}

Answer 6

第一题的最简方法：
  把ArrayList中的数一次变量求其和sum，然后用1+2+……+(n+1)-sum即可得到结果。
 用排序和其他方法都有点浪费了，呵呵～

Answer 7

不错的面试题，收起来，慢慢研究，以后找工的时候或许用得到！THX

Answer 8

第一题的最简方法：
  把ArrayList中的数一次变量求其和sum，然后用1+2+……+(n+1)-sum即可得到结果。这个方法强！！！看来还得有个灵活的数学脑子啊。

Answer 9

这个方法是不是最简单的啊求和之后再减也得用循环来做吧。。import java.util.ArrayList;
class ArrayInteger{
public static void main(String[] args) {
// TODO: Add your code here
ArrayList list=new ArrayList();
list.add(new Integer(1));
list.add(new Integer(2));
list.add(new Integer(3));
list.add(new Integer(4));
list.add(new Integer(5));
list.add(new Integer(6));
list.add(new Integer(8));
list.add(new Integer(9));
System.out.println (getMissing(list));
}

public static int getMissing(ArrayList list){
int n=0;
for(int i=1;i<list.size()+1;i++){
Integer a=(Integer)(list.get(i-1));
if(i!=a.intValue()){
System.out.println (a);
n=i;
break;
}
}
return n;
}

}

Answer 10

楼上的，如果数字不是按从小到大的顺序排列的话你的方法就行不通了，至少要用到Collections.sort()。而用求和再减的方法，至少不用考虑排序了。

Answer 11

第一题的这个ArrayList里面包含的N个Integer没说一开始是从小到大排的咧？？

Answer 12

ArrayList list= new ArrayList();
    list.add(new Integer(7));
    list.add(new Integer(8));
    list.add(new Integer(1));
    list.add(new Integer(2));
    list.add(new Integer(3));
    list.add(new Integer(4));
    list.add(new Integer(5));
    int obj = 0;
    for(int i = 1;i < 9;i++){
      if(list.indexOf(new Integer(i)) == -1){
        obj = i;
      }
    }
    System.err.println("" + obj);

Answer 13

对于第一道题的求值，由于很有规律性，可以用另外一种思路：1+2+...+N+1的值 减去集合里面的总和
 
public getValue(ArratList list){
   
  /*count:1--n+1的总和*/
   int count=0;
  /*集合里整数的总和*/
   int listcount=0;
  /*集合的有效空间，长度*/
   int length=0; 
  /*所求的值*/
   int value=0;
    
   length=list.size();   count=(1+length+1)*n/2;
   
  for(int i=0;i<length;i++)
   listcount=(Integer)list.get(i).intValue()+listcount;
  
  value=count-listcount;
  return value;
}代码我可能不好，但我觉得最有意思的就是对一个问题有不同的思路，不管好的思路还是差的思路，
刚来论坛不久，希望和大家交朋友

Answer 14

无所不在的二分查找（Programing pearls）

Answer 15

public class Arraysort {
static final Integer[] data = {
new Integer(1),
new Integer(2),
new Integer(3),
new Integer(5),
new Integer(4),
new Integer(8),
new Integer(7),
new Integer(10),
new Integer(9),
}; static int count =0;
static int getMissing(){
int result=-1;
boolean flag = true;
for(int i=1;i<data.length+1;i++){
flag = false;
for(int j=0;j<data.length;j++){
if(data[j].intValue() == i ){
flag = true;
count +=1;
break;
}
}
if(!flag)
result = i;
}
return result;
}

public static void main(String[] avg){

System.out.println(Arraysort.getMissing());
System.out.println(Arraysort.count);
}

Answer 16

public getValue(ArratList list){
   
  /*count:1--n+1的总和*/
   int count=0;
  /*集合里整数的总和*/
   int listcount=0;
  /*集合的有效空间，长度*/
   int length=0; 
  /*所求的值*/
   int value=0;
    
   length=list.size();   count=(1+length+1)*n/2;
   
  for(int i=0;i<length;i++)
   listcount=(Integer)list.get(i).intValue()+listcount;
  
  value=count-listcount;
  return value;
}这个算法没有看明白  N是什么

Answer 17

3. 有int型数字如下，123，1234，12345，123456，1234567，12345678，123456789
求一个方法，输出123 1,234 12,345 123,456 1,234,567 12,345,678 123,456,789这个题的逻辑关系没看出来 
不知道能不能用数学的处理方法来做
// 123,
// 1234 - 1000 = 234 
// 12345 -12000 = 345 123
// 123456 - 123000 = 456 1
// 1234567 - 1234000 = 567 12
// 12345678 - 12345000 = 678 123
// 456
// 789

Answer 18

tolimit(没有把握就永远没有幸运)：
你面试的是什么公司，能方便提示一下吗？