List里面两个单词的最近距离

看好几个面经有这题，有些面经写的不清楚还以为是word ladder呢， 终于有个大大写的特别清楚。
面经转载于：http://www.mitbbs.com/clubarticle_t/New_Mommy_and_New_Daddy/20337627.html
给一个words list, 输入两个单词，找出这两个单词在list中的最近距离(先
写了一个没有预处理的，又写了一个预处理建index的)
['green', 'blue', 'orange', 'purple', 'green']  f.distance(list, 'blue', '
green') # output 1
[Thoughts]:不断更新Two Pointer

public int closestWords(LinkedList<String> list, String a, String b){
    int aindex = -1;
    int bindex = -1;
    int index = 0;
    int res = Integer.MAX_VALUE;
    while(index < list.size()){
        if(list.get(index).equals(a)){
            aindex = index;
            if(bindex>=0)
                res = Math.min(res, aindex-bindex);
        }else if(list.get(index).equals(b)){
            bindex = index;
            if(aindex>=0)
                res = Math.min(res, bindex-aindex);
        }
        index++;
    }
    return res;
}

返回二叉树的镜像

面经上看来的题，Leetcode上有Clone Graph 和 Copy List with Random Pointer 都是生成一个结构的镜像，但是因为二叉树本身结构的原因，这个词比Leetcode上的两个题都要简单。

public TreeNode cloneTree(TreeNode root){
    if(root==null)
        return null;
    TreeNode newRoot = new TreeNode(root.val);
    newRoot.left = cloneTree(root.left);
    newRoot.right = cloneTree(root.right);
    return newRoot;
}

Concurrent - 实现一个blocking queue

这是Java Condition里给的示例代码，若是用linkedlist实现会更简单些。

class BlockingQueue{
    final Lock lock = new ReentrantLock();
    final Condition notFull = lock.newCondition();//两个Condition
    final Condition notEmpty = lock.newCondition();
    
    final Object[] items;
    int putptr, takeptr, count;
    public BlockingQueue(int capacity){//construct function， 初始化buffer的capacity
        items = new Object[capacity];
    }
    
    public void put(Object x){//put 方法
        lock.lock();
        try{
            while(count==items.length)//count代表现在buffer的size
                notFull.await();
            items[putptr] = x;
            if(++putptr == items.length)//若存满，则从头开始，若用linkedlist结构就不需要这一步了。
                putptr = 0;
            count++;
            notEmpty.signal();
        }catch(InterruptedException e){
            e.printStackTrace();
        }finally{
            lock.unlock();
        }
    }
    public Object take(){//take 方法
        lock.unlock();
        try{
            while(count==0)
                notEmpty.await();
            Object x = items[takeptr];
            if(++takeptr == items.length)
                takeptr = 0;
            count--;
            notFull.signal();
            return x;
        }catch(InterruptedException e){
            e.printStackTrace();
        }finally{
            lock.unlock();
        }
        return null;
    }  
}

Concurrent - H2O 问题

题目：  实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。

[Thought]: 下面的方法是用Condition， blockingqueue应该也可以，稍后做。 想了想这样有点不好，还是应该像宇宙一样把H2O单独拿出来做一个class，而不应该用static变量。 
改编自：http://www.cnblogs.com/lautsie/p/3430356.html 和  http://chengao789.blogspot.com/

public class Test2{  
    public static void main(String[] arg){
        for (int i = 0; i< 10; i++) {
            new Thread(new H2O("h")).start();
        }
        for (int i = 0; i< 5; i++) {
            new Thread(new H2O("o")).start();
        }
    }
}
class H2O implements Runnable
{
    static Lock lock = new ReentrantLock();
    static int hcount=0;
    static int ocount=0;
    static Condition hc = lock.newCondition();
    static Condition oc = lock.newCondition();
     
    private String particle;//string 指明run哪一个方法
    public H2O(String particle)//构造函数包含一个string， 新建thread时要指明。
    {
        this.particle = particle;
    }
 
    public void run()
    {
        if (particle.equals("h"))// 此线程call H 
            H();
        else if (particle.equals("o"))// 此线程call O
            O();
    }
     
    public void H()
    {
        lock.lock();
        hcount++;
        try {
            if (hcount >= 2 && ocount >= 1)
            {// generate water - 遇到一个H，只要原来有一个H, 一个O就够了
                hc.signal();
                oc.signal();
                System.out.println("H2O");
            }
            else
            {// wait
                hc.await();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }
     
    public void O()
    {
        lock.lock();
        ocount++;
        try {
            if (hcount >= 2)
            {// generate water - 遇到一个O， 原来有两个H就够了
                hc.signal();
                hc.signal();
                System.out.println("H2O");
            }
            else
            {// wait
                oc.await();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }
     
}

~~华丽丽来袭, 其实没什么区别，只是变换下结构, 但就这样，正规了许多，清楚了许多。

import java.util.LinkedList;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
class hclass implements Runnable{
    private H2O obj;
    public hclass(H2O obj){
        this.obj = obj;
    }
    public void run(){
        obj.H();
    }
}
class oclass implements Runnable{
    private H2O obj;
    public oclass(H2O obj){
        this.obj = obj;
    }
    public void run(){
        obj.O();
    }
}
class H2O{
    Lock lock = new ReentrantLock();
    int hcount=0;
    int ocount=0;
    Condition hc = lock.newCondition();
    Condition oc = lock.newCondition();
     
    public void H()
    {
        lock.lock();
        hcount++;
        try {
            if (hcount >= 2 && ocount >= 1)
            {// generate water - 遇到一个H，只要原来有一个H, 一个O就够了
                hc.signal();
                oc.signal();
                System.out.println("H2O");
            }
            else
            {// wait
                hc.await();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }
     
    public void O()
    {
        lock.lock();
        ocount++;
        try {
            if (hcount >= 2)
            {// generate water - 遇到一个O， 原来有两个H就够了
                hc.signal();
                hc.signal();
                System.out.println("H2O");
            }
            else
            {// wait
                oc.await();
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }  
}
public class Test2{  
    public static void main(String[] arg){
        final H2O obj = new H2O();
        for (int i = 0; i< 10; i++) {
            new Thread(new hclass(obj)).start();
        }
        for (int i = 0; i< 5; i++) {
            new Thread(new oclass(obj)).start();
        }
    }
}

Concurrent - 三个方法依次运行

CC上的题：
public class Foo{
    public Foo( ){...}
    public void first( ){...}
    public void second( ){...}
    public void third( ){...}
}
Foo的一个对象会传给三个不同的threads， 第一个thread调用first， 第二个thread 调用second， 第三个thread电泳third。 设计一个模式first is called before second， second is called before third。

class Foo {
    private Lock lock = new ReentrantLock();
    private Condition c1 = lock.newCondition();
    private Condition c2 = lock.newCondition();
    private Condition c3 = lock.newCondition();
    private int pointer = 1;//pointer代表下一个应该运行的方法

    public void first() {
        lock.lock();
        try {
            while (pointer != 1) {
                c1.await();
            }
            System.out.println("First method");
            pointer = 2;
            c2.signal();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }
    public void second() {
        lock.lock();
        try {
            while (pointer != 2) {
                c2.await();
            }
            System.out.println("Second method");
            pointer = 3;
            c3.signal();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }
    public void third() {
        lock.lock();
        try {
            while (pointer != 3) {
                c3.await();
            }
            System.out.println("Third method");
        } catch (InterruptedException e) {
            e.printStackTrace();
        } finally {
            lock.unlock();
        }
    }
}

下面是main方法

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class threeMethod {
    public static void main(String[] args) {
        final Foo foo = new Foo();
        new Thread(){// Thread 2
            public void run(){
                foo.second();
            }
        }.start();
        
        new Thread(){//Thread 3
            public void run(){
                foo.third();
            }
        }.start();
        
        new Thread(){//Thread 1
            public void run(){
                foo.first();
            }
        }.start();
   }
}

Concurrent - 生产者和消费者

经典的生产者消费者问题， 生产者每次添加1， 消费者减去1， 但当生产者添加到最大size时不能继续添加，同理消费者消耗到0时不能继续消耗。 为了简单这里用int变量代替storage。

[Thoughts]: BlockingQueue 接口里给出的方法， 这个实现应该是最简单的，但不晓得面试官会不会让用，最好问一下吧。
Note： BlockingQueue can safely be used with multiple producers and multiple consumers.

public class Setup {
    public static void main(String[] args) {
        BlockingQueue<Integer> q = new LinkedBlockingQueue<Integer>(3);
        new Thread(new producer(q)).start();
        new Thread(new consumer(q)).start();
        new Thread(new consumer(q)).start();
    }

}
//Producer Thread
class Producer implements Runnable{
    private final BlockingQueue queue;
    public Producer(BlockingQueue q){
        queue = q;
    }
    public void run(){
        try{
            while(true){
                queue.put(produce());
                System.out.println("Produced " + (i-1) +" Current size is "+ queue.size());
            }
        }catch(InterruptedException e){
            e.printStackTrace();
        }
    }
    private Object produce(){
        return new Object();
    }
}
//Consumer Thread
class Consumer implements Runnable{
    private final BlockingQueue queue;
    public Consumer(BlockingQueue q){
        queue = q;
    }
    public void run(){
        try{
            while(true){
                consume(queue.take());
            }
        }catch(InterruptedException e){
            e.printStackTrace();
        }
    }
    private void consume(Object x){
        
    }
}

Storage 类定义了充当cache的int 变量num 和最大容量MAX_SIZE。 和两个方法produce， consume。 produce被Producer调用，用于添加1， consume被consumer调用，用于减1.

public class Storage{
    private int num = 0;
    private final int MAX_SIZE = 10;
    public void produce(){
        synchronized (this){
            while (num >= MAX_SIZE){//已满， producer thread进入等待
                try{
                    this.wait();
                }catch (InterruptedException e){
                    e.printStackTrace();
                }
            }
            num++;
            this.notifyAll();
         }
    } 
    public void consume(){
        synchronized (this){
            while (num==0){//已空， consumer thread进入等待
                try{
                    this.wait();
                }catch (InterruptedException e){
                    e.printStackTrace();
                }
             }
            num--;
            this.notifyAll();
        }
    }
    public static void main(String[] args) {// Main 方法
        Storage obj = new Storage();
        Executor exec = Executors.newCachedThreadPool();
        for(int i=1; i<20; i++){//for testing
            exec.execute(new Producer(obj));
            exec.execute(new Consumer(obj));
        }
    }
}

class Producer extends Thread{// Producer 类
    private Storage storage;
    public Producer(Storage storage){
        this.storage = storage;
    }
    public void run(){
        storage.produce();
    }
}
    
class Consumer extends Thread{ // Consumer 类
    private Storage storage;
    public Consumer(Storage storage){
        this.storage = storage;
    }
    public void run(){
        storage.consume();
    }
}  

Thread Pool

Thread pool: a collection of threads, the size of which is bounded.
Java provides thread pools through the Executor framework.
[Thoughts]: The following class implements part of a simple HTTP server。 If you don't use parallel computing, it will have poor ferformance becasue process request might frequently blocks on I/O.
Executors: 

• provide a layer of indirection between a client and the execution of a task; instead of client executing a task directly, an intermediate object executes the task; 
• Allow you to manage the execution of asynchronous tasks without having to explicitly manage the lifecycle of threads. 

newFixedthreadPool：Saves time, because do not need to pay for thread creation overhead for every single task.
newCachedThreadPool: create as many threads as it needs during the execution of a program and then will stop creating new threads as it recycles the old ones.

class TaskExecutionWebServer throws IOException{
  private static final int nthreads = 100;// control the number of threads launched. 
  private static final int serverport = 8080;
  private static final Executor exec = executors.newFixedthreadPool(nthreads);

  public static void main(Strings[] arg){
    ServerSocket serversocket = new ServerSocket(serverport);
    while(true){
      final Socket connection = serversocket.accept();
      Runnable task = new Runnable(){
        public void run(){
        Worker.handleRequest(connection);
        }
      };
    exec.execute(task);
  }
 }
}

Concurrent - 两个线程依次输出

实现两个线程，一个线程打印1-52，另一个线程打印字母A-Z。

打印 顺序为12A34B56C……5152Z
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[Thoughts]：下面用了两种方法，两种方法的思路是一样的，只不过第二种用synchronized方法把wait 和 notify单独拿出来了。

public class OddEven { 
  public static void main(String[] args) {
    OddEven obj = new OddEven();
    oddThread thread1 = new oddThread(obj);
    evenThread thread2 = new evenThread(obj);
    thread1.start();
    thread2.start();
  }
}
class oddThread extends Thread{
  private OddEven monitor;
  public oddThread(OddEven monitor){
    this.monitor = monitor;
  }
  public void run(){
    synchronized(monitor){
      for(int i=1; i<=52; i+=2){
        System.out.print(i+""+(i+1));
        monitor.notify();
        try{
          monitor.wait();
        }catch(Exception e){
          System.out.println(e.getMessage());
        }
     }   
   } 
 }
}
class evenThread extends Thread{
  private OddEven monitor;
  public evenThread(OddEven monitor){
    this.monitor = monitor;
  }
  public void run(){
    synchronized(monitor){
      for(char i='A'; i<='Z'; i++){
        System.out.print(i);
        monitor.notify();
        try{
          if(i!='Z')//z是最后一个输出，不需要wait
          monitor.wait();
        }catch(Exception e){
          System.out.println(e.getMessage());
        }
      }
   } 
  }
}

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
[Thoughts]:

public class OddEven {
 private boolean turn = false;//实例变量 turn， false代表数字，true代表字母。
 public static void main(String[] args) {
  OddEven obj = new OddEven();
  oddThread thread1 = new oddThread(obj);
  evenThread thread2 = new evenThread(obj);
  thread1.start();
  thread2.start();
 }
 public synchronized void waitturn(boolean oldturn){
  while(turn != oldturn){
   try{
    wait();
   }catch(Exception e){
    System.out.println(e.getMessage());
   }
  }
 }
 public synchronized void toggleturn(){
  turn = !turn;
  notify();
 }
}
class oddThread extends Thread{
 private OddEven monitor;
 public oddThread(OddEven monitor){
  this.monitor = monitor;
 }
 public void run(){
  for(int i=1; i<=52; i+=2){
   monitor.waitturn(false);
   System.out.print(i+""+(i+1)); 
   monitor.toggleturn();
  }
 }
}
class evenThread extends Thread{
 private OddEven monitor;
 public evenThread(OddEven monitor){
  this.monitor = monitor;
 }
 public void run(){
  for(char i='A'; i<='Z'; i++){
   monitor.waitturn(true);
   System.out.print(i);
   monitor.toggleturn();
  }  
 }
}

如果不要求两个thread，下面的也work，不确定有没有隐含bug

public class Test2 {
 public int num = 1;
 public char cha = 'A';
 public static void main(String[] arg){
  final Test2 sol = new Test2();
  Thread thread = new Thread(){
   public void run(){
    sol.printn();
   }
  };
  thread.start();
  //此处需要加个thread.join()吗？
 }
 public synchronized void printn(){
  if(num<=52){
   System.out.print((num++)+""+(num++));
   printc();
  }
 }
 public synchronized void printc(){
  if(cha<='Z'){
   System.out.print(cha++);
   printn();
  }
 }
}

Java OO Conceptions

What is Composition  and Inheritance
Composition:  create objects of your existing class inside the new class.
Inheritance: create a new class as a type of an existing class.
Classes is allowed to inherit commonly used state and behavior from other classes.

What is Polymorphism（dynamic binding）
The ability of an object to take on many forms(You have the same interface from the base class, and different forms using that interface: the different versions of the dynamically bound methods. ).
Like override( when a parent class reference is used to refer to a child class object.).

Data Abstract

Abstract Method: a method that is incomplete; it has only a declaration and no method body;

abstract void f();

An abstract class 可以没有abstract method， 但是有abstract method的class一定是abstract class。
You can not make an object of an abstract class!!!

Abstract Class:

• The implementation is provided by inheritors. 
• Abstract class can have fields. 
• Can have complete default code / details to be overridden. 
• Can have access modifiers. 
• Is-a relationship

Interface:

• Support multiple inheritance. 
• Interface can also have fields, but these are implicitly static and final. 
• Completely abstract class, can not have code, just signature. 
• Can not have Access Modfiers, everything is assumed as public. 
• Has-a realtionship.

Encapsulation（data hiding）：

Encapsulation is the technique of making the fields in a class private and providing access to the fields via public methods.

Java 线程

Difference between process and threads

A process is an execution of a program but a thread is a single execution sequence within the process.

A process has its own memory space, and can contain multiple threads.  Thread share the resource belongs to the process.

Difference ways to create thread

1, implement the runnable interface, and need to create an Thread Object and pass the runnable instance.

public void example1 implements Runnable{

                  public void run(){

}

}

public static void main(String[] args){

                  example1 instance = new example1();

                  Thread thread = new Thread(instance);

                  thread.start();

}

2, extents the Thread class.

public void example2 extends Thread{

                  public void run(){

}

}

public static void main(String[] args){

                  example2 instance = new example2();

                  instance.start();

}

Extending Thread Class vs. Implementing the Runnable Interface
Implementing the Runnable Interface may be preferable:

1)  Java does support multiple inheritance, once you extends Thread class, the subclass can not extend any other class.

2) A class might only be interested in being runnable, and therefore, inheriting the full overhead of the Thread class would be excessive.

Thread yield, wait, sleep

wait: current thread to wait until another thread invokes the notify() method.

Yield: A suggestion to the thread scheduler that this would be a good time to switch to another task for a while. 

Sleep: block the execution of that task for a given time. Do not release the object lock. 

Deadlock
Threads within a given process share the same memory space.

Deadlock is situation that a thread is waiting for an object lock that another thread holds, and this second thread is waiting for another object lock that the first thread holds. So both of them remain waiting forever.

For conditions of deadlock

1,  Mutual Exclusion: Only one process can access a resource at a given time.

2, Hold and Wait: Thread already holding a resource can request additional resources.

3, No Preemption: One thread can’t remove others’ resources.

4, Circular Wait: Form a chain, each thread is waiting on another’s resource in the chain.

Thread States
1. New : allocates any necessary system resources and performs initialization. 

2. Runnable: The scheduler can arrange it. 

3. Blocked: The thread can be run, but something prevents it. The schedule will simply skip it and not give it any CPU time. 

• the task is put to sleep()
• the execution is suspended with wait()
• waiting for some I/O to complete
• trying to call synchronized method on an object, whose lock is not  available. 

4. Dead: return from run() or be interrupted.  Will not receive any CPU time.