今天参加金山的校园招聘，java笔试，回来仔细研究实现一下：

题目1：工厂两条生产线，三个工人，生产线上可以最多存放m个产品，当生产线满时，机器停止生产，等产品线不满时才继续生产，每条产线上一次只能允许一个工人取产品，编程实现该过程，使整个生产线能流畅 运行。

importjava.util.concurrent.ArrayBlockingQueue;importjava.util.concurrent.BlockingQueue;//多线程(生产者消费者问题)

class Producer extendsThread {//使用阻塞队列(BlockingQueue)控制线程通信

private BlockingQueuebq;public Producer(BlockingQueuebq){this.bq =bq;

}public voidrun(){//用于生产的元素

String[] strArr = newString[]{"Java","Structs","Spring"};for(int i = 0;i

Thread.sleep(200);//尝试放入元素，如果队列已满，则线程被阻塞

bq.put(strArr[i%3]);

}catch(Exception ex){

ex.printStackTrace();

}

System.out.println(getName()+"生产完成："+bq);

}

}

}class Consumer extendsThread{private BlockingQueuebq;public Consumer(BlockingQueuebq){this.bq =bq;

}public voidrun(){//每条生产线上只允许一个人去取(同步代码块“加锁-修改-释放锁”)

synchronized(bq){while(true){

System.out.printf(getName()+"消费者准备消费集合元素");try{

Thread.sleep(200);//尝试取出元素，如果队列已空，则阻塞该线程

bq.take();

}catch(Exception ex){

ex.getStackTrace();

}

System.out.println(getName()+"消费完成"+bq);

}

}//同步代码块结束，该线程释放同步锁

}

}public classUseBlockingQueue {public static voidmain(String[] args){//创建一个容量为1的BlockingQueue

int m=10;

BlockingQueuebq = new ArrayBlockingQueue(m);//启动2个生产者线程

newProducer(bq).start();newProducer(bq).start();//启动一个消费者线程

newConsumer(bq).start();

}

}

题目二：写一个java程序实现ArrayList类，最简单必须实现add()、remove().....

发现网上写成 什么样的都有，于是参考了一下jdk源码，简单实现了一个：

importjava.util.AbstractList;importjava.util.List;public class shixianArrayList extends AbstractList implements List{private transientObject[] elementData;private int size=0;public shixianArrayList(intinitialCapacity){super();if(initialCapacity=0;

}public intindexOf(Object o){if(o == null){for(int i=0;i

}

}

}else{for(int i=0;i

}

}return -1;

}//这里是不带索引的add()，带索引的也可以有

public booleanadd(E e){

elementData[size++] =e;return true;

}//这里是直接按照元素删除，按照索引删除的也可以有

public booleanremove(Object o){if(o == null){for(int index=0;index

fastRemove(index);return true;

}

}

}else{for(int index=0;index

fastRemove(index);return true;

}

}

}return false;

}private void fastRemove(intindex) {

modCount++;int numMoved = size-index-1;if(numMoved>0)

System.arraycopy(elementData, index+1,elementData , index,numMoved);

elementData[--size] = null; //让gc来做这个工作

}public static voidmain(String[] args){

String[] books={"java","structs"};

shixianArrayList booklist = new shixianArrayList();for(int i =0;i

booklist.add(books[i]);

}//booklist.remove(books[1]);

System.out.println(booklist.toStringFunc());

}//elementData为Object[]类型，不能直接打印

publicString toStringFunc(){

String tempstr="";for(int i=0;i

tempstr+=this.elementData[i];

}

}returntempstr;

}

}

题目三：已知两个字符串由不同的字母组成，一长一短，长的为A，短的为B。若所有在B中出现的字符都在A中出现，则返回true，否则返回false。假设短的长度为m，长的长度为n，要求算法的时间复杂度不能大于O(m+n)。

解法一：最先想到的解法，对字符串B中的每个字母在A中都遍历一遍(但是时间复杂度为O(m*n))

public classBinA {public static voidmain(String[] args){

String[] stra= {"a","a","b","b","b","b","c","d","e","e"};

String[] strb= {"a","a","c","d","e"};

Contain A= newContain();

System.out.println(A.containStr(stra, strb));

}

}classContain{public booleancontainStr(String[] stra,String[] strb){int count=0;//因为是要把strb中的每个元素拿出来跟stra中的每个元素比，所以要把strb的放在外面的循环

for(int i=0;i

{for(int j=0;j

{//因为数组中可能有重复元素，所以只要在stra中找到一个与strb相等的就就跳出来，才能保证count值=length

if(strb[i]==stra[j]){

count++;

j=stra.length;

}

}

}//count用作计数器，恰好比较了strb。length次说明在stra中每个strb中的数都有相等的了

if(count==strb.length){return true;

}return false;

}

}

解法二：设一个哈希表，对字符串A的字符遍历，将每个字符对应的哈希表中的值设为1。然后对B中的字符进行遍历，如果所有字符对应的hash值都为1，则返回true，否则返回false。时间复杂度为O(m+n)。

packageJingDian;importjava.util.HashMap;public classHashBinA {public static voidmain(String[] args){

String[] stra= {"a","a","b","b","b","b","c","d","e","e"};

String[] strb= {"a","b","c","d","e"};

hashSolve hs= newhashSolve();

System.out.println(hs.hashBinA(stra, strb));

}

}classhashSolve{public booleanhashBinA(String[] stra,String[] strb){

HashMap hm = new HashMap();int count=0;for(int i=0;i

{

hm.put(stra[i],1);

}for(int j=0;j

{//若strb中存在stra中没有的keyget()方法会返回空而报空指针错误，因此要判断是否为空

if(hm.get(strb[j])!=null&&hm.get(strb[j])==1){

count+= 1;

}

}//count只是一个计数器，如果每一个strb中字母得到的value都为一(都在stra中)则其长度为strb。length

if(count ==strb.length)

{return true;

}return false;

}

}