<file_sep>/**
 * Given a class of Box, which has attribute color which specifies the color 
 * of the box, including red (0), white (1), black (2); Given an array of
 * box and sort the boxes by all red boxes first, then white, then black
 */
public class SortBox{
  private class Box{
    int color;
    public Box(int c){
      this.color = c;
    }
  }

  public void sort(Box[] boxes){
    if(boxes == null || 0 == boxes.length){
      return;
    }
    int[] count = new int[3];
    for(int i = 0; i < boxes.length; i++){
      count[boxes[i].color]++;
    }
    count[1] += count[0];
    count[2] += count[1];
    
    Box[] newBoxes = new Box[boxes.length];
    for(int i = 0; i < boxes.length; i++){
      newBoxes[count[boxes[i].color]--] = boxes[i];
    }
    boxes = newBoxes;
  }
}
<file_sep>import java.util.Arrays;

public class MaxHeap<T extends Comparable<T>> extends Heap<T>{
	@Override
	public void heapify(int i){
		int left = left(i);
		int right = right(i);
		if(left < heap.size() && get(left).compareTo(get(i)) > 0){
			swap(left, i);
			heapify(left);
		}else if(right < heap.size() && get(right).compareTo(get(i)) > 0){
			swap(right, i);
			heapify(right);
		}
	}

	@Override
	public void increaseKey(int i, T key){
	    while(i > 0 && key.compareTo(get(parent(i))) > 0){
            swap(i, parent(i));
            i = parent(i);
        }
	}

	public static void main(String[] args){
		MaxHeap<Integer> maxHeap = new MaxHeap<Integer>();
		maxHeap.push(3);
		maxHeap.push(5);
		maxHeap.push(6);
		maxHeap.push(2);
		maxHeap.push(8);
		maxHeap.push(7);
		maxHeap.push(4);
		maxHeap.push(3);

		int size = maxHeap.size();
		for(int i = 0; i < size; i++){
			System.out.println(maxHeap.get(i));
		}

        
		maxHeap.pop();
		size = maxHeap.size();

		for(int i = 0; i < size; i++){
			System.out.println(maxHeap.get(i));
		}
		
	}

}
<file_sep>import java.util.Set;
import java.util.HashSet;
import java.util.BinarySearchTree;

public class Duplicate{
  private class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int v){
      this.val = v;
    }
    
    boolean static addAndCheck(TreeNode root, TreeNode node, int range){
      if(node == null){
        return true;
      }
      if(root == null){
        root = node;
        return true;
      }
      int diff = Math.abs(node.val - this.val);
      if(diff < range){
        return false;
      }
      if(node.val < root.val){
        return addAndCheck(root.left, node, range);  
      }else{
        return addAndCheck(root.right, node, range);
      }
    }
  }
  public static boolean checkDuplicate(int[] input){
    Set set = new HashSet<Integer>();
    for(int one : input){
      if(set.contains(one)){
        return true;
      }else{
        set.add(one);
      }
    }
    return false;
  }

  public static boolean checkDuplicateWithKIndices(int[] input, int k){
    Set<Integer> set = new HashSet<Integer>();
    for(int i = 0; i < input.length; i++){
      if(i >= k){
        set.remove(input[i - k]);
      }
      if(set.contains(input[i])){
        return true;
      }else{
        set.add(input[i]);
      }
    }
    return false;
  }

  public static boolean checkDupWithKIndLRange(int[] input, int k, int l){
    Set<Integer> set = new HashSet<Integer>();
    TreeNode root;
    for(int i = 0; i < input.length; i++){
      if(root == null){
        root = new TreeNode(input[i]);
      }
    }

  }


}
<file_sep>package ctci.chapter14;

public class CircularArrayIterator<T> implements Iterator<T>{
  private CircularArray array;
  private int index;

  public CircularArrayIterator(CircularArray array){
    this.array = array;
    this.index = array.getHead();
  }

  @Override
  public boolean hasNext(){
    int indexBeforeHead = array.getHead() == 0 ? array.length - 1 : array.getHead() - 1;
    return index != indexBeforeHead;
  }

  @Override
  public T next(){
    if(hasNext){
      return array[index++];
    }else{
      return null;
    }
  }

  @Override
  public void remove(){
    throw new UnsupportedOperationException();
  }

}<file_sep>
import java.util.List;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
/**
 * Given an array and an integer k, find the maximum for each and 
 * every contiguous subarray of size k
 *
 */
public class MaximumOfK{
  static List<Integer> maximumOfK(int[] array, int k){
    List<Integer> ret = new ArrayList<Integer>();
    Comparator<Integer> comparator = new Comparator<Integer>(){
      public int compare(Integer i1, Integer i2){
        return i2 - i1;
      }
    };
    PriorityQueue<Integer> heap = new PriorityQueue<Integer>(k, comparator);
    for(int i = 0; i < array.length; i++){
      if(i < k){
        heap.offer(array[i]);
      }else{
        ret.add(heap.peek());
        heap.remove(array[i - k]);
        heap.offer(array[i]);
      }
    }
    ret.add(heap.peek());
    return ret;
  }

  //more efficient way use a double-ended queue
  static List<Integer> maximumDequeue(int[] array, int k){


  }


  public static void main(String[] args){
    int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
    List<Integer> ret1 = maximumOfK(a, 3);
    for(int i : ret1){
      System.out.print( i + " ");
    }
    System.out.println();
    
    int[] b = new int[]{9, 2, 3, 8, 5, 3, 7, 3, 9};
    ret1 = maximumOfK(b, 2);
    for(int i : ret1){
      System.out.print( i + " ");
    }
    System.out.println();
  }
}
<file_sep>package ctci.chapter09;

import java.util.Set;
import java.util.HashSet;

/*
* Implement an algorithm to print all valid(ie. properly opened and closed) 
* combinations of n-pairs of parentheses
*/
public class Parentheses{
  public Set<String> allParentheses(int num){
    Set<String> results = new HashSet<String>();
    if(num == 0){
      results.add("");
    }
    // remove the situation which could get from the following condition 
    /*else if(num == 1){
      results.add("()");
    }*/
    else{
      Set<String> former = allParentheses(num - 1);
      for(String single:former){
        for(int i = 0; i < single.length(); i++){
          if(single.charAt(i) == '('){
            results.add(parentheseFromIndex(single, i));
          }
        }
        results.add("()" + single);
      }
    }
    return results;
  }

  private String parentheseFromIndex(String str, int index){
    StringBuilder sb = new StringBuilder();
    sb.append(str.substring(0, index + 1));
    sb.append("()");
    sb.append(str.substring(index + 1));
    return sb.toString();
  }

  public static void main(String[] args){
    Parentheses pr = new Parentheses();
    Set<String> results = pr.allParentheses(2);
    for(String result:results){
      System.out.println(result);
    }
  }
}<file_sep>import java.io.*;
/*Babai is standing in the top left cell (1,1) of an N*M table. The table has N rows and M columns. Initially he is facing its right cell. He moves in the table in the following manner:

He moves one step forward
He turns to its right
If moving forward makes him exit the boundaries of the table, or causes him to reach a visited cell, he turns to its right.
He moves around the table and visits as many cells as he can. Your task is to find out the number of cells that he visits before he stops.

Here's a sample of Babai's steps on a 9x9 grid. The value at each cell denotes the step number.

1  2 55 54 51 50 47 46 45 
4  3 56 53 52 49 48 43 44 
5  6 57 58 79 78 77 42 41 
8  7 60 59 80 75 76 39 40 
9 10 61 62 81 74 73 38 37 
12 11 64 63 68 69 72 35 36 
13 14 65 66 67 70 71 34 33 
16 15 20 21 24 25 28 29 32 
17 18 19 22 23 26 27 30 31 
 
Input:
The input contains two integers N and M separated by a line. N and M are between 1 and 100.

Output:
Print a single integer which is the answer to the test-case

Sample input #00:
3
3

Sample output #00:
9

Sample input #01:
7
4

Sample output #01:
18
*/
public class SquareVisitedCells{
  public static int steps(int n, int m){
    if(m == 0 || n == 0){
      return 0;
    }
    if(m == 1 && n == 1){
      return 1;
    }

    if(n % 2 == 1){
      return 2 * n + steps(m - 2, n);
    }else{
      return 2 * n;
    }
  }
  public static void main(String args[] ) throws Exception {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int m = Integer.parseInt(br.readLine());
    System.out.println(steps(n, m));

  }

}<file_sep>/**
 * Suppose that you have a dictionary of words and a collection of letters
 * Find all of the longest words in the dictionary that you can form using letters in your collection:
 */

public class LongestWordInDic{


}
<file_sep>import java.util.Arrays;

public class BubbleSort{
  private static int[] array;

  public static void bubbleSort(){
    int len = array.length;
    for(int i = len - 1; i >= 0; i--){
      for(int j = 0; j < i; j++){
        if(array[j] > array[j + 1]){
          swap(j, j + 1);
        }
      }
    }
  }
  
  public static void swap(int i, int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

  public static void main(String[] args){
    array = new int[]{2,4,7,3,1,7,4,5,0,6};
    bubbleSort();
    System.out.println(Arrays.toString(array));
  }
}
<file_sep>/**
 * Triangle
 * By starting at the top of the triangle and moving to adjacent numbers on the row below,
 * the maximum total from top to bottom is 27
 *       5
 *     9  6
 *   4   6  8
 * 0   7  1   5                     
 * resutl 5 + 9 + 6 + 7 = 27
 * Write a program in a language of your choice to find the maximum total from top to bottom
 *
 */


import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;
import java.util.Arrays;

public class Triangle{
  private static int line = 100;
  private static int[][] triangle = new int[line][line];
  private static int[][] result = new int[line][line];
  private static void readFile(){
    BufferedReader br = null;
    String line;
    Scanner sc = null;
    try{
      br = new BufferedReader(new FileReader("triangle.txt"));
      int lineNo = 0;
      while((line = br.readLine()) != null){
        sc = new Scanner(line);
        int index = 0;
        while(sc.hasNextInt()){
          triangle[lineNo][index++] = sc.nextInt();
        }
        lineNo++;
      }
    }catch(IOException e){
      e.printStackTrace();
    }finally{
      try{
        if(br != null){
          br.close();
        }
      }catch(IOException ex){
        ex.printStackTrace();
      }
    }
  }
  
  private static int maxSum(){
    result[0][0] = triangle[0][0];
    int max = Integer.MIN_VALUE;
    for(int i = 1; i < line; i++){
      result[i][0] = result[i - 1][0] + triangle[i][0];
      for(int j = 1; j <= i; j++){
        result[i][j] = Math.max(result[i - 1][j - 1], result[i - 1][j]) + triangle[i][j];
        if(i == line - 1){
          max = Math.max(max, result[i][j]);
        }
      }
    }
    return max;
  }

  public static void main(String[] args){
    readFile();
    //System.out.println(Arrays.deepToString(triangle));
    System.out.println("___________________");
    int max = maxSum();
    System.out.println(max);
  }
}
<file_sep>#include<stdio.h>

class Wrapper{
  public:
    Wrapper(int i = 0){
      dig = i;
    }
    int & getDig(){
      return dig;
    }
  private:
    int dig;
};

void mul(int & a ){
  a = 2 * a;
}

int main(){
  Wrapper w(1);
  mul(w.getDig());
  printf("%d\n", w.getDig());
  return 0;
}
<file_sep>
import java.util.Random;

public class ShortestPath{
  boolean[][] matrix;
  Random random;
  public ShortestPath(int len, int wid){
    this.matrix = new boolean[len][wid];
    this.random = new Random();
  }

  public void generateMatrix(){
    for(int i = 0; i < matrix.length; i++){
      for(int j = 0; j < matrix[0].length; j++){
        int rand = random.nextInt(5);
        if(rand > 0){
          matrix[i][j] = true;
        }else{
          matrix[i][j] = false;
        }
      }
    }
  }

  /**
   * This solution suppose can only move left or down
   */ 
  public int shortestPath(int x, int y){
    if(x >= matrix[0].length || x >= matrix.length){
      throw new IllegalArgumentException();
    }

    int[][] dp = new int[y][x];
    for(int i = 0; i < y; i++){
      for(int j = 0; j < x; j++){
        if(!matrix[i][j]){
          dp[i][j] = 0;
          continue;
        }
        if(i == 0 && j == 0){
          dp[i][j] = 0;
        }else if(i == 0){
          dp[i][j] = matrix[i][j - 1] ? dp[i][j - 1] + 1 : 0;
        }else if(j == 0){
          dp[i][j] = matrix[i - 1][j] ? dp[i - 1][j] + 1 : 0;
        }else{
          int temp = Integer.MAX_VALUE;
          if(matrix[i - 1][j]){
            temp = Math.min(temp, dp[i - 1][j]);
          }
          if(matrix[i][j - 1]){
            temp = Math.min(temp, dp[i][j - 1]);
          }
          if(temp == 0){
            dp[i][j] = 0;
          }else{
            dp[i][j] = temp + 1;
          }
        }
      }
    }
    return dp[y - 1][x - 1];
  }

  public static void main(String[] args){
    ShortestPath sp = new ShortestPath(5, 6);
    sp.generateMatrix();
    for(int i = 0; i < 5; i++){
      for(int j = 0; j < 6; j++){
        System.out.print(sp.matrix[i][j] +  " ");
      }
      System.out.println();
    }

    System.out.println("Path to 3, 3 = " + sp.shortestPath(3, 3));
  }
}
<file_sep>import java.util.ArrayList;
import java.util.List;

public abstract class Heap<T extends Comparable<? super T>>{
	protected List<T> heap;
	public Heap(){
		heap = new ArrayList<T>();
	}

	public void push(T item){
		heap.add(item);
		increaseKey(heap.size() - 1, item);
	}

	public T pop(){
		T top = getFirst();
		swap(0, heap.size() - 1);
		heap.remove(heap.size() - 1);
		heapify(0);
		return top;
	}

	public T getFirst(){
		return heap.get(0);
	}

	public T get(int index){
		return heap.get(index);
	}

	public int size(){
		return heap.size();
	}

	protected int parent(int i){
		if(i == 0){
			throw new IllegalArgumentException("can not find the parent of the root");
		}
		return (i - 1) / 2;
	}

	protected int left(int i){
		return 2 * i + 1;
	}

	protected int right(int i){
		return 2 * i + 2;
	}

	protected void swap(int i, int j){
		T itemAtI = heap.get(i);
		heap.set(i, heap.get(j));
		heap.set(j, itemAtI);
	}

	public void buildHeap(){
		int size = heap.size();
		int middle = size / 2 - 1;

		for(int i = middle; i >= 0; i--){
			heapify(i);
		}

	}

	public abstract void heapify(int i);

	public abstract void increaseKey(int i, T key);

}
<file_sep>
import java.util.Queue;
import java.util.LinkedList;
/**
 * 数据结构设计题，给你一个黑匣子，匣子里面有很多sorted的数，支持get()和next()函数，类似于pop()跟peek()的区别，
 * 都是取得最小数，不过一个删数一个不删数，叫你设计一个数据结构，除了这两个函数之外还要支持add(int)这个函数，你不能对黑匣子进行修改
 */ 
public class BoxImpl implements Box{

  private Box box;
  private int temp;
  private boolean isTempNull;
  public BoxImpl(Box box){
    this.box = box;
    this.temp = 0;
    this.isTempNull = true;
  }

  @Override
  public int get(){
    if(isTempNull){
      return box.get();
    }else{
      int curr = box.get();
      if(curr > temp){
        return temp;
      }else{
        return curr;
      }
    }
  }

  @Override
  public int next(){
    if(isTempNull){
      return box.next();
    }else{
      int curr = box.get();
      if(curr > temp){
        int ret = temp;
        temp = 0;
        isTempNull = true;
        return ret;
      }else{
        return box.next();
      }
    }
  }

  void add(int x){
    if(isTempNull){
      isTempNull = false;
      temp = box.next() + temp + x;
    }else{
      temp += x;
    }
  }

  public static void main(String[] args){
    final Queue<Integer> queue = new LinkedList<Integer>();
    queue.add(1);
    queue.add(2);
    queue.add(3);
    queue.add(4);
    queue.add(5);
    queue.add(7);
    Box box = new Box(){
      public int get(){
        return queue.peek();
      }
      public int next(){
        return queue.poll();
      }
    };
    BoxImpl addBox = new BoxImpl(box);
    System.out.println(addBox.get());
    System.out.println(addBox.next());
    addBox.add(4);
    System.out.println(addBox.next());
    System.out.println(addBox.next());
    System.out.println(addBox.next());
    System.out.println(addBox.next());
    System.out.println(addBox.next());
  }
}<file_sep>import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;

public class SquareGoodNode {

  public static void main(String[] args) throws Exception{
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Node> nodeList = new ArrayList<Node>();
        int totalNumber = Integer.parseInt(br.readLine());
        for(int i=0; i<totalNumber; i++){
          nodeList.add(new Node());
        }
        for(int i=0; i<totalNumber; i++){
          nodeList.get(i).next = nodeList.get(Integer.parseInt(br.readLine())-1);
        }
      System.out.println(minChangeToGood(nodeList));
  }
  public static int minChangeToGood(ArrayList<Node> list){
    HashSet<Node> set = new HashSet<Node>();
    Node node1 = list.get(0);
    int count = 0;
    for(int i=0; i<list.size(); i++){
      Node node = list.get(i);
      if(set.contains(node)){
        continue;
      }else{
        HashSet<Node> subset = new HashSet<Node>();
        while(!subset.contains(node)){
          subset.add(node);
          node = node.next;
        }
        if(!subset.contains(node1)) count++;
        set.addAll(subset);
      }
    }
    return count;
  }
}
<file_sep>public class List<T>{
  public  ListNode<T> reverseRecursive(ListNode<T> node){
    if(node == null){
      return null;
    }
    if(node.next == null){
      return node;
    }
    ListNode<T> second = node.next;
    node.next = null;
    ListNode<T> after = reverseRecursive(second);
    second.next = node;
    return after;
  }

  public ListNode<T> reverseIterative(ListNode<T> node){
    if(node == null){
      return null;
    }
    ListNode<T> prev = null;
    ListNode<T> curr = node;
    ListNode<T> next = null;
    while(curr != null){
      next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }
    return prev;
  }

  private void print(ListNode<T> node){
    ListNode<T> tmp = node;
    while(tmp != null){
      System.out.println(tmp.value);
      tmp = tmp.next;
    }
  }

  public static void main(String[] args){
    ListNode<Integer> node = new ListNode<Integer>(1);
    node.next = new ListNode<Integer>(2);
    node.next.next = new ListNode<Integer>(3);
    List<Integer> list = new List<Integer>();
    ListNode<Integer> after = list.reverseRecursive(node);

    list.print(after); 

    ListNode<Integer> another = list.reverseIterative(after);
    list.print(another);
  }
  
}
<file_sep>package edu.nyu.zhaohui.amazon;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Windows {
  public static List<Integer> calculateWindowsSums(List<Integer> list, int windowSize){
    if(null == list){
      throw new IllegalArgumentException("list should not be null");
    }
    List<Integer> ret = new ArrayList<Integer>();
    if(list.size() == 0 || windowSize <= 0){
      return ret;
    }
    int total = 0;
    for(int i = 0; i < list.size(); i++){
      if(i < windowSize){
        total += list.get(i);
      }else{
        ret.add(total);
        total -= list.get(i - windowSize);
        total += list.get(i);
      }
    }
    ret.add(total);
    return ret;
  }
  
  public static void main(String[] args){
    Integer[] one = new Integer[]{4, 2, 73, 11, -5};
    List<Integer> input = new ArrayList<Integer>(Arrays.asList(one));
    List<Integer> ret = calculateWindowsSums(input, 2);
    List<Integer> ret2 = calculateWindowsSums(input, 3);
    for(Integer i : ret){
      System.out.print(i + " ");
    }
    for(Integer i : ret2){
      System.out.print(i + " ");
    }
  }
}
<file_sep>

public class WiredOrderPrint{
  public static void print(int[] array){
    int len = array.length;
    boolean smallThanLater = true;
    for(int i = 1; i < len; i++){
      if(smallThanLater){
        if(array[i - 1] > array[i]){
          change(array, i - 1, i);
        }
      }else{
        if(array[i - 1] < array[i]){
          change(array, i - 1, i);
        }
      }
      smallThanLater = smallThanLater ? false : true;
    }
    for(int i = 0; i < len; i++){
      System.out.print(array[i] + " ");
    }
    System.out.println();
  }
  private static void change(int[] array, int x, int y){
    int temp = array[x];
    array[x] = array[y];
    array[y] = temp;
  }
  public static void main(String[] args){
    int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
    print(a);

    int[] b = new int[]{9, 8, 7, 6, 5, 4, 3, 2, 1};
    print(b);

    int[] c = new int[]{5, 2, 8, 4, 6, 2, 9, 3, 5};
    print(c);

    int[] d = new int[]{ 3, 6, 3, 1, 9, 6, 8, 2, 5, 6, 4, 2, 1};
    print(d);
  }
}
<file_sep>package edu.nyu.zhaohui.amazon;

import java.util.HashMap;
import java.util.Map;

public class MostFrequentNumber {
  public static int mostFrequent(int[] array){
    if(null == array || 0 == array.length){
      throw new IllegalArgumentException();
    }
    int ret = 0;
    int freq = Integer.MIN_VALUE;
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for(int num : array){
      if(!map.containsKey(num)){
        map.put(num, 1);
      }else{
        int oldFreq = map.get(num);
        map.put(num, oldFreq + 1);
        if(oldFreq + 1 > freq){
          freq = oldFreq + 1;
          ret = num;
        }
      }
    }
    return ret;
  }
  
  public static void main(String[] args){
    int[] array = new int[]{1, 3, -4, 0, 9, 0, -4, 3, -4, 10000, -398};
    System.out.println(mostFrequent(array));
  }
}
<file_sep>package ctci.chapter08.4thedition;

/**
* Write a method to generate the nth Fibonacci number
* Both Recursive and Iterative way used
*/

public class Fibonacci{

  // Recursive
  public static int fibonacciRecursive(int n){
    if(n < 0){
      throw new IllegalArgumentException("Argument cannot be negative: " + n);
    }
    if(n == 0){
      return 0;
    }
    if(n == 1){
      return 1;
    }
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
  } 

  // First Attempt: This method has a bug, will outOfIndex if n = 0;
  public static int fibonacciIterative_old(int n){
    int[] result = new int[n];
    for(int i = 0; i < n; i++){
      if(i == 0 || i == 1){
        result[i] = 1;
      }else{
        result[i] = result[i - 1] + result[i - 2];
      }
    }
    return result[n - 1];
  }

  // THis method is not an effient, since 
  //we do not need to use array to save all the data
  public static int fibonacciIterative_again(int n){
    if(n < 0){
      throw new IllegalArgumentException("Argument cannot be negative: " + n);
    }

    if(n == 0){
      return 0;
    }
    int[] resultSet = new int[n];
    for(int i = 0; i < n; i++){
      if(i == 0 || i == 1){
        resultSet[i] = 1;
      }else{
        resultSet[i] = resultSet[i - 1] + resultSet[i - 2];
      }
    }
    return resultSet[n - 1];
  }

  // Iterative
  public static int fibonacciIterative(int n){
    if(n < 0){
      throw new IllegalArgumentException("Argument cannot be negative: " + n);
    }

    if(n == 0){
      return 0;
    }
    
    int a = 1, b = 1;
    int c = 0;
    for(int i = 3; i <=n; i++){
      c = a + b;
      a = b;
      b = c;
    }
    return b;

  }

  public static void main(String[] args){
    System.out.println(fibonacciRecursive(0));
    //System.out.println(fibonacciIterative_old(0));
    System.out.println(fibonacciIterative_again(0));
    System.out.println(fibonacciIterative(0));
  }
}<file_sep>package edu.nyu.zhaohui.amazon;

public class NotifyCustomers {
  public static ListNode<Integer> notify(ListNode<Integer> head, int k){
    ListNode<Integer> fast = head;
    while(k > 0){
      fast = fast.next;
      k--;
    }
    ListNode<Integer> slow = head;
    while(fast != null){
      fast = fast.next;
      slow = slow.next;
    }
    return slow;
  }
  
  public static void main(String[] args){
    ListNode<Integer> node1 = new ListNode<Integer>(1);
    ListNode<Integer> node2 = new ListNode<Integer>(8);
    ListNode<Integer> node3 = new ListNode<Integer>(4);
    ListNode<Integer> node4 = new ListNode<Integer>(2);
    ListNode<Integer> node5 = new ListNode<Integer>(7);
    ListNode<Integer> node6 = new ListNode<Integer>(13);
    ListNode<Integer> node7 = new ListNode<Integer>(3);
    node1.next = node2;
    node2.next = node3;
    node3.next = node4;
    node4.next = node5;
    node5.next = node6;
    node6.next = node7;
    System.out.println(notify(node1, 2).val);
  }
}
<file_sep>package edu.nyu.zhaohui.amazon;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Intersection {
  public List<Integer> intersec(List<Integer> list1, List<Integer> list2){
    if(list1 == null || list2 == null){
      return null;
    }
    List<Integer> ret = new ArrayList<Integer>();
    if(list1.size() == 0 || list2.size() == 0){
      return ret;
    }
    
    Map<Integer, Boolean> map = new HashMap<Integer, Boolean>();
    for(int i : list1){
      map.put(i, false);
    }
    for(int j : list2){
      if(map.containsKey(j)){
        map.put(j, true);
      }
    }
    for(int one : map.keySet()){
      if(map.get(one)){
        ret.add(one);
      }
    }
    return ret;
  }
  
  public static void main(String[] args){
    Integer[] array1 = new Integer[]{4, 2, 73, 11, 9};
    Integer[] array2 = new Integer[]{-5, 73, -1, 9, 9, 4, 7};
    Intersection intersection = new Intersection();
    List<Integer> ret = intersection.intersec(Arrays.asList(array1), Arrays.asList(array2));
    System.out.println(ret.toString());
  }
}
<file_sep>package com.ask.interview.second;

/**
 * This class can be used to build of a graph
 * and perform some basic operations on it.
 * 
 * The graph is constructed by calling the 
 * addEdge or addEdges methods. The Strings
 * to define an edge will contain 2 characters,
 * each character being the label for the 
 * node. After these 2 characters, there will
 * be an integer value that represents the
 * distance or length on the edge between
 * the nodes. The edges are directional. In
 * other words "AB" implies that you can
 * traverse from A to B but not from B to A.
 * You would have to have anther edge added
 * "BA" in order to go the other direction.
 * 
 * There are several methods available to 
 * get details about the graph.
 * 
 */
public class Graph {
	
	/**
	 * The format of the string is
	 *  1st Character = starting node name
	 *  2nd Character = ending node name
	 *  Integer = edge length
	 *  
	 * For example, the String "AB5" should
	 * create 2 nodes, each labeled "A" and
	 * "B" respectively with a distance between
	 * them of 5 units.
	 */
	public void addEdge(String edge) {
		throw new RuntimeException("Implement Me!!!");
	}
	
	/**
	 * Just like addEdge() but it does
	 * more than one at a time.
	 */
	public void addEdges(String... edges) {
		throw new RuntimeException("Implement Me!!!");
	}

	/**
	 * Each character in the String represents an edge
	 * traversal over which the sum of the edge lengths
	 * is to be accumulated.
	 * 
	 * The route is defined by providing a sequence of
	 * characters that represent the nodes of the path.
	 * 
	 * For example, if a graph had been created as
	 * "AB5", "BC2" then the return value for various
	 * paths would be:
	 * 
	 * "AB" --> 5
	 * "BC" --> 2
	 * "ABC" --> 7
	 * "ABCB" --> 9
	 */
	public int calculateRouteDistance(String routeToTake) {
		throw new RuntimeException("Implement Me!!!");
	}
	
	/**
	 * The format of the fromTo input string is 
	 *  1st Character = starting node name
	 *  2nd Character = ending node name
	 *  
	 * Any single shortest path from the starting node
	 * name to the ending node dame. If the graph had
	 * been created as "AB5", "BC2", "AD2", "DC5", and
	 * this method was called with "AC" then both paths
	 * "ABC7" and "ADC7" are of length 7 and either
	 * would be a valid return value.
	 * 
	 * The return value should be the node names followed
	 * by the length of the path.
	 */
	public String calculateShortestRoute(String fromTo) {
		throw new RuntimeException("Implement Me!!!");
	};

	/**
	 * The format of the string is 
	 *  1st Character = starting node name
	 *  2nd Character = ending node name
	 *  
	 *  As each edge is traversed, the length of the edge
	 *  should be accumulated to create a total distance 
	 *  for that route.
	 *  
	 *  All unique paths that go from the starting node to the
	 *  ending node which are shorter than the maximumDistance
	 *  should be counted.
	 *  
	 *  For example, if the graph is constructed as "AB5", "BC2",
	 *  "CD3", "BD6", "AC1", "AD9", then some valid paths for "AD"
	 *  are "ABCD10", "ABD11", "ACD4", "AD9".
	 *  
	 *  If the maximumDistance is set above 11, all 4 should be
	 *  returned. If set below 4, then nothing should be returned.
	 *  If set to 4, then "ACD4" should be returned, and so on.
	 */
	public String[] getPaths(String fromTo, int maximumDistance) {
		throw new RuntimeException("Implement Me!!!");
	}
	
}
<file_sep>

public class Shouda{



}

<file_sep>package edu.nyu.zhaohui.amazon;

public class FindLoop<T> {
  
  public boolean hasLoop(ListNode<T> head){
    if(head == null){
      return false;
    }
    ListNode<T> fast = head;
    ListNode<T> slow = head;
    
    while(fast != null && fast.next == null){
      slow = slow.next;
      fast = fast.next.next;
      if(slow == fast){
        return true;
      }
    }
    return false;
  }
}
<file_sep>package edu.nyu.zhaohui.amazon;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class KClosest {
  private final static int K = 5;
  public List<Point> findKClosest(List<Point> points){
    PriorityQueue<Point> heap = new PriorityQueue<Point>();
    for(Point point : points){
      if(heap.size() < K){
        heap.add(point);
      }else{
        if(heap.peek().compareTo(point) < 0){
          heap.poll();
          heap.offer(point);
        }
      }
    }
    return new ArrayList<Point>(heap);
  }
}
<file_sep>

/**
 * Given a set of numbers, find the length of the longest arithmetic progression(LAP) in it
 * 1) all the numbers in LAP should be continuous
 * Example:
 *    {1, 2, 3, 5, 4}
 *    output = 3
 *    The lap is {1, 2, 3}
 *   
 * 2) what if we do not care about the position
 * Example:
 *    {1, 7, 10, 15, 27, 29}
 *    output = 3
 *    The longest arithmetic progression is {1, 15, 29}
 *
 */
public class LongestArithmeticProgression{
  public static int getLengthLAPContinues(int[] array){
    int len = array.length;
    if(null == array || 0 == len){
      return 0;
    }
    if(1 == len){
      return 1;
    }
    int ret = 2;
    int maxSofar = 2;
    int diff = 0;
    for(int i = 1; i < len; i++){
      int currDiff = array[i] - array[i - 1];
      if(currDiff == diff){
        maxSofar++;
      }else{
        ret = Math.max(ret, maxSofar);
        diff = currDiff;
        maxSofar = 2;
      }
    }
    ret = Math.max(ret, maxSofar);
    return ret;
  }

  public static int getLengthLAP(int[] array){
  
  }

  public static void main(String[] args){
    int[] array = new int[]{1, 2, 4, 6, 7, 8, 10};
    System.out.println(getLengthLAPContinues(array));

  }
}

<file_sep>

/**
 *
 * 给一个text file， 里面是按行分割的各种单词，让找到频率第k大的那个单词。尽可能的优化
 */
public class TextWordCount{

}
<file_sep>public interface Box{
    int get();
    int next();
  }<file_sep>code interview
=============

Prepare for the code interview, including my solutions to crack the code interview and Leetcode
<file_sep>import java.util.Arrays;

public class InsertSort{
  private static int[] array;
  public static void insertSort(){
    for(int i = 1; i < array.length; i++){
      for(int j = 0; j < i; j++){
        if(array[j] > array[i]){
          int temp = array[i];
          for(int k = i; k > j; k--){
            array[k] = array[k - 1];
          }
          array[j] = temp;
          break;
        }
      }
    }
  }

  public static void insertSortSwap(){
    for(int i = 1; i < array.length; i++){
      for(int j = i; j > 0; j--){
        if(array[j] < array[j - 1]){
          swap(j, j - 1);
        }else{
          break;
        }
      }
    }
  }

  public static void swap(int i, int j){
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }

  public static void main(String[] args){
    array = new int[]{2,4,7,3,1,7,4,5,0,6};
    insertSortSwap();
    System.out.println(Arrays.toString(array));
  }

}
<file_sep>package ctci.chapter09;

import java.util.ArrayList;
import java.util.Arrays;

/**
* Write an algorithm to print all ways of arranging eight queens 
* on a 8, * chess board
*/
public class EightQueens{
  private static final int GRID_SIZE = 8;
  
  public static void placeQueens(int row, Integer[] colums, ArrayList<Integer[]> results){
    if(row == GRID_SIZE){
      results.add(colums.clone());
    }else{
      for(int colum = 0; colum < GRID_SIZE; colum++){
        if(isValid(colum, row, colums)){
          colums[row] = colum;
          placeQueens(row + 1, colums, results);
        }
      }
    }
  }

  public static boolean isValid(int colum, int row, Integer[] colums){
    for(int i = 0; i < row; i++){
      if(colums[i] == colum){
        return false;
      }
      int columDiff = Math.abs(colums[i] - colum);
      int rowDiff = Math.abs(i - row);
      if(columDiff == rowDiff){
        return false;
      }
    }
    return true;
  }
  public static ArrayList<Integer[]> getEightQueensPosition(){
    ArrayList<Integer[]> results = new ArrayList<Integer[]>();
    Integer[] test = new Integer[GRID_SIZE];
    System.out.println("TEST" + test[0]);
    placeQueens(0, test, results);
    return results;
  }
  public static void main(String[] args){
    ArrayList<Integer[]> results = getEightQueensPosition();
    int count = 0;
    for(Integer[] result:results){
      System.out.println(Arrays.toString(result));
      count++;
    }
    System.out.println(count);
    
  }
}<file_sep>import java.io.FileReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.util.HashMap;

/**
* This class simulates the process of Cosine Similarity Score of two queries
* Input file as parameters of the class, please run this program use:
* java CosineSimilarityScore file1 file2
* I assume the cosine similarity score calculated like the following:
* If there is multiple scores under one ID, just add them together;
* If there is ID1 in query1 but not in query2, use value 0 instead;
* Then calculate the score using Euclidean dot product formula listed in Wikipedia
*/
public class CosineSimilarityScore{
  private static class Query{
    public String name;
    public HashMap<String, Integer> scores;
    public Query(String n, HashMap<String, Integer> s){
      name = n;
      scores = s;
    }
  }
  
  private static Query query1;
  private static Query query2;

  private static String readFile(String inputName) throws IOException {
    BufferedReader br = null;
    StringBuilder sb = new StringBuilder();
    try {
      String line;
      br = new BufferedReader(new FileReader(inputName));
      while((line = br.readLine()) != null){
        sb.append(line);
      }
    } catch (IOException ioe) {
      ioe.printStackTrace();
    } finally {
      if (br != null) {
        br.close();
      }
    }
    return sb.toString();
  }

  private static Query parseString(String str){
    String[] temp = str.split("\\t");
    String name = temp[0];
    String other = temp[1];
    String[] values = other.split(",");
    int num = Integer.parseInt(values[0]);
    HashMap<String, Integer> scores = new HashMap<String, Integer>();
    for(int i = 0; i < num; i++){
      String key = values[2 * i + 1];
      int score = Integer.parseInt(values[2 * i + 2]);
      if(scores.containsKey(key)){
        scores.put(key, scores.get(key) + score);
      }else{
        scores.put(key, score);
      }
    }
    return new Query(name, scores);
  }

  private static double calCosine(){
    int dotMul = 0;
    int a = 0;
    int b = 0;
    for(String k : query1.scores.keySet()){
      if(query2.scores.containsKey(k)){
        dotMul += query1.scores.get(k) * query2.scores.get(k);
        a += query1.scores.get(k) * query1.scores.get(k);
        b += query2.scores.get(k) * query2.scores.get(k);
        query2.scores.remove(k);
      }else{
        a += query1.scores.get(k) * query1.scores.get(k);
      }
      
    }
    for(String k: query2.scores.keySet()){
      b += query2.scores.get(k) * query2.scores.get(k);
    }
    double ret = (double)dotMul / (Math.sqrt(a) * Math.sqrt(b));
    // System.out.println(ret);
    return ret;
  }

  public static void main(String[] args) throws IOException{
    String str1 = readFile(args[0]);
    String str2 = readFile(args[1]);
    query1 = parseString(str1);
    query2 = parseString(str2);
    double cosine = calCosine();
    System.out.println(query1.name + "\t" + query2.name + "\t" + cosine);
  }

}<file_sep>#include<stdio.h>

char * strcpy(char * dst, const char * src){
  char * ptr;
  ptr = dst;
  while((*ptr++ = *src++) != '\0')
    ;
  return dst;
}

char * strcpy2(char dst[], const char source[]){
  int i = 0;
  while(source[i] != '\0'){
    dst[i] = source[i];
    i++;
  }
  dst[i] = '\0';
  return dst;
}

int main(){
  char str[] = "october";
  char dst[40];
  char dst2[40];
  strcpy(dst, str);
  strcpy2(dst2, str);
  printf("dst: %s dst2: %s\n", dst, dst2);
  return 0;
}
<file_sep>package ctci.chapter09;

import java.util.ArrayList;

/**
* Write a method to return all subsets of a set
*/
public class SubSet{

  // Recursion method
  public ArrayList<ArrayList<Integer>> getAllSubSetsRecursion(ArrayList<Integer> set){
    int size = set.size();
    return getAllSubSetsRecursion(set, size - 1);
  }

  public ArrayList<ArrayList<Integer>> getAllSubSetsRecursion(ArrayList<Integer> set, int index){
    
    ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
    if(index <= 0){
      results.add(new ArrayList<Integer>());
    }else{
      ArrayList<ArrayList<Integer>> tmp = getAllSubSetsRecursion(set, index - 1);
      results.addAll(tmp);
      for(ArrayList<Integer> curr:tmp){
        ArrayList<Integer> cache = curr;
        cache.add(set.get(index));
        results.add(cache);
      }
    }
    return results;

  }


  // Combinatorics Method
  public ArrayList<ArrayList<Integer>> getAllSubSets(ArrayList<Integer> set){
    int num = set.size();
    int compator = 1 << num;

    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>> ();
    for(int i = 0; i < compator; i++){
      ArrayList<Integer> current = getSubSetFromCompator(set, i, num);
      result.add(current);
    }
    return result;
  }

  public ArrayList<Integer> getSubSetFromCompator(ArrayList<Integer> set, int compator, int num){
    ArrayList<Integer> result = new ArrayList<Integer>();
    for(int i = 0; i < num; i++){
      if((compator & (1<<i)) != 0){
        result.add(set.get(i));
      }
    }
    return result;
  }

  public static void main(String[] args){
    ArrayList<Integer> test = new ArrayList<Integer>();
    test.add(1);
    test.add(2);
    test.add(3);
    SubSet ss = new SubSet();
    ArrayList<ArrayList<Integer>> results = ss.getAllSubSetsRecursion(test);
    for(ArrayList<Integer> result:results){
      for(int i = 0; i < result.size(); i++){
        System.out.print(result.get(i));
      }
      System.out.println();
    }
  }
}<file_sep>package edu.nyu.zhaohui.amazon;

import java.util.Arrays;

public class AdjancentValue {
  private class Combination implements Comparable<Combination>{
    public int index;
    public int value;
    public Combination(int ind, int val){
      this.index = ind;
      this.value = val;
    }
    
    @Override
    public int compareTo(Combination another) {
      return this.value - another.value;
    }
  }
  
  public int minumDistance(int[] array){
    int len = array.length;
    Combination[] comb = new Combination[len];
    for(int i = 0; i < len; i++){
      comb[i] = new Combination(i, array[i]);
    }
    Arrays.sort(comb);
    int ret = Integer.MAX_VALUE;
    int last = comb[0].index;
    boolean firstDifferent = false;
    for(int i = 1; i < len; i++){
      if(comb[i].value != comb[i - 1].value){
        ret = Math.min(ret, Math.abs(comb[i].index - comb[i - 1].index));
        last = comb[i].index - 1;
        firstDifferent = true;
      }else if(firstDifferent){
        ret = Math.min(ret, Math.abs(comb[i].index - last));
      }
    }
    last = comb[len - 1].index;
    firstDifferent = false;
    for(int i = len - 1; i > 0; i--){
      if(comb[i].value != comb[i - 1].value){
        ret = Math.min(ret, Math.abs(comb[i].index - comb[i - 1].index));
        last = comb[i].index;
        firstDifferent = true;
      }else if(firstDifferent){
        ret = Math.min(ret, Math.abs(comb[i].index - last));
      }
    }
    return ret;
  }
  
  public static void main(String[] args){
    int[] a = {0, 3, 3, 7, 5, 3, 11,1};
    int[] b = {1, 4, 7, 3, 3, 5, 6};
    AdjancentValue av = new AdjancentValue();
    System.out.println(av.minumDistance(a));
    System.out.println(av.minumDistance(b));
  }
}
<file_sep>package edu.nyu.zhaohui.amazon;

public class StudentResult {
  int studentId;
  String data;
  int testScore;
  
  public StudentResult(int id, String data, int score){
    this.studentId = id;
    this.data = data;
    this.testScore = score;
  }

  public int getStudentId() {
    return studentId;
  }

  public void setStudentId(int studentId) {
    this.studentId = studentId;
  }

  public String getData() {
    return data;
  }

  public void setData(String data) {
    this.data = data;
  }

  public int getTestScore() {
    return testScore;
  }

  public void setTestScore(int testScore) {
    this.testScore = testScore;
  }
  
  
}
