Niccolo Paganini Selected Works

Posted on 2015-05-01   |   In Music   |  

Leonid Kogan - Cantabile, Paganini

Kogan - La Campanella

Jascha Heifetz - Caprice No. 24

#Classical

Validate Binary Search Tree， Unique Binary Search Trees, Unique Binary Search Trees II, Binary Tree Preorder Traversal,Binary Tree Inorder Traversal ,Binary Tree Postorder Traversal, Binary Tree Zigzag Level Order Traversal, Binary Search Tree Iterator

Posted on 2015-04-16   |   In 刷题   |  

Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Brute force Solution

Inorder traversal, then compare each value…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isValidBST(TreeNode root) {
    if(root==null) return true;
    LinkedList<Integer> p = new LinkedList<Integer>();
    inorder(root, p);
    for (int j =0;j< p.size() - 1;j++) {
        if(p.get(j)>=p.get(j+1))
        return false;
    }
    return true;
}
private void inorder(TreeNode r, LinkedList<Integer> p){
    if(r==null) return;
    inorder(r.left,p);
    p.add(r.val);
    inorder(r.right,p);
}

Or use static variable to store the previous val:

1
2
3
4
5
6
7
8
9
10
public static int pre = Integer.MIN_VALUE; 
public boolean isValidBST(TreeNode root) {
    if(root==null) return true;
    if(!isValidBST(root.left)) return false;
    if(root.val<=pre) return false;
    System.out.println(pre);
    pre=root.val;
    if(!isValidBST(root.right)) return false;
    return true;
}

Recursive/MinMax Solution

At each node we must satisty

  • left subtree max value must not exceed cur.val
  • right subtree min value must not be lower than cur.val
1
2
3
4
5
6
7
8
9
public boolean isValidBST(TreeNode root) {
    return dfs(root, (long)Integer.MIN_VALUE-1,(long)Integer.MAX_VALUE+1);
}
private boolean dfs(TreeNode r,long minv, long maxv){
    if(r==null) return true;
    if(r.val>=maxv ||r.val<=minv) return false;
    return  dfs(r.left, minv, r.val) && dfs(r.right, r.val, maxv);
}

Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.

1
2
3
4
5
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

DP Solution

  • Define c[i] as the number of unique binary tree possibly generated with [0….i]
  • A tree with i as its root, left subtree is consist of [1…i-1], right subtree is consist of [i+1…n]
  • c[0] = 0 ; c[1]=1 ; c[2] = c[0]c[1] //1 as root + c[1]c[0] //0 as root; c[3] = c[0] c[2] //1 as root + c[1] c[1] //2 as root + c[2] * c[0] //3 as root
  • Ct+1 += Ci*Ct-i(0<= i <= t)
  • Ct += Ci*t-1-i(0<=i<=t-1, 1<=t<=n)
1
2
3
4
5
6
7
8
9
10
11
12
public int numTrees(int n) {
        if(n == 0||n == 1)
            return 1;
        int[] C = new int[n+1];
        C[0] = 1;
    for(int t=1;t<=n;t++){  
        for(int i=0;i<=t-1;i++){  
            C[t] += C[i]*C[t-1-i];  
        }  
    }
        return C[n];
    }

Unique Binary Search Trees II

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

1
2
3
4
5
1         3     3      2      1
 \       /     /      / \      \
  3     2     1      1   3      2
 /     /       \                 \
2     1         2                 3

DFS Solution

Similar to I, we pick (1…n) as root, recursivly get all left and right subtrees.
We pick one from left subtree and one from right subtree, attach them to current root and return all the possibilities.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public ArrayList<TreeNode> generateTrees(int n) {
    return buildTrees(1,n);
    
}
public ArrayList<TreeNode> buildTrees(int min, int max){
    ArrayList<TreeNode> res = new ArrayList<TreeNode>();
    if(min>max){res.add(null); return res;}
    for(int i=min;i<=max;i++){
        ArrayList<TreeNode> l = buildTrees(min,i-1);
        ArrayList<TreeNode> r = buildTrees(i+1,max);
        for(TreeNode j: l){
            for(TreeNode k:r){
                TreeNode root =  new TreeNode(i);
                root.left = j;
                root.right = k;
                res.add(root);
            }
        }
    }
    return res;
}

Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
6
   1
    \
     2
    /
   3
return [1,2,3].

Recursive Solution

1
2
3
4
5
6
7
8
9
10
11
12
public List<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    preorder(root, res);
    return res;
}
private void preorder(TreeNode n, ArrayList<Integer> res){
    if(n==null) return;
    res.add(n.val);
    preorder(n.left,res);
    preorder(n.right,res);
}

Iterative Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    Stack<TreeNode> stk =new Stack<TreeNode>();
    if(root==null) return res; //别忘了这句...
    stk.push(root);
    while(!stk.isEmpty()){
        TreeNode tmp = stk.pop();
        res.add(tmp.val);
        if(tmp.right!=null) stk.push(tmp.right);
        if(tmp.left!=null) stk.push(tmp.left);
    }
    return res;
}

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
6
   1
    \
     2
    /
   3
return [1,3,2].

Iterative Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> res= new ArrayList<Integer>();
        Stack<TreeNode> stk=new Stack<TreeNode>();
        if(root==null) return res;
        stk.push(root);
        while(!stk.isEmpty()){
            TreeNode tmp = stk.pop();
            if(tmp == null){
                res.add(stk.pop().val);
            }
            else{
                if(tmp.right!=null){stk.push(tmp.right);}
                stk.push(tmp);
                stk.push(null);
                if(tmp.left!=null){stk.push(tmp.left);}
            }
        }
        return res;

Binary Tree Postorder Traversal

Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3},

1
2
3
4
5
6
   1
    \
     2
    /
   3
return [3,2,1].

Recursive Solution

1
2
3
4
5
6
7
8
9
10
11
12
public List<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    postorder(root, res);
    return res;
}
private void postorder(TreeNode n, ArrayList<Integer> res){
    if(n==null) return;
    postorder(n.left,res);
    postorder(n.right,res);
    res.add(n.val);
}

Iterative Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public List<Integer> postorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    Stack<TreeNode> stk =new Stack<TreeNode>();
    if(root==null) return res; 
    stk.push(root);
    while(!stk.isEmpty()){
        TreeNode tmp = stk.pop();
        if(tmp==null) res.add(stk.pop().val);
        else{
            stk.push(tmp);
            stk.push(null);
            if(tmp.right!=null) stk.push(tmp.right);
            if(tmp.left!=null) stk.push(tmp.left);
        }
    }        
    return res;
}

Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).
For example:

1
2
3
4
5
6
7
8
9
10
11
12
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

Recursive Solution

  • Simple DFS, check height%2 each level
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ArrayList<List<Integer>> zigzagLevelOrder(TreeNode root) {
 ArrayList<List<Integer>> res = new ArrayList();
 if(root==null) return res;
 dfs(root, res, 0);
 return res;
 }
private void dfs(TreeNode r, ArrayList<List<Integer>> res, int h){
    if(r==null) return;
    if(h>res.size()-1){
        res.add(new ArrayList<Integer>());
    }
    if(h%2==1){
        res.get(h).add(0,r.val);
    }  
    else{
        res.get(h).add(r.val);
    }
    dfs(r.left, res, h+1);
    dfs(r.right,res,h+1);
}

Iterative Solution

  • a queue to store nodes in BFS order
  • a boolean value to decide insert order in each level list
  • each new level, set poopsite direction, clear list and add to result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public ArrayList<List<Integer>> zigzagLevelOrder(TreeNode root) {
  ArrayList<List<Integer>> res = new ArrayList();
  if(root==null) return res;
  Queue<TreeNode> q = new LinkedList<TreeNode>();
  List<Integer> tmp = new ArrayList<Integer>();
  q.offer(root);
  int size = q.size();
  boolean l2r = true;
  while(!q.isEmpty()){
      TreeNode cur = q.poll();
      size--;
      if(l2r){
         tmp.add(cur.val);
         }
      else{
         tmp.add(0,cur.val);
      }
      if(cur.left!=null) q.offer(cur.left);
      if(cur.right!=null) q.offer(cur.right);
      if(size==0){
          res.add(new ArrayList(tmp));
          l2r=!l2r;
          tmp.clear();
          size = q.size();
      }
  }
  return res;
  }

Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Solution

  • Use one Array to store the inorder traversal of nodes 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ArrayDeque<TreeNode> arr;
public BSTIterator(TreeNode root) {
    arr = new ArrayDeque<TreeNode>();
    inorder(root, arr);
}
private void inorder(TreeNode root, ArrayDeque<TreeNode> arr){
    if(root==null) return;
    inorder(root.left, arr);
    arr.add(root);
    inorder(root.right,arr);
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
    return !arr.isEmpty();
}
/** @return the next smallest number */
public int next() {
    if(hasNext()) return arr.poll().val;
    else return -1;
}

O(1) Time O(h) Memory Solution

  • Dissect inorder into two parts
  • push root’s all left children into stack
  • upon calling next(), pop one node and push all right child’s left child into stack 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Stack<TreeNode> stk;
public BSTIterator(TreeNode root) {
    stk = new Stack<TreeNode>();
    while(root!=null){
        stk.push(root);
        root=root.left;
    }
   
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
    return !stk.isEmpty();
}
/** @return the next smallest number */
public int next() {
    if(!stk.isEmpty())
        {TreeNode tmp = stk.pop();
         int res=tmp.val;
         if(tmp.right!=null){
             TreeNode node = tmp.right;
             while(node!=null){
                 stk.push(node);
                 node=node.left;
             }
         }
         return res;
        }
        else return -1;
}
#Tree #Recursion #Stack

Maximum Subarray, Maximum Product Subarray

Posted on 2015-04-11   |   In 刷题   |  

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

O(n) Solution

  • It’s called the Kadane’s Algorithm…
1
2
3
4
5
6
7
8
9
10
public int maxSubArray(int[] A) {
    int max_so_far = A[0];
    int max_ending_here = A[0];
    for (int i=1;i<A.length;i++){
        max_ending_here+=A[i];
        max_ending_here = Math.max(max_ending_here, A[i]);
        max_so_far = Math.max(max_ending_here, max_so_far);
    }
    return max_so_far;
}

Divide and Conquer Solution O(nlogn)

  • more subtle does not mean cleaner…
  • divide the given array in two halves and return the maximum of following three
  • Maximum subarray sum in left half
  • Maximum subarray sum in right half
  • Maximum subarray sum such that the subarray crosses the midpoint
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int maxSubArray(int[] A) {
         int l=0, r=A.length-1;
         return rec(A, l, r);
    }
    
    private int rec(int[] A, int l, int r){
        if(l==r) return A[l];
        int m= (l+r)/2; 
        return Math.max(Math.max(rec(A,l,m),rec(A,m+1,r)),cross(A,m,l,r));
    }
    
    private int cross(int[] A, int m, int l, int r){
        int suml=A[m];
        int maxvaluel=A[m];
        for (int i=m-1;i>=l;i--){
            suml+=A[i];
            if(suml>maxvaluel){
                maxvaluel=suml;
            }
        }
        int sumr=A[m];
        int maxvaluer=A[m];
        for (int i=m+1;i<=r;i++){
            sumr+=A[i];
            if(sumr>maxvaluer){
                maxvaluer=sumr;
            }            
        }
        return maxvaluel+maxvaluer-A[m];
    }

Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

Near Brute force

  • If we store result from i to j in t[i][j], the runtime is O(n^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxProduct(int[] A){
	int maxvalue=0;
	for(int i=0;i<A.length;i++){
		for(int j=i;j<A.length;j++){
			int tmp=1;
			for(int k=i;k<=j;k++){
			tmp*=A[k];
					}
			if(tmp>maxvalue){
				maxvalue=tmp;
			}
		}
	}
	return maxvalue;
}

DP? Solution

  • There are only two cases when we get a larger result
  • mininum(negative) value multiply cur value(which happens to be negative)
  • maximum value multiply cur value
  • Be careful with the special case when multiplying both would decrease the result, then change start point to self
1
2
3
4
5
6
7
8
9
10
11
12
public int maxProduct(int[] A){
	int maxvalue=A[0];
	int minval=A[0], maxval=A[0];
	for(int i=1;i<A.length;i++){
	    int a=A[i] * minval;
	    int b=A[i] * maxval;
	    maxval=Math.max(Math.max(a,b),A[i]);
	    minval=Math.min(Math.min(a,b),A[i]);
	    maxvalue=Math.max(maxvalue,maxval);
	}
	return maxvalue;
}
#Array #DP

StringtoLong, Implement Trinary Tree

Posted on 2015-04-02   |   In 刷题   |  

StringtoLong

Converts input String to Long

Solution

  • input validation
  • Over/Underflow
  • positive/negative 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
long stringToLong(String s)
	{
		// Use Regex to filter out illegal inputs
		if(!s.matches("-?\\d+")){ 
			throw new NumberFormatException("input String " + s + " is illegal number format");
		}
		// Convert a string to a long 
		long result = 0;
		boolean IsNegative = s.charAt(0)== '-';
		int start=IsNegative ? 1:0;
		for(int i=start;i<s.length();i++){
			/* Deal with overflow and underflow */
			
			if(((!IsNegative) && result > (Long.MAX_VALUE)/10 )|| ((!IsNegative) && result == (Long.MAX_VALUE)/10 && (s.charAt(i) - 48)>7)){
				
				throw new NumberFormatException("input String " + s + " out of bound (overflow)");
			}
			else if((IsNegative && (-1 * result) < (Long.MIN_VALUE)/10 ) || (IsNegative &&  (-1 * result) == (Long.MIN_VALUE)/10 ) && (s.charAt(i) - 48)>8 ){
				
				throw new NumberFormatException("input String " + s + " out of bound (underflow)");
			}
			else{
				result=result * 10 + (s.charAt(i) - 48);
			}
		}
		return IsNegative ? -result : result;
	}

Implement Trinary Tree

Insersion and Deletion

Solution

  • Define Node class
  • Recursivly add/delete node
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class TrinaryNode{
	int val;
	TrinaryNode left;
	TrinaryNode right;
	TrinaryNode middle;
	TrinaryNode(int x){
		this.val = x;
	}
}
////////////
TrinaryNode root;
	TrinaryTree(){
		root = null;
	}
	TrinaryTree(int x){
		root = new TrinaryNode(x);
	}
	//Insertion
	TrinaryNode insert(TrinaryNode root, int x){
		TrinaryNode tmp = new TrinaryNode(x);
		//Insert root if root is not set
		if(root==null){
			root = tmp;
			return root;
		}
		//Find target position in left subtree if x is smaller than current node
		if(root.val > x){
			if(root.left==null){
				root.left = tmp;
			}
			else{
				insert(root.left, x);
			}
		}
		//Find target position in right subtree if x is larger than current node
		if(root.val < x){
			if(root.right==null){
				root.right = tmp;
			}
			else{
				insert(root.right, x);
			}
		}
		//Find target position in middle subtree if x is equal to current node
		if(root.val == x){
			if(root.middle==null){
				root.middle = tmp;
			}
			else{
				insert(root.middle, x);
			}
		}
		return root;
	}
	//Deletion
	TrinaryNode delete(TrinaryNode root, int x){
		//Target node is in left subtree
		if(root.val > x){
			root.left = delete(root.left, x);
		}
		//Target node is in right subtree
		else if(root.val < x){
			root.right = delete(root.right, x);
		}
		//Target node equals current node
		else if(root.middle != null){
			//Delete middle node that is equal to current node
			root.middle = delete(root.middle ,x);
		}
		//Replace current node with its successor in right subtree
		else if(root.right !=null){ 
			root.val = Sucessor(root.right).val;
			delete(root, Sucessor(root.right).val);
		}
		//Transplant left subtree directly
		else {
			root = root.left;
		}
		return root;
	}
	//Function to find successor in right subtree
	TrinaryNode Sucessor(TrinaryNode root){
		TrinaryNode tmp = root;
		while(tmp.left!=null){
			tmp=tmp.left;
		} 
		return tmp;
	}
	//Function to in-order traverse the tree for testing purpose
	void test_print(TrinaryNode root){
		if (root!=null){
			System.out.println("Node Value: " + root.val);
		}
		else return;
		test_print(root.left);
		test_print(root.middle);
		test_print(root.right);
	}
#Math #Recursion #String #Tree

Unique Combination of Factors, Factorial Trailing Zeroes

Posted on 2015-03-24   |   In 刷题   |  

Unique Combination of Factors

Print all unique combinations of factors of a positive integer. For example given 24:

1
2
3
4
5
6
7
24*1
12*2
8*3
6*4
6*2*2
4*3*2
3*2*2*2

Solution

Reverse DFS all possible division combinations. Keep track of current dividend, try all divisors. Use backtracking to gather all all possible division combinations.

1
2
3
4
5
6
7
8
     24
  /   |  \
 1    6    24
/ \ / | \  / \
....  2  4 ....
	   |
	  / \
    1   2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public ArrayList<ArrayList<Integer>> factorCombinations(int n){
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> tmp = new ArrayList<Integer>();
		ArrayList<Integer> first=new ArrayList<Integer>();
		first.add(n);first.add(1);
		res.add(first);
		res=dfs(res, n, n/2, tmp);
		return res;
	}
	private ArrayList<ArrayList<Integer>> dfs(ArrayList<ArrayList<Integer>> res, int Curdividend, int Largestdivisor, ArrayList<Integer> tmp){
		if(Curdividend==1){
			res.add(new ArrayList<Integer>(tmp));
			return null;
		}
		for(int i=Largestdivisor; i>1;i--){
			if(Curdividend%i==0){
				tmp.add(i);
				dfs(res,Curdividend/i, i,tmp);
				tmp.remove(tmp.size()-1);
			}
		}
		return res;
	}

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

1
2
3
4
5
6
7
8
9
public int trailingZeroes(int n) {
       if(n<5) return 0;
       int count_of_five=0;
       while(n>1){
           n=n/5;
           count_of_five+=n;
       }
       return count_of_five;
   }
#Math #Recursion

Stack and Heap

Posted on 2015-03-20   |   In 刷题   |  

Overview

Value types are created on the stack, and reference types are created on the heap.

Both are stored in computer RAM.

Each thread gets a stack, while there’s typically only one heap for the application.

Stack

When a function is called, a block is reserved on the top of the stack for local variables and some bookkeeping data in a LIFO order. Freeing a block from the stack is nothing more than adjusting one pointer.

Heap

Unlike the stack, there’s no enforced pattern to the allocation and deallocation of blocks from the heap; you can allocate a block at any time and free it at any time. This makes it much more complex to keep track of which parts of the heap are allocated or free at any given time; there are many custom heap allocators available to tune heap performance for different usage patterns.

Q & A

What is their scope?

The stack is attached to a thread, so when the thread exits the stack is reclaimed.

The heap is typically allocated at application startup by the runtime, and is reclaimed when the application (technically process) exits.

What determines the size of each of them?

The size of the stack is set when a thread is created.

The size of the heap is set on application startup, but can grow as space is needed (the allocator requests more memory from the operating system).

What makes one faster?

The stack is faster because the access pattern makes it trivial to allocate and deallocate memory from it, while the heap has much more complex bookkeeping involved in an allocation or free.

Each byte in the stack tends to be reused very frequently which means it tends to be mapped to the processor’s cache, making it very fast.

Another performance hit for the heap is that the heap, being mostly a global resource, typically has to be multi-threading safe, i.e. each allocation and deallocation needs to be (typically) synchronized.

#Design

Basic Data Structure

Posted on 2015-03-13   |   In CC   |  

List

Iterator

  • if structural change is made(add, remove, clear), iterator is no longer valid
  • if iterator invokes its remove method, then iterator is still valid
  • main advantage of remove method from iterator is that Collection’s remove method must first find the item to remove

ArrayList

  • advantage
    • calls to get and set take constant time
  • disadvantage
    • insertion and removal might be expensive unless changes are made at the end of arraylist
    • inefficient for search
    • notation of capacity(size of underlying array)
  • operation
    • get, set: O(1)
    • insertion(add to front) and removal: O(n)

LinkedList

  • advantage
    • insertion and removal is cheap(constant time), provided the position of the changes is known
  • disadvantage
    • not easily indexable
    • calls to get and set might be expensive
    • inefficient for search
  • operation
    • get, set: O(n)
    • insertion, removal: O(1)

Stack

  • operation
    • push: O(1)
    • pop: O(1)
  • implementation
    • list: push is to add node to the front of list and pop is to remove from front of list
    • array: topOfStack is initialized to -1, when push, arr[topOfStack++]=element; when pop, return arr[—topOfStack]; use topOfStack==-1 to check if emtpy
  • applications
    • balance symbols
    • postfix expression
    • infix to postfix conversion
    • method calls

Queue

  • idea
    • insertion is done at one end
    • deletion is doen at the other end
  • operation
    • enqueue: O(1)
    • dequeue: O(1)

Nested Class vs. Inner Class

  • nested class
    • when make something a nested class, it is placed inside of another class which is the outer class
    • must use static to signify it is nested; without static, it would be inner class
    • nested class can be made private so that it is inaccessible from classes outside outer class
  • inner class
    • when declare inner class, compiler adds implicit reference to outer class that caused the inner class’s construction
    • The inner class is useful in a situation in which each inner class object is associated with exactly one instance of an outer class object. In such a case, the inner class object can never exist without having an outer class object with which to be associated

Tree

General trees

  • representation
    • first child + next sibling for tree node
1
2
3
4
class TreeNode{
   Object element;
   TreeNode firstChild;
   TreeNode nextSibling;
  • traversal
    • preorder traversal
      • root->left->right
      • application in file system(list all files in directory)
1
2
3
4
5
6
7
8
9
10
11
public void listAll(){
   listAll(0);
}
public void listAll(int depth){
   printFileName(depth);
   if(isDirectory()){
      for each file in the directory
          listAll(depth+1)
   }
}
  • postorder traversal
    • left->right->root
    • compute size of directory
1
2
3
4
5
6
7
8
public int dirSize(){
    int totalSize = sizeOfFile();
    if(isDirectory()){
      for each file f in directory
          totalSize += c.dirSize()
    }
    return totalSize;
}
  • levelorder traversal
  • inorder traversal
    • left->root->right
  • application
    • file system

Binary Tree

  • overview
    • average depth is O(sqrt(N)), worst case depth is N-1
    • for binary search tree, average depth is O(logN)
  • representation
1
2
3
4
5
class BinaryNode{
   Object element;
   BinaryNode left;
   BinaryNode right;
}
  • application
    • expression tree
      • push operands to stack while reading
      • if see an operator, pop two trees(operands) from stack, build a new tree and push onto the stack

Binary Search Tree

  • overview

    • values in left subtree less than root value
    • values in right subtree larger than root value

  • operations

    • time O(depth), for average depth, time O(logn)

  • balance and self-adjusting

AVL Tree

  • overview

    • almost identical to binary search tree
    • for every node, height of left and right subtree differ at most 1

  • rotation

Splay Tree

B-Tree

Set and Map in Standard Libary

Set

  • overview

    • do not allow duplicate

  • types

    • TreeSet(Sorted Set): worst time O(logn)

Map

  • overview

    • a collection of entries of keys and values
    • keys must be unique
    • several keys can be mapped to the same value
    • map does not provide iterator

  • types

    • TreeMap(Sorted Map): keep keys in sorted order

Hashing

  • overview
    • perform insertion, deletion, searching in average O(1) time
    • print in sorted order in O(n) not supported
    • load factor: ratio of number of elements in the hash table to the table size

hash function

  • determinism: given an input, always generate the same value
  • uniformity: map inputs as evenly as possible over its output range
  • defined range: desirable that outputs of hash function have fixed size
  • continuity: a hash function that is used to search for similar data must be as continuous as possible, two inputs differing a little should be mapped to nearly equal hash values
  • non-invertible: impossible to reconstruct input from hash value

collisions

  • given inputs map to the same hash value
  • separate chaining
    • idea: keep a list elements that hash to the same value
    • operations
      • search: first determine which list to traverse and then search appropriate list
      • insertion: first check appropriate list to see whether element is already in place(if duplicates allowed, keep an extra field); if element is new, insert into the front of list because recently inserted elements are more likely to be used in the near future
    • disadvantage
      • using linkedlist
      • slow down time to allocate new cells
      • require implementation of another data structure
  • probing
    • hash function: h_i(x) = (hash(x) + f(i)) % TABLE_SIZE
    • types
      • linear probing
        • f(i) = i
        • primary clustering: as long as table is large enough, a free cell can always be found but might take a long time; when table is relatively empty, blocks of occupied cells start forming
        • insertions and unsuccessful search require the same number of probes
        • on average, successful search takes less time than unsuccessful search
      • quadratic probing
        • f(i) = i^2
        • eliminate the primary clustering
        • no guarantee finding free cell when table gets more than half full or even before if table size is not prime because at most half of the table can be used as alternative locations to resolve collisions
        • table size must be prime, otherwise insertion might fail
        • secondary hashing
          • solution by double hashing: f(i)=i*hash2(x)

rehashing

  • when table gets too full, operations start taking too long
  • solution: build another table with twice size, compute new hash value for new table
  • running time: O(n)
  • options
    • rehash as soon as table is half full
    • rehash only when an insertion fails
    • rehash when table reaches a certain load factor

hash tables with worst O(1) time

Priority Queue(Heap)

  • structure property
    • a heap is a binary tree that is completely filled(exception at the bottom level), the average height of complete binary tree is O(logN)
    • for any element in array position i
      • left child: 2i
      • right child: 2i+1
      • parent: floor(i/2)
    • heap consists of Comparable objects
  • heap order property
    • smallest(largest) element at the root
    • min-heap: for every node X, key in the parent of X is <= key in X
    • order property ensures findMin() in O(1) time
  • operations
    • insert()
      • create a hole in next available position, if order property not violated, done; otherwise, heapify up
      • time O(logN) if inserted element is new minimum(maximum)
    • deleteMin()
      • find minimum is easy
      • removing minimum will create a hole in the root, we must move last element X in the heap to correct position
      • put X in correct spot along a path from the root containing minimum children(heapify down)
      • time: worst O(logN), average O(logN)
    • decreaseKey()
      • lowers the value of item at position p by positive amount
      • if violate order property, heapify up
      • application: make something with higher priority
    • increaseKey()
      • increase the value of item at position p by positive amount
      • if violate order property, heapify down
      • application: scheduler drops the priority of a process that is consuming excessive CPU time
    • delete()
      • remove node at position p
      • first perform decreaseKey(p,infinity) then perform deleteMin()
      • application: process terminated by user
    • buildHeap()
      • done with N successive inserts
      • insert takes O(1) average, O(logN) worst
      • build takes O(N) average, O(NlogN) worst
  • applications
    • selection problem
      • approach one(k smallest elements)
        • read N elements into array and buildHeap
        • perform k deleteMin()
        • time: buildHeap O(N), deleteMin O(logN), total is O(N+klogN)
      • approach two(k largest elements)
        • idea: at any time, maintain a set of k largest elements
        • read first k elements
        • when a new element is read, compare it with kth largest element Sk(Sk is the smallest element in set S)
          • if new element is larger, it replaces Sk
          • otherwise, do nothing
        • finally, return the smallest element in S
        • time: build with first k elements O(k), time to process remaining (N-k)O(logk), total is O(k+(N-k)logk) = O(Nlogk)
    • event simulation
#Concepts

Basic Comparisons

Posted on 2015-03-13   |   In CC   |  

Linkedlist vs. Arraylist vs. Vector

  • Operations

    • LinkedList
      • get(index): O(n)
      • add(element): O(1)
      • add(index, element): O(n)
      • remove(index): O(n)
      • Iterator.remove(): O(1), main benefit
      • Iterator.add(element): O(1), main benefit
    • ArrayList
      • get(index): O(1), main benefit
      • add(element): O(1) amortized, worst case O(n) because need to resize array and copy
      • add(index, element): O(n-index) amortized, worst case O(n)
      • remove(index): O(n-index), remove last is O(1)
      • Iterator.remove(): O(n-index)
      • Iterator.add(element): O(n-index)

  • Compare

    • Linkedlist
      • O(1) time insertions or removals using iterator, but only sequential access
      • finding a position in the linkedlist takes time O(n)
      • each element of linkedlist have more memory overhead because pointers need to be stored
      • linkedlist also implements queue interface which adds more methods such as offer(), peek(), poll()
    • Arraylist
      • fast random read access in O(1)
      • adding or removing element except at the end require shifting latter elements, if add more elements, need to allocate new array and copy old values
      • iterating over arraylist is technically faster
      • to avoid overhead of resizing, construct arraylist with initial capacity

  • Similarities

    • both are implementation of list interface
    • maintain elements in insertion order
    • non-synchronized, but can be made synchronized explicitly
    • if list is structurally modified after iterator is created, except through iterator’s own remove or add method, iterator will throw exception

  • When to use which

    • frequent addition and deletion: linkedlist
    • frequent search: arraylist
    • less memory to store many elements: arraylist

  • Vector

    • almost identical to arraylist, but is synchronized
    • more overhead because of synchronization
    • still use arraylist because they can make it synchronized explicitly by encapsulating: 
1
coll = Collections.synchronizedCollection(coll);

HashMap vs. TreeMap vs. HashTable vs. LinkedHashMap

  • Overview

    • HashMap: implemented as a hash table, no ordering on keys or values
    • TreeMap: implemented based on red-black tree, ordered by key
    • LinkedHashMap: preserves insertion order
    • HashTable: synchronized in constrast to HashMap

  • HashMap

    • operation
      • put(): average O(1), worst O(n) when collision
      • get(), remove(): O(1)
    • if key is self-defined objects, need to implement equals() and hashCode()
    • iteration order not predictable
    • does not allow two identical elements
      • equals(): return true if two references refer to the same object
      • hashCode(): return distinct integers for distinct objects
    • allow null keys and values

  • TreeMap

    • operation
      • put(), get(), remove(): worst O(logn)
    • sorted by keys
    • object for key has to implement Comparable interface
    • only allow values to be null

  • HashTable

    • HashMap is roughly equivalent to HashTable, except hashmap is not synchronized and permits null
    • Hashtable does not allow null keys or values. HashMap allows one null key and any number of null values.

  • LinkedHashMap

    • operation: see arraylist
    • subclass of HashMap
    • linkedlist preserves the insertion order
    • allow null keys and values

Set vs. List vs. Map

  • Set

    • unordered collection
    • unique objects (!e1.equals(e2))
    • contains at most one null

  • List

    • ordered collection(sequence)
    • access by index and search
    • may contain duplicates
    • user has control over where element inserted

  • Map

    • object that maps keys to values
    • no duplicated allowed
    • a key can map to at most one value

BST vs. HashTable

  • BST

    • insert and retrieve: O(logn)
    • store data sorted
    • no need to know size of input in advance
    • memory efficient: do not reserve more memory than they need to

  • HashTable

    • insert and retrieve: O(1)
    • elements stored unsorted
    • with more inputs, collisions may show up
    • need more space than input data if to avoid collision
    • need to know data size, otherwise might need to resize the table

BFS vs. DFS

  • Overview

    • search algorithms for graphs and trees
    • used for unordered graph and tree
    • graph representation
      • adjacent list: space O(V+E)
      • adjacent matrix: space O(V^2)

  • BFS

    • start with root node
    • scan each node in the each level
    • while traversing each level, decide if target is found

  • DFS

    • start with root node
    • follow on branch as far as possible until target is found or hit a leaf node
    • if hit a leaf node, continue search at the nearest ancestor
  • Comparison
    • memory
      • BFS uses a large amount of memory because need to store pointers to a level(serious problem if the tree is very wide)
      • DFS uses less memory because no need to store all child pointers at a level
    • depend on the data you search for
      • look for people alive in family tree: DFS because targets are likely to be on the bottom of the tree
      • look for people who died: BFS
    • implementation
      • BFS: queue
1
2
3
4
5
6
7
8
9
10
procedure BFS(G,v)
   initialize a queue Q
   Q.push(v)
   label v as visited
   while Q is not empty
      v <- Q.pop()
      for all edges from v to w in adjacent(v)
          if w is not visited
             Q.push(w)
             label w as visited
- DFS: stack
  + recursive

1
2
3
4
5
procedure DFS(G,v)
   label v as visited
   for all edges from v to w in adjacent(v)
       if w is not visited
           DFS(G,w)
  + iterative

1
2
3
4
5
6
7
8
9
procedure DFS(G,v)
   initialize stack S
   S.push(v)
   while S is not empty
      v <- S.pop()
      if v is not visited
         label v as visited
            for all edges from v to w in adjacent(v)
                S.push(w)
  • solution
    • BFS: complete algorithm, give optimal solution
    • DFS: suboptimal solution
  • complexity
    • BFS: worst time O(V+E), worst space O(V)
    • DFS: worst time O(v+E), worst space O(V)

Tree vs. Graph

  • tree is restricted form of a graph(directed acyclic graph)
  • trees have direction(parent/child relationship)
  • tree does not contain cycles
  • in trees, a child can only have one parent
#Concepts

Java Related Questions

Posted on 2015-03-13   |   In CC   |  

Java Questions

Contents:

Object Oriented

  • model organized around objects rather than actions and data rather than logic
  • based on the concept of “objects”
  • contain data in the form of fields(attributes)
  • code in the form of procedures(methods)
  • object’s procedures can access and modify the data fields of the associated object

Java Keywords

  • Access modifiers

    | modifier | access in same package | access in different package |
    | ———— | ——————————— | —————————————- |
    | private | no | no |
    | public | yes | yes |
    | default | yes | no |
    | protected| yes | only if extend class |

  • final keyword

    • can be assigned to variable, method, class, object
    • if assigned
      • variable: behave like a constant and cannot change value
      • method: cannot be overridden in its child class
      • class: no other class can extend it
      • object: only instantiated once

  • synchronized keyword

    • provide lock on the object and prevent race condition
    • can be applied to static/non-static methods or block of code
    • only one thread at a time can access synchronized methods
    • if multiple threads, need to wait for execution complete

  • volatile keyword

    • volatile variable stored in main memory
    • every thread can access
    • local copy updated from main memory
    • has performance issues

  • static variable

    • static cannot be used for class
    • everything declared as static is related to class not object
    • multiple objects of a class share the same instance of static variable

  • static method

    • can be accessed without creating the objects
    • use class name to access static method
    • static method can only access static variables and not local or global non-static variable: because if the class is not instantiated and therefore the variables are not initialized and cannot be accessed from a static method
    • static method can only call static methods and not non-static methods
    • non-static methods can call static methods

  • static class

    • class cannot be declared as static
    • class is static if all variables and methods are static and constructor is private, so the only way to access is to use class name

  • throw keyword

    • throw exception manually
    • used when program fails the condition and wants to give warning
    • throw the exception from a method to the calling method
    • calling method can decide to handle exception or throw to its calling method

Concepts

  • object vs. class

    • an object is an instance of a class
      • object refers to an actual instance of a class
      • every object must belong to a class
      • objects are created and then destroyed, only live in the program for limited time
    • objects have a lifespan but classes do not
      • properties of objects can change while they live

  • static and instance method

    • instance method
      • belong to the instance of a class and require the instance before it can be called
      • dynamic binding
      • JVM selects the method to invoke based on the type of object reference, known at run time
    • static method
      • belong to the class itself
      • static binding
      • JVM selects the method to invoke based on the actual class of the object, known at compile time

  • abstract class and interface

    • abstract class
      • contain at least one abstract method
      • can contain numbers of concrete methods
      • variable can be public, private,protected, default, or constants
      • a class can only extend one abstract class
      • not compulsory to implement all methods
      • if want to add a new feature, simply implement in the abstract class and call it from subclass
    • interface
      • only contain abstract methods
      • variable is by default public final, only has constants
      • a class can implement multiple interfaces
      • compulsory to implement all methods
      • if want to add a new feature, need to implement the method in all classes implementing the interface

  • instanceof and isInstance(Object obj)

    • instacneof is a keyword but isInstance() is a method
    • instanceof check whether the object is type of particular class or subclass
    • isInstance() only used to identify if object is of a particular class

  • pass by value and pass by reference

    • Java only supports pass by value, actual value is passed
    • Java passes the references by value, the pointer to the object is passed as value
    • references passed to the method are actually copies of the original references

  • == and equals()

    • == is used to compare the references of the objects
    • equals() can compare the values of two objects

  • StringBuffer and StringBuild

    • StringBuffer is synchronized but StringBuild is not

  • final, finally,finalize()

    • final: a final variable acts like constant, a final method cannot be overridden, a final class is immutable
    • finally: handles exception, clean up after try block
    • finalize(): method helps in garbage collection, invoked before an object is discarded by the garbage collector, allowing it to clean up its state

  • static block and init block

    • static block is loaded when class is loaded by JVM for the first time
    • init block is loaded every time the class is loaded

  • object reflections

    • provide a way to get reflective information of class and object
    • perform operations such as
      • get information about methods and fields present inside the class at runtime
      • get a new instance of a class
      • get and set object fields directly by getting field reference, regardless what the access modifier is
    • advantage
      • help in observing or manipulating runtime behavior
      • help in debugging or testing programs
      • can call method by name when we do not know the method in advance

  • Overload, Override
    -Overloading and overriding are complementary things, overloading means the same method name but different parameters, and overriding means the same method name in a subclass with the same parameters. So its not possible for overloading and overriding to happen at the same time because overloading implies different parameters.

1
2
3
4
5
6
7
8
9
10
  class A {
    public void doSth() { /// }
}
class B extends A {
    public void doSth() { /* method overriden */ }
    public void doSth(String b) { /* method overloaded */ }
}

OOP

  • polymorphism

    • define more than one function with the same name
    • compile time polymorphism(overloading) and runtime polymorphism(overriding)
    • method override: a class method has same name and signature as a method in parent class, JVM determines the proper method to call at runtime
    • method overloading: method with same name but different signature, determined at compile time

  • inheritance

    • allow a child class to inherit some properties from its parent class
    • use extends keyword
    • only public and protected access modifiers can be accessed in child class

  • multiple inheritance

    • Java does not support multiple inheritance
    • diamond problem
    • use of multiple interfaces (or extend a class and implement some interfaces)
1
2
3
4
5
6
7
8
9
interface A{
   add();
}
interface B{
   add();
}
class C implements A,B{
   add();
}

  • abstraction

    • convert real world objects in terms of class

  • encapsulation

    • achieved by combining the methods and attribute into a class
    • class acting like a container encapsulation the properties
    • hide how things work and expose the user requests

Collections

  • ArrayList and vector

    • synchronization
      • ArrayList is not thread-safe but vector is
      • each method in vector class is surrounded by a synchronized block
    • data growth
      • both use arrays to store contents
      • enlarge array if not enough space
    • performance
      • vector is slower than arraylist because of thread-safe

  • Sort objects in lists

    • implement Comparable interface for the object class and override compareTo() method
    • if object class is a jar file, create Comparator and override compare() method
    • call Collection.sort()

  • HashMap and HashTable

    • HashMap is not synchronized but HashTable is
    • use Iterator for HashMap(fail-safe) and enumerator for Hashtable(not fail-safe)
    • HashMap allows null values and only one null key; Hashtable does not allow null key or null value

  • List interface

    • ArrayList
      • resizable array implementation
      • dynamic size
      • not thread-safe
    • Vector
      • ArrayList implementation
      • thread-safe
    • LinkedList
      • also implements Queue interface
      • FIFO
      • faster for insertion and deletion

  • Set interface

    • SortedSet
      • interface extends Set
      • allow data to be sorted
      • all elements inserted must implement Comparator or Comparable interface
    • TreeSet
      • implementation of SortedSet interface
      • O(logn) time for add, remove, contains operations
      • not synchronized
    • HashSet
      • implements Set interface
      • back up by hash table
      • no guarantee on constant order
      • allow null element
      • O(1) time for add,remove,contains

  • Arrays and ArrayList

    • arrays are fixed size but ArrayLists are dynamic
    • elements in the array list can be added or removed at runtime
    • array contains elements of same type but arraylist can contain elements of different type

  • ArrayList and LinkedList

    • both fast in insertion, inserting into arraylist and into first position of linkedlist takes O(1) time
    • random lookup in ArrayList is fast, but slow for LinkedList
    • remove is slow for ArrayList(elements need to be shifted) but fast for LinkedList

  • Advantage of iterator

    • used when no clue about object type
    • iterator allows updates

  • Preferred declaration

    • List<String> list = new ArrayList<String>() not ArrayList<String> list = new ArrayList<String>()
    • because function may take List as parameter
    • more flexible

  • Iterator access and index access

    • insert,update,or delete is faster for iterator access for elements in between the structure
    • insert,update,or delete is faster for index access for elements at the end
    • search is fast for index access

Threading

  • Thread vs. Process
    • definition
      • process: executing instance of an application
      • thread: a path of execution within a process
    • relationship
      • a process can contain multiple threads
      • thread considered as lightweight process
    • comparison
      • thread for small tasks, process for heavy tasks
      • thread within the same process share the same address space(allow threads to read and write data to the same structures and variables, allow communication between threads), but different processes do not
      • threads are easier to create than processes because they do not require a separate address space
      • multi-threading: be careful that threads share structures that should be modified by one thread at a time
      • processes are independent of each other
#Concepts

Shortest word in Dictionary

Posted on 2015-02-27   |  

有一个输入字符，然后我有一个英文字典，说白了就是字符串数组，然后写一个function返回字典里拥有输入字符串里所有字母(非数字或者空格等符号，就是纯字母)的最短的那个字符串。举个例子：
输入字符串”SR 456 T”，字符串数组里有”SORT”，而且是最短的，那么就返回它

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class ShortestDict {
	private List<String> wordList;
	private List<Integer> maskList;
	public ShortestDict(String[] words) {
		wordList = new ArrayList<String>();
		maskList = new ArrayList<Integer>();
		//rewrite comparator to compare string length
		Arrays.sort(words, new Comparator<String>(){
			public int compare(String s1, String s2) {
				return s1.length() - s2.length();
			}
		});
		for (String word : words) {
			wordList.add(word);
			maskList.add(getMask(word));
		}
	}
	public String getShortest(String inputWord) {
		int inputMask = getMask(inputWord);
		for (int i = 0; i < maskList.size(); i++) {
			if (inputMask == (inputMask & maskList.get(i))) {
				return wordList.get(i);
			}
		}
		return "";
	}
	public static int getMask(String word) { 
		int mask = 0;
		word = word.toLowerCase();
		for (char c : word.toCharArray()) {
			if ('a' <= c && c <= 'z') {
				mask |= (1 << (c - 'a'));
			} 
		}
		return mask;
	}
	public static void main(String[] args) {
		String[] words = new String[]{"so99ort", "so1rt", "skype", "so11rt", "apppples"};
		ShortestDict d = new ShortestDict(words);
		System.out.println(d.getShortest("SR 456 T"));
	} 
}
#String