Scala - 1. Setup

Need:
1. JDK 1.8
2. Scala Build Tool (sbt), version 0.13x
3. IDE. Scala IDE for Eclipse or Intellij IDEA


1. JDK 1.8
Install JDK and set PATH of the bin direcotry

Check version: java -version

2. sbt
Install sbt.
Check version: sbt about
Compile and run: sbt
then run

3. Intellij IDEA
Install community edition.
Install Scala plugin.
go to Configure → Project defaults → Project structure and add the JDK
To use it, click Create New Project on the Welcome Screen, then select Scala, and finally SBT Project.

Sorting

Insertion Sort

Selection Sort

Merge Sort

Quick Sort

Bubble Sort

Selenium Learning Notes

Selenium IDE

Working and Handling multiple windows
storeTitle i
openWindow
selectWindow
selectWindow ${i}
close i
close

Selenium Webdriver

java learning part2

input and output

文本界面的输入输出
1. 使用Scanner类
java.util.Scanner
nextInt();
nextDouble();
next();
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
System.out.printf("%d\n", a);

2. use java.io
System.in.read()
System.out.print()

输入一行
BufferedReader in = new BufferedReader(new InputStreamReader( System.in ));
s = in.readLine();
ss = in.readLine();
n = Integer.parseInt( ss );
d = Double.parseDouble( ss );

图形界面的输入输出
文本框 TextField 输入
标签 Label 输出
按钮Button 执行命令
首先需要创建一个Frame

java learning part1

path: 命令所在路径 (javac, java etc.)
classpath: 所要引用的类所在的路径

set path=.;c:\jdk\bin...
set path: 查看当前path

javac -cp libxx.jar xxx.java
java -cp libxx.jar xxx
//临时设一下classpath, 用-cp

使用package时的编译
文件和路径一致
程序中使用package语句
使用import语句
javac -d classes src\edu\uiuc\tds\ui\*.java src\edu\uiuc\tds\util\*.java src\edu\uiuc\tds\*.java
java -cp classes edu.uiuc.tds.PackageTest

运行applet
javac xxx.java
appletViewer xxx.html
applet替代物: Flash, SilverLight, javascript, HTML5

javac 编译
java 运行
javaw 运行图形界面
appletViewer 运行applet程序
jar 打包工具
javadoc 生成文档
javap 查看类信息及反汇编

jar打包
javac A.java
jar cvfm A.jar A.man A.class (c create, v显示详情verbose, m表示生成清单文件, f表示指定文件名
java A.jar
A.man一般命名为MANIFEST.MF

javadoc -d 目录名 xxx.java
/** */

Iterator

Iterator, an interface in java.util for iterating sequence of objects.

public interface Iterator {
    boolean hasNext();
    Object next();
    void remove();                          // The remove() method is optional.
  }

An Iterator is like a bookmark.
 Just as you can have many bookmarks in a book, you can have many Iterators iterating over the same data structure, each one independent of the others.

One Iterator can advance without disturbing other Iterators that are iterating over the same data structure.
The first time next() is called on a newly constructed Iterator, it returns the first item in the sequence. Each subsequent time next() is called, it returns the next item in the sequence.
 After the Iterator has returned every item in the sequence, every subsequent call to next() throws an exception and halts with an error message. (I find this annoying; I would prefer an interface in which next() returns null. The Java library designers disagree.)

To help you avoid triggering an exception, hasNext() returns true if the Iterator has more items to return, or false if it has already returned every item in the sequence. It is usually considered good practice to check hasNext() before calling next(). (In the next lecture we'll learn how to catch exceptions; that will give us an alternative way to prevent our program from crashing when next() throws an exception.)

 There is usually no way to reset an Iterator back to the beginning of the sequence. Instead, you construct a new Iterator.

Most data structures that support Iterators "implement" another interface in
java.util called "Iterable".

public interface Iterable {
    Iterator iterator();
  }

怎么用，一般来说，如果想遍历一个数据结构DS，就call DS.iteratre(); 这个method会constructs and returns DSIterator whose fields are initialized so it is ready to return the first item in DS.

例子:

/* list/SListIterator.java */

package list;
import java.util.*;

public class SListIterator implements Iterator {
  SListNode n;

  public SListIterator(SList l) {
    n = l.head;
  }

  public boolean hasNext() {
    return n != null;
  }

  public Object next() {
    if (n == null) {
      /* We'll learn about throwing exceptions in the next lecture. */
      throw new NoSuchElementException();                       // In java.util
    }
    Object i = n.item;
    n = n.next;
    return i;
  }

  public void remove() {
    /* Doing it the lazy way.  Remove this, motherf! */
    throw new UnsupportedOperationException("Nice try, bozo."); // In java.lang
  }
}

/* list/SList.java */

package list;
import java.util.*;

public class SList implements Iterable {
  SListNode head;
  int size;

  public Iterator iterator() {
    return new SListIterator(this);
  }

  [other methods here]
}

Ruby on Rails

Tools:
 Rake - Create/migrate database, clear web session data.
 WEBrick - Web server for hosting Rails web applications.
 SQLite - A simple database system.
 Rack Middleware - Standardized interface for interaction between web server and web application.

rails new hello_www
cd hello_www
rails server (start a web server)

Under hello_www (Rails root):
app: models, views, and controllers code
bin: helper scripts (bundle, rails, rake)
config: App, database and route configuration
db: database schema and migrations
Gemfile: specify the required gems
lib:
log: application logging directory
pulic: webroot of the application
test: Tests - Agile development

Popular web application frameworks

- Ruby on Rails (Ruby)
- Play (Java and Scala)
- ASP.NET MVC (Microsoft)
- Django (Python)
- Sinatra (Ruby) (very light-weight)
- Symfony (PHP)
- Sails.js (Node.js, JavaScript)

Content management systems (CMSs):
WordPress, Drupal, Joomla!

The MVC Design pattern
Model-View-Controller model
 - Decouples data (model) and presentation (view)
 - A controller handles requests, and coordinates between the model and the view
 - More robust applications, easier to maintain

MVC control flow:
 1. User interface (view) awaits user input
 2. User provides input, e.g., clicks a button
 3. Controller handles the input event -> some action (handler or callback) understandable by the model
 4. Controller notifies the model, possibly changing the model's state
 5. Controller notifies the view (if it needs to be updated). Back to step 1.

PriorityQueue

Operations:
add O(logn), find largest O(1), remove largest O(log(n))

Application:
scheduling long streams of actions to occur at various future times.
useful for sorting.

Common implementation is Heap.

Heap:
max-heap is a binary tree that:
Both labels in both children of each node are less than node's label

So node at the top has largest label.

Longest Increasing Subsequence

Leetcode 300
Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

O(n^2):
Naive solution is use array T[] to track the LIS for each element in the original array. We have to track all the elements because the LIS can only increase for previous element which are smaller than current element.

public class Solution {
    public int lengthOfLIS(int[] nums) {
        // naive solution, keep another array to store the LIS so far. O(n^2)
        if (nums==null || nums.length == 0) return 0;
        int[] lens = new int[nums.length];
        int maxsofar = 1;
        for (int i = 0; i < nums.length; i++) {
            lens[i] = 1;
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if ((lens[j]+1) > lens[i]) {
                        lens[i] = lens[j] + 1;
                    }
                }
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (lens[i] > maxsofar) maxsofar = lens[i];
        }
        return maxsofar;
    }
}

Best Time to Buy and Sell Stock

1. Best Time to Buy and Sell Stock

Leetcode 121 (M)
只能买卖一次。
只能一次的话，就是要寻找最小和最大的值（同时必须满足最大值在最小值后面）
可以用两个值来存,maxcurr记录对于第i天可以拿到的最大利润，maxsofar记录到目前为止见过的最大利润（最大的maxcurr)。
所以唯一的问题是如何计算maxcurr，如果maxcurr小于0，那么就是0，对于第i天的maxcurr来说，如果maxcurr + (p[i] - p[i-1]) > 0, 那么更新maxcurr。

或者可以，一直寻找最小的minprice，然后用prices[i]-minprice，同时即时更新minprice。

code1:

public class Solution {
    public int maxProfit(int[] prices) {
        int maxcurr = 0;
        int maxsofar = 0;
        for (int i = 1; i < prices.length; i++) {
            maxcurr = Math.max(0, maxcurr + (prices[i] - prices[i-1]));
            maxsofar = Math.max(maxsofar, maxcurr);
        }
        return maxsofar;
    }
}

code2:

public int maxProfit(int[] prices) {
    int profit = 0;
    int minElement = Integer.MAX_VALUE;
    for(int i=0; i < prices.length; i++){
       profit = Math.max(profit, prices[i]-minElement);
       minElement = Math.min(minElement, prices[i]);
    }
    return profit;
}

1. Best Time to Buy and Sell Stock II

Leetcode 122 (M)

可以买卖多次。这样的话很容易理解，就是把所以递增的都增量都加起来就可以了。因为如果是递增，那么price[j] - price[k] = price[j]-price[i] + price[i]-price[k]

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        
        int total = 0;
        
        for (int i = 1; i < prices.length; i++) {
            total += Math.max(0, prices[i] - prices[i-1]);
        }
        return total;
    }
}

1. Best Time to Buy and Sell Stock III
2. Best Time to Buy and Sell Stock IV
3. Best Time to Buy and Sell Stock with Cooldown

Dynamic Programming

Dynamic programming is a technique for solving problems with the following properties:

1. An instance is solved using the solutions for smaller instances.
2. The solution for a smaller instance might be needed multiple times.
3. The solutions to smaller instances are stored in a table, so that each smaller instance is solved only once.
4. Additional space is used to save time.

经典题目：

1. 买卖股票I II III IV

Java技能

Java：
1. OO, 常用Java API (collection, multithreads, I/O (NIO), Socket, JDBC, XML, reflection)。
2. JSP and Servlet (Java web). JSTL/EL。监听器，过滤器（Web组件)。MVC架构模式进行java web项目开发。
3. Spring IoC container。 AOP原理。Spring框架管理各种web组件。
4. Hibernate, MyBatis等ORM框架。熟悉他们的核心API。对hibernate的关联映射，继承映射，组件映射，缓存机制，事务管理，性能调优。
5. HTML/CSS/JavaScript web前端。JQuery和Bootstrap。Ajax在web项目中的应用。前端MVC框架(AngularJS)和JavaScript模板引擎(HandleBars)。
6. 常用的relatinal db (MySQL, Oracle)。熟练使用SQL和PL/SQL。

7. Design Pattern。GoF设计模式。UML。 TDD/DDD
8. Apache, NginX, Tomcat, WildFly, Weblogic等web服务器和应用服务器的使用。
9. 产品原型工具Axure。设计建模工具PowerDesigner和Enterprise Architect。Java开发环境Eclipse和IntelliJ。前端开发环境webstorm。版本控制svn和git。项目构建和管理工具Maven和Gradle。

项目：
本系统是X委托Y开发的用于Z的系统，系统包括A, B, C, D等模块。系统使用了java企业级开发的开源框架E以及前端技术F。表示层运用了G架构，使用H作为视图I作为控制器并实现了REST风格的请求；业务逻辑层运用了J模式，并通过K实现事务、日志和安全性等功能，通过L实现缓存服务；持久层使用了M封装CRUD操作，底层使用N实现数据存取。整个项目采用了P开发模型。

E: Spring
F: JQuery库及其插件，或者是Bootstrap框架。 SPA(单页应用）最佳方案是前端MVC框架（AngularJS）和JavaScript模板引擎(HandleBars)。
G: MVC (模型-视图-控制）。Spring MVC, Struts 2, JSF
J：事务脚本
K: AOP技术
L：memcached和Redis
M: 选择很多，Hibernate和MyBatis （一般来说增删改交给hibernate，复杂查询给MyBatis）
N: Relational DB (MySQL, Oracle, SQLServer etc.), 或者NoSQL(MongoDB, MemBase, BigTable)，和其他大数据存取方案（GFS, HDFS)。
P: 瀑布模型，快速原型模型，增量模型，螺旋模型，喷泉模型，RAD模型。

版本控制： CVS/SVN/Git
自动构建：Ant/Maven/Ivy/Gradle
持续集成： Hudson/Jenkins

系统架构：
负载均衡服务器：F5, A10
应用服务器：
    Http: Apache, NginX
    Servlet: Tomcat, Resin
    EJB容器: WildFly(JBoss Application Server), GlassFish，Weblogic, WebSphere
数据库服务器: MySQL / Oracle

第三方工具（插件）应用
图表工具: 基于jQuery的图标插件(jQchart, Flot, Charted）
报表工具： Pentaho Reporting, iReport, DynamicReports等
文档处理： POI, iText
工作流引擎：

常用java API

HashSet:
https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html

• java.lang.Object
• • java.util.AbstractCollection<E>
  • • java.util.AbstractSet<E>
    • • java.util.HashSet<E>

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, Set<E>

Methods:
  boolean add(E e)
  boolean contains(O o)
  int size()
  boolean isEmpty()
用处：
  当不需要map的时候（比如只存数字便于查找），可以用HashSet。

Leetcode 52 - N-Queens II

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

Backtracking (recursive)
RecursiveNQueens(Q[1 .. n],r):
if r = n + 1
    print Q
else for j ← 1 to n
    legal ← True
    for i ← 1 to r − 1
        if (Q[i] = j) or (Q[i] = j + r − i) or (Q[i] = j − r + i)
        legal ← False
    if legal
        Q[r] ← j
        RecursiveNQueens(Q[1 .. n],r + 1)

Bit Manipulation

Bit Manipulation

常用operators:
~        unary bitwise complement operator, inverts a bit pattern
<<       signed left shift operator
>>       signed right shift operator
>>>     unsigned right shift operator, a zero into the leftmost position
&        bitwise AND
^         bitwise exclusive OR   (必须有且只有一个为真才行）
|          bitwise inclusive OR

特性：
（n&(n-1) == 0) true if n is power of 2. (or if n=1)
  n^n = 0
可以用来判断两个词有没有重复字符

常见问题：
Leetcode 136 - Single Number
Leetcode 268 - Missing Number
Leetcode 318 - Maximum Product of Word Lengths

Class and Project - Design and Refactoring

Goal: Design a class to support path finding through a maze
Questions:
1. What do I want to do with the graph?
2. What is the ration of edges to nodes? (adj list or matrix?)
3. How do I need to access to nodes/edges?
4. What properties do nodes and edges need to store?

Objects that make sense, whose data and methods go together.
Interfaces are clean; private data (or data structures) are not exposed.
Easy and fast to do the operations you want to do.
Methods are short and easy to read and understand.

DFS is not short!
Solution: refactor! - restruture code without changing functionality
Each method should have one task!

还可以创建一个MazeEdge class
以及一个Coordinate class来存coordinate。

Leetcode 217 - Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

需要能够快速查询，然后有一个数和对应出现次数的对应，所以想到用Hashtable
Solution1:

import java.util.*;
public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Hashtable nummap = new Hashtable();
        for (int n : nums) {
            if (nummap.get(n) != null) return true;
            else nummap.put(n,1);
        }
        return false;
    }
}

其实只关心每个num出现没出现，0或者1，所以用不到map，只需要知道有没有就可以，所以hashset就可以。
Solution2:

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet numset = new HashSet();
        for (int n : nums) {
            if (!numset.add(n)) return true;
        }
        return false;
    }
}

黑白棋 - Java

黑白棋规则：
棋盘共有8行8列共64格。开局时，棋盘正中央的4格先置放黑白相隔的4枚棋子（亦有求变化相邻放置）。通常黑子先行。双方轮流落子。只要落子和棋盘上任一枚己方的棋子在一条线上（横、直、斜线皆可）夹着对方棋子，就能将对方的这些棋子转变为我己方（翻面即可）。如果在任一位置落子都不能夹住对手的任一颗棋子，就要让对手下子。当双方皆不能下子时，游戏就结束，子多的一方胜。

参考：
http://blog.csdn.net/da_keng/article/details/47779141

Leetcode 242 - Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

做法1：

把两个string都sort好，然后比较之。
Time: O(nlogn)
Space: O(1)

这样的话答案78.41%

public class Solution {
    public boolean isAnagram(String s, String t) {
        char[] ss = s.toCharArray();
        Arrays.sort(ss);
        String sss = new String(ss);
        char[] tt = t.toCharArray();
        Arrays.sort(tt);
        String ttt = new String(tt);
        return sss.equals(ttt);
    }
}

做法2： 用一个数组存起来
似乎比sort还要慢一些, 46.32%, 8ms。

public class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        else if (s.length() == 0) return true;
        int[] numbychar = new int[256];
        int num_unique = 0;
        int num_complete = 0;
        char[] s_char = s.toCharArray();
        for (char c : s_char) {
            if (numbychar[c] == 0) num_unique++;
            ++numbychar[c];
        }
        for (int i = 0; i < t.length(); i++) {
            int c = (int) t.charAt(i);
            if (numbychar[c] == 0) return false;
            --numbychar[c];
            if (numbychar[c] == 0) {
                ++num_complete;
                if (num_complete == num_unique) {
                    return i==t.length()-1;
                }
            }
        }
        return false;
    }
}

Improve the 2nd solution: use a hashtable

import java.util.*;
public class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length()!=t.length()) return false;
        
        Hashtable 
            theTableS = new Hashtable(),
            theTableT = new Hashtable();
        for (char i:s.toCharArray()) {
            if (theTableS.containsKey(i))
                theTableS.put(i,theTableS.get(i)+1);
            else theTableS.put(i,1);
        }
        for (char i:t.toCharArray()) {
            if (theTableT.containsKey(i)) 
                theTableT.put(i,theTableT.get(i)+1);
            else theTableT.put(i,1);
        }
        return theTableT.equals(theTableS);
    }
}

Leetcode 238 - Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
O(n), 所以只能扫一遍就得到该有的信息，自然想到的是左边扫一遍右边扫一遍。
省空间的话简单，右边扫的时候直接把答案存起来。

public class Solution {
    public int[] productExceptSelf(int[] nums) {
        //keep track of product of left elements in the array
        // then scan from right to left to multiply the right elements
        int n = nums.length;
        int[] results = new int[n];
        results[0] = 1;
        for (int i = 1; i < n; i++) {
            results[i] = results[i-1] * nums[i-1];
        }
        int right = 1;
        for (int i = n-1; i >= 0; i--) {
            results[i] *= right;
            right *= nums[i];
        }
        return results;
    }
}

Graphs

Unstructured structures: sets
Hierarchy structures: Trees
Basic objects and relationship between them: Graphs

Basic objects: nodes, vertices   ...  websites
Relationship: edges, arcs, links  ...  hypelinks

Definition:
Basic objects: vertices.. V
Relationship: edges... E
Size: |V| + |E|
Directed or undirected
Weighted or unweighted
Path: a sequence of vertices and edges that depicts hopping along graph
In degree: number of edges coming to v
Out degree: number of outgoing edges from v

Adjacent matrix: (better for dense graph)
  Pro: quick add/delete edges etc.
  Con: Adding vertices (need to expand the matrix), and storing N^2 piece information.
Adjacency list: (better for sparse matrix)
  A map: vertices -> neighbors
  private Map<Integer, ArrayList<Integer>> adjListsMap
  Pro: easy (not quick) add/delete edges; easy (not quick) to add vertices; use less memory

Searching a graph:
1. DFS
  Need to keep track of visited node. - HashSet. Constant time add, remove, and find.
  Keep track of the next node to visit. - Use a stack. add and remove node.
  Keep track of the path from start to goal. - HashMap. Link each node to the node from which it was  discovered.
DFS algorithms (recursive)
DFS(S, G, visited, parents):
    if S==G return;
    for each of S's neighbors, n, not in visited set:
        add n to visited;
        add S as n's parent in the parent map;
        DFS(n, G, visited, parents);

DFS algorithms (stack)
DFS(S, G):
    Initialize: stack, visited HashSet and parent HashMap
    Push S to the stack and add to visited
    while stack is not empty:
        pop node curr from top of stack;
        if curr == G return parent map
        for each neighbor of curr, n, not in visited:
            add n to visited
            add curr as n's parent to parent map
            push n to the stack
    // if get here then there is no path

2. BFS
  Just change the to-visit stack to a queue.
BFS(S, G):
    Initialize: queue, visited HashSet and parent HashMap
    Enqueue S onto the queue and add to visited
    while queue is not empty:
        dequeue node curr from front of queue
        if curr == G return parent map
        for each of curr's neighbor, n, not in visited yet:
            add n to visited set
            add curr as n's parent in parent map
            enqueue n onto the queue
    // if get here there is no path
BFS find the shorter path than DFS.

Leetcode 73 - Edit Distance

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Naive Approach:
For word1, use insert/delete/replace to generate all strings as its children, then for each children, generate all strings etc...
But the tree will expand too fast.
Solutions:
1. DP
2. Pruning (delete the nodes that are not actual English words).

HashTable

Use HC as index to quickly query some key in the hash table.

Pro:
Quick lookup, insert and remove O(1) (on average)
Challenge:
1. Collisions: values with same hashcode
    1) Solution 1: linear probing: insert. Just put it in the next open spot.
        Has to search for subsequent space for values. May be a problem when the hash table gets full.
        Random probing is an alternative.
    2) Solution 2: separate chaining. Just keep a list at each spot.
        This solution is usually preferred. But drawbacks.
2. Resizing: resize if gets too full (70%)
    requires create a new table, new hash function, and reinsert everything.
3. Ordering data.
    Hash Table don't have order within structure.

Hash Set vs. Hash Map
1. Hash Set: java.util
    class hashset<E>
    boolean add(E e)
    boolean contains(Object o)
    Just tells you if an item is in the set. Perfect for a dictionary.

2. Hash Map: java.util
    class hashmap<K,V>
    V get(Object key)
    V put(K key, V value)
    Stores both a key and some data associated with the key.

Trie

reTRIEval

TRIE storing dictionary, will use word structure
- Not every node contains words
- Nodes can have > 2 children
- Have internal nodes that does not represent any word.

Performance vs. BST:
1. find a key:
BST: O(logn)
Trie: slightly better (since most words are not long)

Use a hashmap to store the link to the next node in trie because:
1. Use ArrayList waste a lot of space
2. Use linkedList will lose the index of some particular character.
https://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html
HashMap<Character, TrieNode> Children;
put(key, value);
get(key);

Application:
A. Autocomplete: ex. autocomplete "ea"
    1. Find the stem
    2. Do a level traversal from there (if want to generate words from shortest to longest)

Trees

Tree:
Single root;
Each node (except the root) can have only one parent;
No cycle;

Tree一般指Binary Tree.

class TreeNode{
 int value;
 TreeNode left;
 TreeNode right;
}

Binary Search Tree: for all nodes left children <= current node <= right children
Balanced: the depth of the left and right subtrees of every node differ by 1 or less

In Java, built-in Balanced BST: TreeSet.

Applications:
Expression tree such as 48 * (3 + 8)
Decision tree.
File system
If root is most important: heap tree
Organized by character frequency: huffman tree
Organized by node ordering: Search tree

Basic Operations:
A. Depth-first search (go to the path until the end 一条道走到黑)
    比如走迷宫，最好用此策略。
    1. Binary Tree Preorder Traversal
    Visit your self, then visit all your left subtree, then all your right subtree.
    2. Binary Tree Inorder Traversal
    Visit all your left subtree, visit your self, then all your subtree.
    3. Binary Tree Postorder Traversal
    Visit all your left subtree, then all your right subtree, visit yourself.
B. Breath-first search
    比如social network, find your closet path to friend D.
    4. Binary Tree Level Order Traversal
    Use a queue (linkedlist) to keep the visited node, while the queue is not empty, every time a node is visited, remove it, and add its children to the list.

C. Binary Search Tree
    1. search / find Best O(1), Worst O(n), Average O(logn), so need balancing.
    Recursion / iteration

public boolean contains(E toFind) {
  TreeNode curr = root;
  int comp;
  while (curr != null) {
   comp = toFind.compareTo(curr.getData());
   if (comp < 0)
    curr = curr.getLeft();
   else if (comp > 0)
    curr = curr.getRight();
   else
    return true;
  }
  return false;
 }

    2. insert
    Recursion / iteration

public boolean insert(E toInsert) {
  TreeNode curr = root;
  int comp = toInsert.compareTo(curr.getData());
  while (comp < 0 && curr.getLeft() != null ||
    comp > 0 && curr.getRight() != null) {
   if (comp < 0) curr = curr.getLeft();
   else curr = curr.getRight();
   comp = toInsert.compareTo(curr.getData());
  }
  if (comp < 0)
   curr.addLeftChild(toInsert);
  else if (comp > 0)
   curr.addRightChild(toInsert);
  else return false;
  return true;
 }

    3. remove
    Remove leaf or a node with only one child is easy. If remove a node with two children, then find the smallest from the right subtree and replace the value with the value.

 Preorder transersal:
1. Recursive

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List preorderTraversal(TreeNode root) {
        List nodes = new ArrayList();
        if (root == null) {
            return nodes;
        }
        nodes.add(root.val);
        nodes.addAll(preorderTraversal(root.left));
        nodes.addAll(preorderTraversal(root.right));
        return nodes;
    }
}

2. Iteration (using a stack)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List preorderTraversal(TreeNode root) {
        List nodes = new ArrayList();
        if (root == null) return nodes;
        Stack nodetovisit = new Stack();
        nodetovisit.push(root);
        while(!nodetovisit.empty()) {
            TreeNode node = nodetovisit.pop();
            nodes.add(node.val);
            if (node.right != null) nodetovisit.push(node.right);
            if (node.left != null) nodetovisit.push(node.left);
        }
        return nodes;
    }
}

Inorder traversal:
1. Recursive

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List inorderTraversal(TreeNode root) {
        List list = new ArrayList();
        if (root == null) return list;
        list.addAll(inorderTraversal(root.left));
        list.add(root.val);
        list.addAll(inorderTraversal(root.right));
        return list;
    }
}

2. Iteration

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List inorderTraversal(TreeNode root) {
        List list = new ArrayList();
        Stack stack = new Stack();
        if (root == null) return list;
        TreeNode p = root;
        while (!stack.empty() || p != null) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            } else {
                TreeNode t = stack.pop();
                list.add(t.val);
                p = t.right;
            }
        }
        return list;
    }
}

Postorder traversal:
1. Recursive

public class Solution {
    public List postorderTraversal(TreeNode root) {
        // trivial recursion
        List list = new ArrayList();
        if (root == null) return list;
        list.addAll(postorderTraversal(root.left));
        list.addAll(postorderTraversal(root.right));
        list.add(root.val);
        return list;
    }
}

2. Iteration

Level Order Traversal:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List> levelOrder(TreeNode root) {
        // use two queue, current and next level
        List> lists = new ArrayList>();
        List list = new ArrayList();
        if (root == null) return lists;
        Queue current = new LinkedList();
        Queue next = new LinkedList();
        current.offer(root);
        while (!current.isEmpty()) {
            TreeNode node = current.poll();
            list.add(node.val);
            if (node.left != null) next.offer(node.left);
            if (node.right != null) next.offer(node.right);
            if (current.isEmpty()) {
                lists.add(list);
                Queue temp = current;
                current = next;
                next = temp;
                list = new ArrayList();
            }
        }
        return lists;
    }
}

Problems:
Leetcode 144 - Binary Tree Preorder Transversal
Leetcode 94 - Binary Tree Inorder Traversal

Testing - Java, JUnit

To increase confidence:
- Be critical to algorithms/code
- Consider/test corner cases
- Attempt to formally reason about correctness
- Create automated test cases

Test-driven development: Write test -> Write code -> Test

Unit test: testing method
Then integration test: e.g. test your method with database connection etc.

JUnit: lightweight unit test platform
Components:
1. Code to setup tests
2. Code to perform tests
3. Code to cleanup tests

@Before
setup: is run before each test to initialize variables and objects

@BeforeClass
setupClass: is run only once before the class to initialized objects

@Test
test<feature>
Denotes a method to test <feature>
Two useful methods:
fail

try {
   emptyList.get(0);
   fail("Check out of bounds");
  }
  catch (IndexOutOfBoundsException e) {
   
  }

emptyList.get(0) should throw an exception, if it doesn't, we call the fail method.

assertEquals

assertEquals("Check first", "A", shortList.get(0));

assertEquals enforces that shortList.get(0) is "A". Otherwise, throws an error.

@After
tearDown: can be useful if your test constructed something which needs to be properly torn down (e.g. a database).

@AfterClass
tearDownClass: if your setupClass constructed something which needs to be properly torn down.

Generics and Exceptions - Java

Generics:

class ListNode {
    ListNode next;
    ListNode prev;
    E data;}

E: parameterized type

Exceptions:
throws exceptions to indicate fatal problems.

Checked exception must be declared.

public class RememberLast {
public T add(T element) throws NullPointerException { //Not required since NPE is unchecked, but OK
if (element == null) {
throw new NullPointerException("T cannot store null pointers");
}
...
}
}

Benchmarking - Java

Use Java Timing libraries.

java.lang

static long     nanoTime() - Returns the current value of the running JVM's high-resolution time source, in nanoseconds.

Merge sort - Java

Basic algorithm:
1. If list has one element, return;
2. Divide list in half
3. Sort first half
    Sort second half    (use recursion)
4. Merge sorted lists.

Best = Worst = O(nlogn)

Quick sort best = average = O(nlogn), worst = O(n^2)

Regular Expression

"a*" - zero or more a
"a+" - 1 or more a's
"[a-f]" - Any character between a and f
"[^a-cz]" - Any character which is not between a and c, and not z
"[abc]+" - 1 or more of a, b or c in a row
"abc" - character abc in a row
"a|b" - Character a or character b

Java:
java.util.regex
java.util.regex.Matcher;
java.util.regex.Pattern;

protected List getTokens(String pattern)
 {
  ArrayList tokens = new ArrayList();
  Pattern tokSplitter = Pattern.compile(pattern);
  Matcher m = tokSplitter.matcher(text);
  
  while (m.find()) {
   tokens.add(m.group());
  }
  
  return tokens;
 }

Python projects

Schema

Geocoding:

PageRank:

Gmane:

Insertion sorting - Java

Insertion sorting:

 public static void insertionSort( int[] vals ) {
  int currInd;
  for (int pos=1; pos < vals.length; pos++) {
   currInd = pos;
   while (currInd > 0 && vals[currInd] < vals[currInd-1] ) {
    swap(vals, currInd, currInd-1);
    currInd--;
   }
  }
 }

Best: O(n)
Worst: O(n^2)

Java Built-in Sorting

Mergesort

import java.util.*;

public class MyBuiltInSortingTest {
    public static void main (String[] args) {
        Random random = new Random();
        List numsToSort = new ArrayList();
        
        for (int i=0; i < 5; i++) {
            numsToSort.add( random.nextInt(100) );
        }
        
        Collection.sort(numsToSort);
        System.out.println("New array after builtin sort: " + numsToSort.toString());
    }
}

Seletion Sort - Java

Steps:
Find smallest element, swap it with element at location 0;
Find next smallest element, swap it with element at location 1;
etc.

public static void selectionSort( int[] vals ) {
    int indexmin;

    for (int i = 0; i < vals.length-1; i++) {
        indexmin = i;
        for (int j = i+1; j < vals.length-2; j++) {
            if (vals[j] < vals[indexmin]) { indexmin = j; }
        }
        swap( vals, indexmin, j );
    }
}

Correctness:
Left array is always sorted.

Performance:
Time: O(n^2)
Space: O(1)

Note:
Not sensitive to already almost sorted array (takes same amount of time)
So Best = Worst = O(n^2)