Perl and Common Gateway Interface (CGI)

http://www.perl.com/pub/2000/10/begperl1.html

1. The difference between single quotes and double quotes is that single quotes mean that their contents should be takenliterally, while double quotes mean that their contents should be interpreted. For example, the character sequence \n is a newline character when it appears in a string with double quotes, but is literally the two characters, backslash and n, when it appears in single quotes. 

print "This string\nshows up on two lines."; 

print 'This string \n shows up on only one.';

2. the plus sign adds numbers and the period puts strings together.

CGI
http://en.wikipedia.org/wiki/Common_Gateway_Interface

Common Gateway Interface (CGI) is a standard method used to generate dynamic content on web pages and web applications. CGI, when implemented on a web server, provides an interface between the web server and programs that generate the web content. These programs are known as CGI scripts or simply CGIs; they are usually written in ascripting language.

LeetCode:Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

这个题很早就做过了，不难，不过小细节很多，最后还是调试通过的，汗！
注意点：用一个变量记录node个数，当n==number of nodes,时删除head

	public ListNode removeNthFromEnd(ListNode head, int n) {
	if(head==null) return head;
	ListNode firstNode=head, prv=head, secNode=head;
	if(n==1 && head.next == null) return null;
	int i = 0, num=0;
	while(firstNode!=null){
	num++;
	firstNode = firstNode.next;
	if(i>=n){
	prv = secNode;
	secNode = secNode.next;
	}
	i++;
	}
	if(num==n)
	head = head.next;
	else
	prv.next = secNode.next;
	return head;
	}

view raw gistfile1.java hosted with ❤ by GitHub

LeetCode: Gray Code

he gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Solution:

Got a vague impression of this problem. Must have learned something about it before.
After checking out the definition of Gray Code, as shown here how to recursively get Kth gray code from (K-1)th one:

2-bit list:	00, 01, 11, 10
Reflected:		10, 11, 01, 00
Prefix old entries with 0:	000, 001, 011, 010,
Prefix new entries with 1:		110, 111, 101, 100
Concatenated:	000, 001, 011, 010,	110, 111, 101, 100

we can get 2th Gray Code for 0,1 by
0 1 (1 0)--> 00 01 11 10
See the code:

Note: Math.pow(2, i) == 1<<i

	public ArrayList<Integer> grayCode(int n) {
	if(n<0) return null;
	ArrayList<Integer> ret = new ArrayList<Integer>();
	if(n==0) {
	ret.add(0);
	return ret;
	}
	ret.add(0);
	ret.add(1);
	for(int i =2; i<=n; i++){
	for(int j=(1<<i-1)-1; j>=0; j--)
	{
	int m = ret.get(j);
	ret.add(m|1<<i-1);
	}
	}
	return ret;
	}

view raw gistfile1.java hosted with ❤ by GitHub

C++: calling base class constructors

	#include <iostream>
	#include <stdio.h>
	using namespace std;
	// Base class
	class Shape
	{
	public:
	void setWidth(int w)
	{
	width = w;
	}
	void setHeight(int h)
	{
	height = h;
	}
	Shape()
	{
	printf("creating shape \n");
	}
	Shape(int h,int w)
	{
	height = h;
	width = w;
	printf("creatig shape with attributes\n");
	}
	protected:
	int width;
	int height;
	};
	// Derived class
	class Rectangle: public Shape
	{
	public:
	int getArea()
	{
	return (width * height);
	}
	Rectangle()
	{
	printf("creating rectangle \n");
	}
	Rectangle(int h,int w)
	{
	printf("creating rectangle with attributes \n");
	height = h;
	width = w;
	}
	};
	int main(void)
	{
	Rectangle Rect;
	Rect.setWidth(5);
	Rect.setHeight(7);
	Rectangle *square = new Rectangle(5,5);
	// Print the area of the object.
	cout << "Total area: " << Rect.getArea() << endl;
	return 0;
	}
	Output:
	creating shape
	creating rectangle
	creating shape
	creating rectangle with attributes
	Total area: 35

view raw gistfile1.cpp hosted with ❤ by GitHub

The default class constructor is called unless you explicitly call another constructor in the derived class. the language specifies this.

Rectangle(int h,int w):
   Shape(h,w)
  {...}

Polymorphism vs Overriding vs Overloading

Summarize the relationship between polymorphism with overriding and overloading.

Polymorphism is the ability of a class instance to behave as if it were an instance of another class in its inheritance tree, most often one of its ancestor classes. For example, in Java all classes inherit from Object. Therefore, you can create a variable of type Object and assign to it an instance of any class. It always involves class inheritance and method overriding.

An override is a type of function which occurs in a class which inherits from another class. An override function "replaces" a function inherited from the base class, but does so in such a way that it is called even when an instance of its class is pretending to be a different type through polymorphism. Referring to the previous example, you could define your own class and override the toString() function. Because this function is inherited from Object, it will still be available if you copy an instance of this class into an Object-type variable. Normally, if you call toString() on your class while it is pretending to be an Object, the version of toString which will actually fire is the one defined on Object itself. However, because the function is an override, the definition of toString() from your class is used even when the class instance's true type is hidden behind polymorphism.

Overloading is the action of defining multiple methods with the same name, but with different parameters. It can be regarded as one way of static polymorphism. Template is another way.  Static polymorphism is at compile time. Static polymorphism is in fact involves binding of functions based on number or type of arguments and is also known as parametric polymorphism.

LeetCode: Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

很简单的一道题，没有啥要说的，直接accepted

	public int[] plusOne(int[] digits) {
	if(digits == null || digits.length == 0) return digits;
	for(int i=digits.length-1; i>=0; i--){
	if(digits[i]<9){
	digits[i]++;
	return digits;
	}
	else{
	digits[i]=0;
	}
	}
	int[] ret = new int[digits.length+1];
	ret[0]=1;
	for(int i=0; i<digits.length; i++){
	ret[i+1] = digits[i];
	}
	return ret;
	}

view raw gistfile1.java hosted with ❤ by GitHub

LeetCode: Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Solution:
这道题本身不难，关键是逆向思维，先从四个边界开始找‘O’, 找到后换成'D', 用一个queue递归扫描所有连通区域，最后凡是没有没有变成D的O都是被X包围的；注意点是二维数组的操作，code如下：

	public class Solution {
	class Element{
	int x;
	int y;
	Element(int x, int y){
	this.x = x;
	this.y = y;
	}
	}
	public void solve(char[][] board) {
	if(board == null||board.length==0) return;
	int row = board.length;
	int col = board[0].length;
	Queue<Element> qu = new LinkedList<Element>();
	for(int i=0; i<row; i++){
	if(board[i][0] == 'O')
	qu.add(new Element(i, 0));
	if(board[i][col-1] == 'O')
	qu.add(new Element(i, col-1));
	}
	for(int i=0; i<col; i++){
	if(board[0][i] == 'O')
	qu.add(new Element(0, i));
	if(board[row-1][i] == 'O')
	qu.add(new Element(row-1, i));
	}
	while(!qu.isEmpty()){
	Element e = qu.remove();
	board[e.x][e.y] = 'd';
	if(e.x>0 && board[e.x-1][e.y]=='O')
	qu.add(new Element(e.x-1, e.y));
	if(e.x<row-1 && board[e.x+1][e.y]=='O')
	qu.add(new Element(e.x+1, e.y));
	if(e.y>0 && board[e.x][e.y-1]=='O')
	qu.add(new Element(e.x, e.y-1));
	if(e.y<col-1 && board[e.x][e.y+1]=='O')
	qu.add(new Element(e.x, e.y+1));
	}
	for(int i=0; i<row; i++)
	for(int j=0; j<col; j++){
	if(board[i][j] == 'O')
	board[i][j]='X';
	if(board[i][j] == 'd')
	board[i][j]='O';
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

LeetCode:ZigZag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

n=4
P              I              N
A         L  S         I   G
Y   A       H    R
P              I

N=5
P               H
A          S  I
Y      I       R
P   L          I      G
A              N

The key points of this problem is to get the fact that:

• zigSize=2nRows-2
• In each zig, the index of the next element in between (in green) is index + (nRows-i-1)*2. For example, whenRow = 5, the current row=3, index(L) = index(P) + (5-3-1)*2=3+2=5;

	class Solution {
	public:
	string convert(string s, int nRows) {
	if(s.size()<=0) return s;
	if(nRows<=1) return s;
	string ret;
	for(int i=0; i<nRows; i++){
	for(int j=0, index=i; index<s.size(); j++, index = (2*nRows-2)*j+i){
	ret.append(1, s[index]);
	if(i==0 || i==nRows-1) continue;
	index = index + (nRows-i-1)*2;
	if(index<s.size())
	ret.append(1, s[index]);
	}
	}
	return ret;
	}
	};

view raw gistfile1.java hosted with ❤ by GitHub

LeetCode: Word Break

Solution1:
My DP solution. DPB[i]=true means substring s.substr(0,i) is breakable. so the solution is to find DPB[len].

	public class Solution {
	public boolean wordBreak(String s, Set<String> dict) {
	boolean [] dpb = new boolean[s.length()+1]; //initialized to be false by the compiler
	dpb[0] = true;
	for(int i =0; i < s.length(); i++){
	for(int j=i; j>=0; j--){
	if(dpb[j] == true){
	String tempStr = s.substring(j, i+1);
	for(String str : dict){
	if(str.equals(tempStr))
	dpb[i+1] = true;
	}
	}
	}
	}
	return dpb[s.length()];
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

dp[i] has the boolean value that means if string[i : n] can be partitioned according to our dictionary. Hence dp[len] represents the empty string and dp[0] is the answer we are looking for.

For each iteration in the inner for loop, we add a new cut at index j to string[i : n], in whcih string[i : j] has never checked before but string[j + 1 : n](result is in dp[j + 1]) has been known since the previous iteration in outer loop.

	bool wordBreak(string s, unordered_set<string> &dict) {
	int len = s.length();
	if(len==0) return true;
	if((len == 1) &&(dict.find(s)!=dict.end()))
	return true;
	else if(len == 1)
	return false;
	int *DPB = new int[len+1]; //DPB[i]=true: substr (start from 0, length=i) breakable, find DPB[len]
	for(int i=0; i<=len; i++)
	DPB[i] = false;
	DPB[0] = true;
	DPB[1] = (dict.find(s.substr(0,1)) != dict.end());
	for(int i=1; i<s.length(); i++)
	{
	for(int j=i; j>=0; j--)
	{
	string sub = s.substr(j, i-j+1);
	if((dict.find(sub)!=dict.end()) && DPB[j])
	{
	DPB[i+1]=true;
	break;
	}
	}
	}
	bool res = DPB[len];
	delete []DPB;
	return res;
	}
	Solution2
	class Solution {
	public:
	bool wordBreak(string s, unordered_set<string> &dict) {
	int len = s.length();
	vector<bool> dp(len + 1,false);
	dp[len] = true;
	for (int i = len - 1; i >= 0; i--) {
	for (int j = i; j < len; j++) {
	string str = s.substr(i,j - i + 1);
	if (dict.find(str) != dict.end() && dp[j + 1]) {
	dp[i] = true;
	break;
	}
	}
	}
	return dp[0];
	}
	};

view raw gistfile1.cpp hosted with ❤ by GitHub

dynamic linking VS static linking

A static library is meant to be combined with your code into a single executable file by a linker.

A dynamic library is meant to be loaded by the operating system after the main executable has been loaded, and the linking of the symbol addresses will be done by the OS at that time. This may be done automatically based on dependency information in the executable, or it may be done explicitly by the program. This is called "dynamic linking" because the library may change at any point before the OS has loaded it.

How to skip unwanted input string in ANTRL grammar

Question: I want to build a parser for analyzing a large input file, but I don’t need the entire input file, only some parts of it.

For exmaple, the input file may look like this:

bla bla bla bla bla ...

EVENT: e1
type: t1
version: 1
additional-info: abc

EVENT: e2
type: t2
version: 1
uninteresting-info: def

blu blu blu blu blu ...

From this file, all I want is to have a map of event to type (e1=>t1, e2=>t2). All other information is of no interest for me.


How can I build a simple ANTLR grammar that does this?


Anwer:


You can do that by introducing a boolean flag inside your lexer that keeps track whether an event- or type-keyword has been encountered. If it has been encountered, the lexer should not skip the word, all other words should be skipped.


A small demo:

	grammar T;
	@lexer::members {
	private boolean ignoreWord = true;
	}
	parse:
	event* EOF;
	event:
	Event w1=Word Type w2=Word
	{System.out.println(“event=” + w1.text+“,type=”+w2.text);};
	Event:
	'EVENT:' {ignoreWord=false;};
	Type:
	'type:' {ignoreWord=false;};
	Word:
	('a'..'z' | 'A'..'Z' | '0'..'9')+ {if(ignoreWord) skip();};
	NewLine:
	('\r'? '\n' | '\r') {ignoreWord=true; skip();};
	Other:
	.{skip();};

view raw gistfile1.g4 hosted with ❤ by GitHub

You can test the parser with the following class:

import org.antlr.runtime.*;

public class Main {
  public static void main(String[] args) throws Exception {
    String src = 
        "bla bla bla bla bla ...  \n" +
        "                         \n" +
        "prEVENT: ...             \n" +
        "EVENTs: ...              \n" +
        "                         \n" +
        "EVENT: e1                \n" +
        "type: t1                 \n" +
        "version: 1               \n" +
        "additional-info: abc     \n" +
        "                         \n" +
        "EVENT: e2                \n" +
        "type: t2                 \n" +
        "version: 1               \n" +
        "uninteresting-info: def  \n" +
        "                         \n" +
        "blu blu blu blu blu ...  \n";
    TLexer lexer = new TLexer(new ANTLRStringStream(src));
    TParser parser = new TParser(new CommonTokenStream(lexer));
    parser.parse();
  }
}

which will produce the following output:

java -cp antlr-3.3.jar org.antlr.Tool T.g
javac -cp antlr-3.3.jar *.java
java -cp .:antlr-3.3.jar Main

event=e1, type=t1
event=e2, type=t2

From page at http://stackoverflow.com/questions/8313722/skipping-parts-of-the-input-file-in-antlr
string literal


Also, your string rule would probably be better of looking like this:


STRING_LITERAL : ‘”’ (~(‘”’ | ‘\’ | ‘\r’ | ‘\n’) | ‘\’ (‘”’ | ‘\’))* ‘”’;

In other words, the contents of your string is zero or more:


any char other than a quote, backslash or line break: ~(‘”’ | ‘\’ | ‘\r’ | ‘\n’)

or


an escaped quote or backslash ‘\’ (‘”’ | ‘\’)


OR


STRING : ‘”’ (options{greedy=false;}:( ~(‘\’|’”’) | (‘\’ ‘”’)))* ‘”’;

Antlr + StringTemplate

• Antlrworks is not good tool. It does not support semantic predicates.
• The documentation for using Antlr together with StringTemplate is not good enough.
• There are many ways to improve error reporting. A quick fix would be to override emitErrorMessage(String message) in the parser class and simply throw an exception with the provided message:

	grammar T;
	@members {
	@Override
	public void emitErrorMessage(String message) {
	throw new RuntimeException(message);
	}
	}
	definition
	: '(' 'define' ( '(' variable def_formals ')' body ')'
	| variable expression ')'
	)
	;
	def_formals
	: variable* ('.' variable)?
	;
	body
	: ((definition)=> definition)* expression+
	;
	expression
	: INT
	;
	variable
	: ID
	;
	ID : 'a'..'z'+;
	INT : '0'..'9';
	SPACE : ' ' {skip();};

view raw gistfile1.g4 hosted with ❤ by GitHub

which you can test with the class:

	import org.antlr.runtime.*;
	public class Main {
	public static void main(String[] args) {
	String[] tests = {
	"(define x 5)",
	"(define x 5))",
	"(define x)",
	"(define)"
	};
	for(String input : tests) {
	TLexer lexer = new TLexer(new ANTLRStringStream(input));
	TParser parser = new TParser(new CommonTokenStream(lexer));
	System.out.println("\nParsing : " + input);
	try {
	parser.definition();
	} catch(Exception e) {
	System.out.println(" exception -> " + e.getMessage());
	}
	}
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

After running the class above, you will see the following:

bart@hades:~/Programming/ANTLR/Demos/T$ java -cp antlr-3.3.jar org.antlr.Tool T.g

bart@hades:~/Programming/ANTLR/Demos/T$ javac -cp antlr-3.3.jar *.java

bart@hades:~/Programming/ANTLR/Demos/T$ java -cp .:antlr-3.3.jar Main

Parsing : (define x 5)
Parsing : (define x 5))
Parsing : (define x)
exception -> line 1:9 missing INT at ')'
Parsing : (define)
exception -> line 1:7 no viable alternative at input ')'

As you can see, the input (define x 5)) produces no exception! That is because the lexer has no problems with it (they're all valid tokens) and the parser is simply instructed to consume the definition rule:

definition

: '(' 'define' ( '(' variable def_formals ')' body ')'

| variable expression ')'

) ;
which it does. If you wanted an error because of the dangling ')', then you'd have the add the EOF token at the end of the rule:

definition

: '(' 'define' ( '(' variable def_formals ')' body ')'

| variable expression ')'

)

EOF;

LeetCode:Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Solution:
今天做的两道题都是关于双指针问题
刚开始尝试用DP，无果，后来参考解释，有了这个思路
这个题的解法稍微容易一些，用一个数组保存已经出现的字符信息，下标是某个letter的ASCII码值
重点是发现重复字符后的处理：1.比较是否找到更长的符合条件的字符串，2，suppose, s[j]==s[i] (j>i), then set letterExist[start...i-1] to false, the next potential substring starts from i+1; 下面这个图不错，转过来

Code:

	public int lengthOfLongestSubstring(String s) {
	if(s==null||s.length()==0) return 0;
	boolean[] letterExist=new boolean[256];
	int start=0;
	int maxLen=0;
	int i=0;
	for(i=0; i<s.length(); i++){
	if(letterExist[s.charAt(i)]){//find a repeated char at i
	if(i-start>maxLen)
	maxLen = i-start;
	while(s.charAt(start)!=s.charAt(i)){
	//clear the indicator in letterExist from start to the first-time appearance of the found repeated character
	letterExist[s.charAt(start)] = false;
	start++;
	}
	start++;//from next one
	}
	else{
	letterExist[s.charAt(i)] = true;
	}
	}
	if(i==s.length() && i-start>maxLen)
	maxLen = i-start;
	return maxLen;
	}

view raw gistfile1.java hosted with ❤ by GitHub

第一百个题目完成！ 继续加油

LeetCode: Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"

Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

Solution:

这道题挺费劲的

双指针，动态维护一个区间。尾指针不断往后扫，当扫到有一个窗口包含了所有T的字符后，然后再收缩头指针，直到不能再收缩为止。最后记录所有可能的情况中窗口最小的

用两个数组，一个保存T的中字符出现的个数expectCount['A']=1，另个保存目前为止在S中找到的T中字符的个数foundCount['A']=2

参考图解

	public String minWindow(String S, String T) {
	if(S==null||S.length()==0) return "";
	if(S.length()<T.length()) return "";
	int[] foundCount=new int[128];
	int[] expectCount=new int[128];
	int count=0;
	for(int i=0; i<T.length(); i++){
	expectCount[T.charAt(i)]++;
	}
	int minV = Integer.MAX_VALUE, minStart=0;
	int start=0, end =0;
	for(int i=0; i<S.length();i++){
	if(expectCount[S.charAt(i)]==0) continue;//skip characters not in T
	if(expectCount[S.charAt(i)]>0){//this char is part of T
	if(foundCount[S.charAt(i)] < expectCount[S.charAt(i)]){
	count++;
	}
	foundCount[S.charAt(i)]++;
	}
	if(count == T.length()){
	//from start to i, all letters in T have been found in S.substring(start, i)
	end=i;
	while(foundCount[S.charAt(start)] > expectCount[S.charAt(start)] || expectCount[S.charAt(start)]==0){
	if(foundCount[S.charAt(start)] > expectCount[S.charAt(start)])
	foundCount[S.charAt(start)]--;
	start++;
	}
	if(minV > (end-start+1)){
	minV = end-start+1;
	minStart = start;
	}
	}
	}
	if(minV == Integer.MIN_VALUE) return "";
	else return S.substring(minStart, minStart+minV);
	}

view raw gistfile1.java hosted with ❤ by GitHub

LeetCode: 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.

Solution:

Key points: find a way to pass the value of the grand parent. Got the idea from here.
Can also be solved by in-order traversing the BST and then check whether collected values are in the ascending order.

	//in Java
	public boolean isValidBST(TreeNode root) {
	if(root == null) return true;
	return isValidBSTRec(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
	}
	public boolean isValidBSTRec(TreeNode root, int min, int max){
	if(root == null) return true;
	if(root.val>min && root.val<max && isValidBSTRec(root.left, min, root.val)&&isValidBSTRec(root.right, root.val, max))
	return true;
	else
	return false;
	}

view raw gistfile1.java hosted with ❤ by GitHub

LeetCode: Binary Search Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

This is an easy one. Solved it with two solutions

	//iterative solution
	public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
	ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
	if(root == null) return res;
	Queue<TreeNode> que = new LinkedList<TreeNode>();
	TreeNode dumbNode = new TreeNode(0);
	ArrayList<Integer> al = new ArrayList<Integer>();
	que.add(root);
	que.add(dumbNode);
	while(!que.isEmpty()){
	TreeNode node = que.remove();
	if(node == dumbNode){//end of a level
	res.add(al);
	if(!que.isEmpty()){
	que.add(dumbNode);
	al = new ArrayList<Integer>();
	}
	}
	else{
	al.add(node.val);
	if(node.left != null){
	que.add(node.left);
	}
	if(node.right != null){
	que.add(node.right);
	}
	}
	}
	return res;
	}
	//recursive solution
	public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
	ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
	if(root == null) return res;
	levelOrderRec(res, root, 0);
	return res;
	}
	public void levelOrderRec(ArrayList<ArrayList<Integer>> res, TreeNode root, int levelOrder) {
	if(root == null) return;
	int len = res.size();
	if(levelOrder==len){
	ArrayList<Integer> al= new ArrayList<Integer>();
	al.add(root.val);
	res.add(al);
	}
	else if(levelOrder < len){
	res.get(levelOrder).add(root.val);
	}
	levelOrderRec(res, root.left, levelOrder+1);
	levelOrderRec(res, root.right, levelOrder+1);
	}

view raw gistfile1.java hosted with ❤ by GitHub

Good Books and Resources

More Effective C++. pdf available at:
http://proquestcombo.safaribooksonline.com/9780321545190

Effective Java at:
http://proquestcombo.safaribooksonline.com/0-201-31005-8

Internal Reference:
https://docs.google.com/spreadsheet/ccc?key=0AlkacookxMZJdDdhamJPbDdwYWhlU2tqYWJ6RkJGa2c#gid=0 



Tips for Design Problems:

In an interview setting when some asks design questions, you should have a conversation in which you demonstrate an ability to think creatively, understand design trade-offs, and attack unfamiliar problems. You should schetch key data structures and algorithms, as well as the technology stack(pl, libraries, OS, hardware, and services) that you would use to solve the problem. Some specific things to keep in mind are implementation time, scalability, testability, security, and internationalization.

LeetCode: Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactlyL characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

Solution:
The idea is not difficult at all, but caution needs to be exercised when dealing with corner cases. See the code below:

	public ArrayList<String> fullJustify(String[] words, int L) {
	ArrayList<String> res = new ArrayList<String>();
	int numWords = 0;
	String str = "";
	if(L<=0 || words.length <=0){
	res.add(str);
	return res;
	}
	for(int i=0; i<words.length; i++){
	if(str.length()+ words[i].length()>L){
	//if adding current word, the length will exceed, so justify what have been collected
	res.add(justify(words, str, numWords, i, L));
	i--;
	str = "";
	numWords=0;
	}
	else if(str.length()+ words[i].length()==L){
	//if adding current word, the length will be exactly L. Add the word and a valid line
	str += words[i];
	res.add(str);
	str = "";
	numWords=0;
	}
	else{//adding a more word
	numWords++;
	if(i == words.length-1){//if current word is the last word, get the last line
	str += words[i];
	for(int j=str.length(); j<L; j++){//pad the rest with spaces
	str +=" ";
	}
	res.add(str);
	}
	else str += words[i] + " ";
	}
	}
	return res;
	}
	//note A[curIndex] is not included in this line
	public String justify(String[] words, String str, int numWords, int curIndex, int L) {
	int totalCharLen =0;
	int totalSpaceLen =0;
	int[] numSpace = new int[numWords-1];//the number of spaces is less than that of words by 1
	int aveNum = 0;
	String ret = "";
	char[] cs = new char[L];
	if(numWords == 1){//only one word in the whole line
	for(int i=0; i<L; i++){
	if(i<words[curIndex-1].length())
	cs[i] = words[curIndex-1].charAt(i);
	else
	cs[i] = ' ';
	}
	ret = String.valueOf(cs);
	return ret;
	}
	//more than one word in the line, deal with the spaces
	for(int i=1; i<=numWords; i++){
	//get the total number of characters in the line
	totalCharLen +=words[curIndex-i].length();
	}
	//get the total number of sapces in the line
	totalSpaceLen = L-totalCharLen;
	//get the average number of sapces between two words
	aveNum = totalSpaceLen/(numWords-1);
	for(int i=0; i<numWords-1; i++){
	numSpace[i] = aveNum;
	// the empty slots on the left will be assigned more spaces than the slots on the right
	if(i<totalSpaceLen%(numWords-1)) numSpace[i]++;
	}
	//pad spaces
	String spaces="";
	for(int i=1; i<=aveNum; i++) {
	spaces +=" ";
	}
	int n = numWords;
	int j=0;
	while(n>1){
	ret += words[curIndex-n];
	ret += spaces;
	if(j<(numWords-1)&&numSpace[j] >aveNum)
	ret +=" ";
	n--;
	j++;
	}
	ret += words[curIndex-1];
	return ret;
	}

view raw gistfile1.java hosted with ❤ by GitHub

LeetCode: Jump Game I && II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Solution

At first glance, the problem can be solved with recursion or BFS. However, both solutions got the TLE error. Apparently, the intended solution should have less time complexity.

Key point: use maxCover to indicate the maximum index that current index can reach. Update the value of maxCover correspondingly.

	//O(n) solution
	public boolean canJump(int[] A) {
	if(A==null) return false;
	if(A.length == 0) return true;
	int maxCover =0;
	for(int i=0; i<=maxCover&&i<A.length; i++){//i<=maxCover is essential
	maxCover = Math.max(maxCover, A[i]+i);
	if(maxCover >= A.length-1) return true;
	}
	return false;
	}
	//BFS
	public boolean canJump(int[] A) {
	if(A==null) return false;
	if(A.length == 0) return true;
	Queue<Integer> que = new LinkedList<Integer>();
	HashSet<Integer> set = new HashSet<Integer>();
	que.add(0);
	set.add(0);
	while(!que.isEmpty()){
	int id = que.poll();
	int maxJump = A[id];
	if(id+maxJump>=A.length-1) return true;
	else{
	for(int i=1; i<=maxJump; i++){
	if(!set.contains(id+i)){
	que.add(id+i);
	set.add(id+i);
	}
	}
	}
	}
	return false;
	}
	//Recursion DFS
	public boolean canJump(int[] A) {
	if(A==null) return false;
	if(A.length == 0) return true;
	return dfs(A, 0);
	}
	public boolean dfs(int[] A, int id) {
	boolean res = false;
	if(id>=A.length) return false;
	int maxJump = A[id];
	if(id+maxJump>=A.length-1) return true;
	else{
	for(int i=1; i<=maxJump; i++){
	res |= dfs(A, id+i);
	}
	}
	return res;
	}

view raw gistfile1.java hosted with ❤ by GitHub

For Jump Game II. Tried BFS first, got TLE error. Then figured out the right answer based on the solution of Jump Game I. Key point: use a tempoary variable tempCover to get the largest A[i]+i  from all the indices within current maxCover.

	public int jump(int[] A) {
	int minStep = 0;
	if(A==null) return minStep;
	if(A.length == 0 ||A.length == 1) return minStep;
	int maxCover =0;
	int tempCover =0;
	for(int i=0; i<=maxCover&&i<A.length; i++){
	if(tempCover<maxCover)
	tempCover = maxCover;
	if(tempCover < A[i]+i){
	tempCover = A[i]+i;
	}
	if(tempCover >= A.length-1) return ++minStep;
	if(i==maxCover){
	maxCover = tempCover;
	minStep++;
	}
	}
	return minStep;
	}
	//BFS TLE
	public int jump(int[] A) {
	int minStep=0;
	if(A==null) return minStep;
	if(A.length == 0) return minStep;
	Queue<Integer> que = new LinkedList<Integer>();
	HashSet<Integer> set = new HashSet<Integer>();
	que.add(0);
	que.add(-1);
	set.add(0);
	while(!que.isEmpty()){
	int id = que.poll();
	if(id == -1){
	que.add(-1);
	minStep++;
	continue;
	}
	int maxJump = A[id];
	if(id+maxJump>=A.length-1) return minStep;
	else{
	for(int i=1; i<=maxJump; i++){
	if(!set.contains(id+i)){
	que.add(id+i);
	set.add(id+i);
	}
	}
	}
	}
	return minStep;
	}

view raw gistfile1.java hosted with ❤ by GitHub

LeetCode: Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.

这个题让我做的有点儿恶心了

算法本身不难，瞬间找到solution: DFS recursion，题目要求有些变态， the value of a node can be positive, 0 and negative. 

Key points:

•  Use a member variable maxSum. If c++, can use " int maxPathSumRe(TreeNode *root, int &max)"
•  return value should be Maximum(left, right) + curVal

 Code  

	public class Solution {
	int maxSum;
	public int maxPathSum(TreeNode root) {
	if(root == null) return 0;
	if(root.left == null && root.right == null) return root.val;
	maxSum = root.val;
	maxPathSumRe(root);
	return maxSum;
	}
	public int maxPathSumRe(TreeNode root){
	if(root == null) return 0;
	// if(root.left == null && root.right == null) return root.val;
	// if don't comment out this statement, tons of conditions should be considered. it's like a nightmare.
	int rightVal = maxPathSumRe(root.right);
	int leftVal = maxPathSumRe(root.left);
	int curVal = root.val;
	if(rightVal>0) curVal +=rightVal;
	if(leftVal>0) curVal +=leftVal;
	maxSum = Math.max(maxSum, curVal);
	/*
	if(rightVal <=0){
	if(leftVal <=0){
	maxSum = Math.max(maxSum, root.val);
	}
	else{
	maxSum = Math.max(maxSum, leftVal+root.val);
	}
	}
	else{
	if(leftVal <=0){
	maxSum = Math.max(maxSum, rightVal+root.val);
	}
	else{
	maxSum = Math.max(maxSum, rightVal+leftVal+root.val);
	}
	}
	*/
	int maxChild = Math.max(rightVal, leftVal);
	if(maxChild <= 0 ) return root.val;//discard children nodes
	else return maxChild + root.val;
	}
	}

view raw gistfile1.java hosted with ❤ by GitHub

New Techniques

Document Object Model (DOM)

The Document Object Model (DOM) is an API for manipulating HTML and XML documents. It provides a structural representation of the document, enabling you to modify its content and visual presentation by using a scripting language such as JavaScript. 

The Document Object Model is an API for HTML and XML documents. It provides a structural representation of the document, enabling the developer to modify its content and visual presentation. Essentially, it connects web pages to scripts or programming languages.

All of the properties, methods, and events available to the web developer for manipulating and creating web pages are organized into objects (e.g., the document object that represents the document itself, the table object that represents a HTML table element, and so forth). Those objects are accessible via scripting languages in most recent web browsers.

The DOM is most often used in conjunction with JavaScript. However, the DOM was designed to be independent of any particular programming language, making the structural representation of the document available from a single, consistent API. Though we focus on JavaScript throughout this site, implementations of the DOM can be built for any language.

The World Wide Web Consortium establishes a standard for the DOM, called the W3C DOM. It should, now that the most important browsers correctly implement it, enable powerful cross-browser applications.

jQuery

jQuery is a cross-platform JavaScript library designed to simplify the client-side scripting of HTML

Mergesort VS Quicksort

Algorithm: 

Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.
Performance

Worst Case O(n log n)
Average Case O(n log n)
Worst Case Space Complexity O(n) auxiliary 

Example code

	public ListNode sortList(ListNode head) {
	ListNode node = head;
	int n =0;
	while(node!= null){
	n++;
	node = node.next;
	}
	node = head;
	return sortList(head, n);
	}
	public ListNode sortList(ListNode head, int len){
	ListNode node = head;
	ListNode pre = null;
	ListNode left = head;
	ListNode right = null;
	if(len<2) return head;
	for(int i=1; i<=len/2; i++){
	pre = node;
	node = node.next;
	}
	pre.next = null;
	right = node;
	left = sortList(left, len/2);
	right = sortList(right, len-len/2);
	return mergeList(left, len/2, right, len-len/2);
	}
	public ListNode mergeList(ListNode left, int leftLen, ListNode right, int rightLen){
	ListNode newListHead = null;
	ListNode node = null;
	ListNode leftNode = left, rightNode = right;
	if(left.val > right.val){
	newListHead = right;
	right = right.next;
	rightLen--;
	rightNode = right;
	}
	else{
	newListHead = left;
	left = left.next;
	leftLen--;
	leftNode = left;
	}
	node = newListHead;
	while(leftLen>0 || rightLen>0){
	if(leftLen>0 && rightLen>0){
	if(leftNode.val > rightNode.val){
	node.next = rightNode;
	rightNode = rightNode.next;
	rightLen--;
	node = node.next;
	node.next = null;
	}
	else{
	node.next = leftNode;
	leftNode = leftNode.next;
	leftLen--;
	node = node.next;
	node.next = null;
	}
	}
	else if(leftLen == 0){
	node.next = rightNode;
	break;
	}
	else if(rightLen == 0){
	node.next = leftNode;
	break;
	}
	}
	return newListHead;
	}

view raw gistfile1.java hosted with ❤ by GitHub

Reference wikipedia Mergesort

Quicksort

Algorithm

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.

The steps are:
Pick an element, called a pivot, from the list.
Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.
The base case of the recursion are lists of size zero or one, which never need to be sorted.

Performance

Worst Case O(n^2)
Average Case O(n log n)
Worst Case Space Complexity O(n) auxiliary (naive) or O(log n) auxiliary

Example code

	public void sort(int[] num, int start, int end){
	int pivotIdex = partition(num, start, end);
	if(start < pivotIdex-1)
	sort(num, start, pivotIdex-1);
	if(pivotIdex<end)
	sort(num, pivotIdex, end);
	}
	public int partition(int arr[], int left, int right){
	int i = left, j = right;
	int tmp;
	int pivot = arr[(left + right) / 2];
	while (i <= j) {
	while (arr[i] < pivot)
	i++;
	while (arr[j] > pivot)
	j--;
	if (i <= j) {
	tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
	i++;
	j--;
	}
	};
	return i;
	}

view raw gistfile1.java hosted with ❤ by GitHub

Comparison

Although heapsort has the same time bounds as merge sort, it requires only Θ(1) auxiliary space instead of merge sort’s Θ(n). On typical modern architectures, efficient quicksort implementations generally outperform mergesort for sorting RAM-based arrays. On the other hand, merge sort is a stable sort and is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.


As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted.[11] Python uses timsort, another tuned hybrid of merge sort and insertion sort, that has become the standard sort algorithm in Java SE 7,[12] on the Android platform,[13] and in GNU Octave.[14]


Reference WikiPedia Quicksort

LeetCode: Anagrams && HashMap

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

Solution:

Use a HashMap to store sorted strings. If two strings are anagrams, they are the same after being sorted.

	public ArrayList<String> anagrams(String[] strs) {
	ArrayList<String> ret = new ArrayList<String>();
	Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
	if(strs==null || strs.length == 0) return ret;
	for(int i=0; i< strs.length; i++){
	char[] temp = strs[i].toCharArray();
	Arrays.sort(temp);
	String sortedStr = new String(temp);
	if(map.containsKey(sortedStr)){
	map.get(sortedStr).add(strs[i]);
	}
	else{
	ArrayList<String> newArr = new ArrayList<String>();
	newArr.add(strs[i]);
	map.put(sortedStr, newArr);
	}
	}
	for(ArrayList<String> arrs : map.values()){
	if(arrs.size()>1)
	ret.addAll(arrs);
	}
	return ret;
	}

view raw gistfile1.java hosted with ❤ by GitHub

LeetCode: Remove Duplicates from Sorted Array I&&II

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

Solution:

惊艳！One time pass.....

	public int removeDuplicates(int[] A) {
	if(A == null || A.length ==0) return 0;
	int len = A.length;
	int moveForward =0;
	int finLen =1;
	for(int i=1; i<len; i++){
	while(i<len && A[i]==A[i-1]){
	//find a duplicate, use moveForward to indicate how many items to be deleted
	//The new index of next new item would be i-moveForward
	moveForward++;
	i++;
	}
	if(i==len) return finLen;
	if(moveForward>0)
	A[i-moveForward] = A[i];
	finLen++;
	}
	return finLen;
	}

view raw gistfile1.java hosted with ❤ by GitHub

上面的这种方法在解决II的时候变得无比dumb. 其实还有更简单漂亮的解法 双指针 can be considered as double pointers problem

	//solution for I
	public int removeDuplicates(int[] A) {
	if(A == null || A.length ==0) return 0;
	int newEndIndex=0;
	for(int i=1; i<A.length; i++){
	if(A[i]!=A[newEndIndex])
	A[++newEndIndex]=A[i];
	}
	return newEndIndex+1;
	}
	////solution for II
	public int removeDuplicates(int[] A) {
	if(A == null || A.length ==0) return 0;
	int newEndIndex=0;
	int occurTimes=1;
	for(int i=1; i<A.length; i++){
	if(A[i]==A[newEndIndex]){
	if(occurTimes>=2) continue;
	occurTimes++;
	}
	else
	occurTimes=1;
	A[++newEndIndex]=A[i];
	}
	return newEndIndex+1;
	}

view raw gistfile1.java hosted with ❤ by GitHub

LeetCode: Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

Solution:
At first I misunderstood the problem. I thought it requires to exchange the mth and the nth node. The code is as follows

	public ListNode reverseBetweenTwoNodes(ListNode head, int m, int n) {
	if(m==n) return head;
	if(head.next==null) return head;
	ListNode node = head, prv = head;
	ListNode mNode = head, mPrv =head;
	int i=1;
	if((m+1) == n){//at first, I didn't consider this situation.
	while(node != null){
	if(i==m){
	if(m==1){
	node=head.next;
	ListNode tempNext = node.next;
	node.next = head;
	head.next = tempNext;
	head = node;
	}
	else{
	ListNode tempNext = node.next.next;
	prv.next = node.next;
	node.next.next = node;
	node.next = tempNext;
	}
	break;
	}
	i++;
	prv = node;
	node = node.next;
	}
	}
	else{
	while(node != null){///while(node) wrong several times
	if(i==m){
	mNode = node;
	mPrv = prv;
	}
	else if(i==n){
	if(m==1){
	head = head.next;
	prv.next = mNode;
	mNode.next = node.next;
	node.next = head;
	head = node;
	}
	else{
	mPrv.next=node;
	prv.next = mNode;
	ListNode tempNext = node.next;
	node.next = mNode.next;
	mNode.next = tempNext;
	}
	break;
	}
	i++;
	prv = node;
	node = node.next;
	}
	}
	return head;//forgot the return statement
	}

view raw gistfile1.java hosted with ❤ by GitHub

The real intention of this problem is to reverse all nodes between the mth and the nth node. Code:

	public ListNode reverseBetween(ListNode head, int m, int n) {
	if(m==n) return head;
	if(head.next==null) return head;
	ListNode node = head, prv = head;
	ListNode insertRight = head, insertLeft =head;
	int i=1;
	ListNode tempHead = new ListNode(0);
	//use a dumb node to be the temp head if m==1. the trick saves code to deal with the special case of head
	while(node != null){
	if(i==m){
	if(m==1) insertLeft = tempHead;
	else insertLeft = prv;
	insertRight = node;
	}
	if(i>m){
	prv.next = node.next;
	insertLeft.next = node;
	node.next = insertRight;
	insertRight = insertLeft.next;
	node = prv;//for next node to be picked up and inserted
	}
	i++;
	if(i>n) break;
	prv = node;
	node = node.next;
	}
	if(tempHead.next != null) return tempHead.next;
	else return head;
	}

view raw gistfile1.java hosted with ❤ by GitHub