算出num个数内的质数

质数即大于1的一个自然数，这个数可以被1和自身整除，如算出20之内的质数，它们有2，3，5，7，11，13，17，19这样的数字。这道题也是面试过程中笔试常问的一道题。

这道题的其目的在于：

1. 看笔试者的数学还记不记得

2. 看笔试者平时的算法

因此答题有两种。

第一种，通用做法

public class prime {
public static boolean isPrime(int num) {
	for (int i = 2; i <= Math.sqrt(num); i++) {
		if (num % i == 0) {
			return false;
		}
	}
		return true;
}

public static void main(String[] args) {
	for (int j = 2; j <= 20; j++) {
		if (isPrime(j)) {
			System.out.println(j + " is a prime");
		}
	}
}

}

这种做法是对每个2--num个数内的数，进行扫描，需要用到2个循环，其重复度高，效率低下，因此我们还有一种更先进的做法。

“筛选"法

public class Prime2 {

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		int n = 20;

		int[] array = new int[n];

		for (int i = 2; i < n; i++) {

			array[i] = i;

		}

		for (int i = 2; i < n; i++) {
			if (array[i] != 0) {

				int j, temp;

				temp = array[i];

				for (j = 2 * temp; j < n; j = j + temp) {
					array[j] = 0;
				}
				System.out.println("\n");

			}

		}

	}

}

它的原理就是把所有的偶数去掉后即留下质数。

约瑟夫环算法

假设有20个人手拉手围成一圈，顺时针开始报号，报到3的人出圈，然后继续往后报，报到3的人出圈，依次把所有报到3的人都踢出圈，最后剩下一人也踢出圈，问先后被踢出圈的那些人原来是圈内的几号？

不难不难，关键记住这个环的算法（有人看到这个”环“字，要笑了，打住，别想歪了，俗人！）

环的算法即闭合算法，永远依次1，2，3，4，5...20...1再2,3,4,5...20这样一直转下去，假设要让20以内的20个数以环型转起来，它的核心算法如下：

int flag=0;
while(true){
		flag=(flag+1)%n;
}

即”取模运算“，循环继续。

有了核心算法，我们的问题就可以解决了，来：

public class JosephCircle {

	/**
	 * @param args
	 */
	public void josephCircle(int n,int k){
		int flag=0;
		boolean[] kick = new boolean[n];
		//set kick flag to False;
		for(int i=0;i<n-1;i++){
			kick[flag]=false;
		}
		int counter=0;
		int accumulate=0;
		while(true){
			if(!kick[flag]){
				accumulate++;
				if(counter==n-1){
					System.out.println("kick last person===="+(flag+1));
					break;
				}
				if(accumulate==k){
					kick[flag]=true;
					System.out.println("kick person===="+(flag+1));
					accumulate=0;
					counter++;
				}
			}
			flag=(flag+1)%n;
		}

	}
	public static void main(String[] args) {
		JosephCircle jCircle = new JosephCircle();
		jCircle.josephCircle(20, 3);

	}

}

求Missed Number，找丢失的那个数

上次有朋友在美国去yahoo面试，说一道题把它给整了，题目如下：

说有一数组如 int[]{0,1,2} 这样的一个数组，这个数组的第一个必须从0开始，以次+1列出，该数组内最后一个数是这个数组的长度，因此：

int[]{1,2}, missed number为0

int[]{0,1,2}, missed number为3

int[]{0,2}, missed number为1

我朋友和我说这看上去有点像等差数列，我当时就在MSN里和他说：等差数你个头啊！

然后我朋友说，他用了两个循环嵌套也搞不定

我和他说：两个循环你个头啊

他在MSN上又要和我说什么，我还没等他把它打出来直接就是”你个头啊“回过去了。

大家看，这个找missed number是很好玩的一个东西，如果你想着用什么循环，什么算法，什么数据结构，我一律在这边回”你个头啊“，为什么，这么简单的东西，直接套公式啊，唉。。。

public class MissedNumber {

	public int findMissedOne(int[] numArray) {
		int sum = 0;
		int idx = -1;
		for (int i = 0; i < numArray.length; i++) {
			if (numArray[i] == 0) {
				idx = i;
			} else {
				sum += numArray[i];
			}
		}

		// the total sum of numbers between 1 and arr.length.
		int total = (numArray.length + 1) * numArray.length / 2;
		int missedNumber = total - sum;
		return missedNumber;

	}
}

来个测试类

public class TestMissedNumber {

	protected MissedNumber mNum = new MissedNumber();

	@Test
	public void testFindMissedOne() {
		int[] testArray = new int[] {0,2};
		int missedNumber = mNum.findMissedOne(testArray);
		System.out.println(missedNumber);
	}

}

简单吧，数组内的数的总和减去（（数组长度+1）*数组长度/2），即为missed number

所以你就循环求一个数组内各数的和即可鸟。

硬币组合问题

这道题老套了，即2角，5角，1角硬币，问有多少种组合可得到1块钱（一块钱？一块钱以前能够买奶油雪糕，一块钱以前可以买一个铅笔盒，一块钱以前可以吃到大排面，现在能干吗？）

public class CentsCombinations {
	public static void main(String[] args) {
		int i, j, k, total;
		System.out.println("1 cent"+"  2 cents"+"  5 cents");
		for (i = 0; i <= 10; i++)
			for (j = 0; j <= 5; j++)
				for (k = 0; k <= 2; k++) {
					total = i * 1 + j * 2 + k * 5;
					if (total > 10)
						break;
					if (10 == total)
						System.out.println("    " + i + ",    " + j + ",    " + k);
				}

	}
}

在List内去除重复值的问题

说有一个ArrayList{1,2,3,5,1,2,7,5,3,3,4,5,6,9,11,11}，它里面有许多重复数，我要求去除所有的重复数据，得到一个不重复的List。

有的人碰到这个问题，循环2个，嵌套，还有用二分算法的（这种人已经算好的了）。

要什么循环啊？

这道题考的是你对JDK的API是否熟悉，来看下面答案，如果以前没碰到过这个问题的人看完下面的答案后直接就吐血了

public class DuplicateValue {

	public void removeDuplicateValue() {
		List myList = new ArrayList();
		myList.add(1);
		myList.add(2);
		myList.add(1);
		myList.add(3);
		myList.add(4);
		myList.add(5);
		myList.add(6);
		myList.add(5);

		Set myset = new HashSet(myList);
		myList = new ArrayList(myset);
		Iterator it = myList.iterator();
		while (it.hasNext()) {
			System.out.println(""+it.next());
		}
	}

	public static void main(String[] args) {
		DuplicateValue dv = new DuplicateValue();
		dv.removeDuplicateValue();

	}

}

一道题即考了冒泡又考了二分

说有一数组int[]{1,2,2,4,6,8,9,5,3,7,5}，里面可能还有很多，想要知道”两两相加等于10“的这样的数有几对，可以重复如：2+6，6+2

上手就是冒泡

public Vector<SumPossibleBean> checkSumPossible(ArrayList<Integer> intList,
			int sumResult) {
		Vector<SumPossibleBean> possibleList = new Vector<SumPossibleBean>();
		int size = intList.size();
		for (int i = 0; i < size; i++) {
			for (int j = i + 1; j < size; j++) {
				if ((intList.get(i).intValue() + intList.get(j).intValue()) == sumResult) {

					SumPossibleBean spBean = new SumPossibleBean();
					spBean.setFirst(intList.get(i).intValue());
					spBean.setSecond(intList.get(j).intValue());
					possibleList.addElement(spBean);
				}
			}
		}
		return possibleList;
}

不错，两个循环嵌套，当考官问你，有没有更好的算法时，70%以上的人基本歇菜！！！

唉哎。。。二分来一个吗，以前在学校怎么学的？

public Vector<SumPossibleBean> checkSumPossibleBinSearch(
			ArrayList<Integer> intList, int sumResult) {
		Vector<SumPossibleBean> possibleList = new Vector<SumPossibleBean>();
		int size = intList.size();
		Collections.sort(intList);
		for (int i = 0, j = (intList.size() - 1); i < j;) {
			Integer s = intList.get(i);
			Integer e = intList.get(j);
			if ((s + e) == sumResult) {
				SumPossibleBean spBean = new SumPossibleBean();
				spBean.setFirst(intList.get(i).intValue());
				spBean.setSecond(intList.get(j).intValue());
				possibleList.addElement(spBean);
				i++;
				j--;
			} else if ((s + e) > sumResult) {
				j--;
			} else if ((s + e) < sumResult) {
				i++;
			}
		}
		return possibleList;
}

算法讲一些，讲多了枯燥，来几道问答题，如果你没准备过的话也一样可以让你爽到吐血。

Collection 和 Collections的区别 

Collections是个java.util下的类，它包含有各种有关集合操作的静态方法。 
Collection是个java.util下的接口，它是各种集合结构的父接口。

吐血了吗？没吐，OK，下面这道如果在面试时问到一定让你吐，面架构师的人50%以上被问到过这道题

什么时候用assert

断言是一个包含布尔表达式的语句，在执行这个语句时假定该表达式为 true。如果表达式计算为 false，那么系统会报告一个 AssertionError。它用于调试目的：  

assert(a > 0); // throws an AssertionError if a <= 0  

断言可以有两种形式：  

assert Expression1 ;  
assert Expression1 : Expression2 ;  

Expression1 应该总是产生一个布尔值。  
Expression2 可以是得出一个值的任意表达式。这个值用于生成显示更多调试信息的 String 消息。  

断言在默认情况下是禁用的。要在编译时启用断言，需要使用 source 1.4 标记：  

javac -source 1.4 Test.java  

要在运行时启用断言，可使用 -enableassertions 或者 -ea 标记。  

要在运行时选择禁用断言，可使用 -da 或者 -disableassertions 标记。

要系统类中启用断言，可使用 -esa 或者 -dsa 标记。还可以在包的基础上启用或者禁用断言。  

可以在预计正常情况下不会到达的任何位置上放置断言。断言可以用于验证传递给私有方法的参数。不过，断言不应该用于验证传递给公有方法的参数，因为不管是否启用了断言，公有方法都必须检查其参数。不过，既可以在公有方法中，也可以在非公有方法中利用断言测试后置条件。另外，断言不应该以任何方式改变程序的状态。

企业级开发写多了，忘了JAVA是一门计算机语言，计算机语言最早是用来做运算的

来一道

问：Math.round(11.5)等於多少? Math.round(-11.5)等於多少

Math.round(11.5)返回（long）12

Math.round(-11.5)返回（long）-11;

再来一道

问：short s1 = 1; s1 = s1+ 1;有什么错? short s1 = 1; s1 += 1;有什么错

short s1 = 1; s1 = s1 + 1;有错，s1是short型，s1+1是int型,不能显式转化为short型。可修改为s1 =(short)(s1 + 1) 。short s1 = 1; s1 += 1正确。

数组有没有length()这个方法? String有没有length()这个方法

数组没有length()这个方法，有length的属性。

String有有length()这个方法。

error和exception有什么区别?

error 表示恢复不是不可能但很困难的情况下的一种严重问题。比如说内存溢出。不可能指望程序能处理这样的情况。

exception 表示一种设计或实现问题。也就是说，它表示如果程序运行正常，从不会发生的情况。

abstract的method是否可同时是static,是否可同时是native，是否可同时是synchronized?

都不能 

可变类与不可变类的区别

所谓不可变类：

是指当创建了这个类的实例后，就不允许修改它的属性值。在JDK的基本类库中，所有基本类型的包装类，如Integer和Long类，都是不可变类，java.lang.String也是不可变类。

不可变类：

当你获得这个类的一个实例引用时，你不可以改变这个实例的内容。不可变类的实例一但创建，其内在成员变量的值就不能被修改。

如何创建一个不可变类？

这道题90%以上的人都会被挂或者只回答一半对，来看：

1. 所有成员都是private
2. 不提供对成员的改变方法，例如：setXXXX
3. 确保所有的方法不会被重载。手段有两种：使用final Class(强不可变类)，或者将所有类方法加上final(弱不可变类)。
4. 如果某一个类成员不是原始变量(primitive)或者不可变类，必须通过在成员初始化(in)或者get方法(out)时通过深度clone方法，来确保类的不可变。

四点中少一点，回答失败，来看一个例子：

public final class MyImmutableWrong {
	private final int[] myArray;

	public MyImmutableWrong(int[] anArray) {
		this.myArray = anArray; // wrong
	}

	public String toString() {
		StringBuffer sb = new StringBuffer("Numbers are: ");
		for (int i = 0; i < myArray.length; i++) {
			sb.append(myArray[i] + " ");
		}
		return sb.toString();
	}
}

以上不可变类书写错误，为什么？违犯了第四点

正确的写法：

public final class MyImmutableCorrect {
	private final int[] myArray;

	public MyImmutableCorrect(int[] anArray) {
		this.myArray = anArray.clone();
	}

	public String toString() {
		StringBuffer sb = new StringBuffer("Numbers are: ");
		for (int i = 0; i < myArray.length; i++) {
			sb.append(myArray[i] + " ");
		}
		return sb.toString();
	}
}

记住，不可变类的写法，我说过90%的人碰到这个问题会挂，另10%回答出。

但 是这10%里90%的人只回答出第1点，第2点和第3点，对于第四点即：

如果某一个类成员不是原始变量(primitive)或者不可变类，必须通过在成员初始化(in)或者get方法(out)时通过深度clone方法，来确保类的不可变。

则都没回答上来。

由此可判断这个面试者是真正写过还是只是为了应付面试而背原理。

所以，不要把面试当儿戏，每一次面试可能就是对自己这段时间的一个检查，看看自己平时缺了什么，JAVA是一门体系化的语言，要想面试的好，不只是死记硬背，是真的平时要化时间自己去补一些基础的。

上手就学SSH，JSP能连个数据库满天飞，这就是JAVA了？这就是中国IT了。。。这是错误的。

今天暂写这么多，下次继续。