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

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

C++: calling base class constructors

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

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如下：

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;

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].

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.

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:




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:

which you can test with the class:




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:

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

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

参考图解

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.

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

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:

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.

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.

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  

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

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

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.

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

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

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

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