Posting Java Code On Blogger

When I returned to review my posts containing Java code,  I found many of contents have been lost and become unreadable. A quick search recommands this to use:

http://hilite.me/

I am gonna update my posts tomorrow.

Longest Word in 2 D Array

Problem:
given a 2D character array, and a dictionary, please find the longest in dictionary word from the array.

Restrictions:
Do not access an element twice;
from current position, there are 8 possible next moves: horizontally, vertically and Diagonally.

I will give out two solutions here. One is working directly on the given array, another is to covert the array to a graph, and then do depth first traversal to access all possible path and build out word as it traverses.
The key in second solution is to build up neighbors. The second approach has more codes to work on, but it is easier to understand.

Time efficiency for the two solutions are about the same, but second one use extra data structure so it consumes more space.

Solution 1:
Starting from anywhere in a matrix and find all words starting with it. since it uses same strategy to follow all the possible paths to go further, it's naturally recursive solution.

package tree;

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

//this program return first in dictionary word with maximum word length
public class TDArray {

 // test: remove T from shopbopt to return abebook
 public static void main(String[] args) {
  final char array[][] = { 
    { 'A', 'B', 'P', 'R' },
    { 'S', 'H', 'E', 'P' }, 
    { 'P', 'O', 'V', 'B' },
    { 'B', 'O', 'O', 'O' },
    { 'C', 'P', 'T', 'K' } 
    };
  final Set<String> dict = new HashSet<>(Arrays.asList("AMAZON",
    "ABEBOOKTO", "SHOPBOPT"));
  findLongestWorrdInDictionary(array, dict);

 }

 public static int longestLength(Set<String> dict) {
  if (dict == null)
   return -1;
  int length = 0;
  for (String word : dict) {
   if (word.length() > length)
    length = word.length();
  }
  return length;
 }

 public static void findLongestWorrdInDictionary(char[][] matrix,
   Set<String> dictionary) {
  if (matrix == null || dictionary == null)
   return;
  String longestWord = null;
  Set<String> visited = new HashSet<>();
  StringBuffer finalWord = new StringBuffer();
  // search from each possible start position
  for (int i = 0; i < matrix.length; i++) {
   for (int j = 0; j < matrix[i].length; j++) {
    visited.clear();
    longestWord = "";
    findFromNewStart(matrix, dictionary, i, j, longestWord,
      visited, longestLength(dictionary), finalWord);
   }
  }

  System.out.print("Longest in dictionary word is:" + finalWord);
 }

 // from each start position, it can go to 8 possible other positions
 public static String findFromNewStart(char[][] matrix, Set<String> dict,
   int x, int y, String longestWord, Set<String> visited,
   int maxLength, StringBuffer finalWord) {
  // over the matric boundary, return previous string/word being built
  if (x < 0 || y < 0 || x >= matrix.length || y >= matrix[0].length)
   return longestWord;
  // if the string is already longer than the max word length in
  // dictionary, stop building longer string
  if (longestWord.length() >= maxLength)
   return longestWord;
  // all the nodes have been visited, then this operation is done because
  // it's asked not to access same node twice
  if (!visited.add(String.valueOf(x) + String.valueOf(y))) {
   return longestWord;
  }
  // otherwise, we can continue to build longer string by adding the
  // current character
  longestWord = longestWord + matrix[x][y];
  // for each new string, check if it is in the dictionary
  if (dict.contains(longestWord)){
   System.out.println("Find a word:" + longestWord);
    
    if( longestWord.length() > finalWord.length()) {
   // if the current in dictionary word is longer than previous in
   // dictionary word, then remember it as new candidate word

     finalWord.delete(0, finalWord.length());
     finalWord.append(longestWord);
    }
  }
//for a given node (x,y), since all nodes can only be accessed once, the visited should keep tracking them
//but when going back to the start node, all nodes should be removed so that next invoking won't be impacted  
  // go next step 1-left,2-upper left, 3-up, 4-upper right,5-right,6-lower
  // right, 7-down, 8-lower left

  // 1 of 8 possible moving directions, each of new node has same 8
  // possible moving directions, the possible moving directions are
  // traversed according to following sequences

  findFromNewStart(matrix, dict, x - 1, y, longestWord, visited,
    maxLength, finalWord);

  findFromNewStart(matrix, dict, x - 1, y + 1, longestWord, visited,
    maxLength, finalWord);
  findFromNewStart(matrix, dict, x, y + 1, longestWord, visited,
    maxLength, finalWord);
  findFromNewStart(matrix, dict, x + 1, y + 1, longestWord, visited,
    maxLength, finalWord);
  findFromNewStart(matrix, dict, x + 1, y, longestWord, visited,
    maxLength, finalWord);
  findFromNewStart(matrix, dict, x + 1, y - 1, longestWord, visited,
    maxLength, finalWord);
  findFromNewStart(matrix, dict, x, y - 1, longestWord, visited,
    maxLength, finalWord);
  findFromNewStart(matrix, dict, x - 1, y - 1, longestWord, visited,
    maxLength, finalWord);
  /**
   * the above can be done this way:
   * for (int row=y-1; row<=y+1 && row<matrix.length; row++)
        for (int col=x-1; col<=x+1 && col<matrix[0].length; col++)
          if (row>=0 && col>=0 && !visited.contains(String.valueOf(col) + String.valueOf(row)))
     findFromNewStart(matrix, dict, col, row, longestWord, visited,
       maxLength, finalWord);
   */
  //at end of traversal, nodes should be removed from visited list so that next traversal from different node won't be impacted
  visited.remove(String.valueOf(x) + String.valueOf(y));
  return longestWord;
 }

}

Solution 2 

Converting the matrix to a graph, starting from any node/vertex and for every node/vertex, using depth first traversal to traverse the entire graph. a node's neighbors are the ones surrounding the corresponding element in the matrix.

package tree;

/**
 * Boggle (Find all possible words in a board of characters)
 */
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

/**
 * The idea is to consider every character as a starting character and find all
 * words starting with it. All words starting from a character can be found
 * using Depth First Traversal. We do depth first traversal starting from every
 * cell. We keep track of visited cells to make sure that a cell is considered
 * only once in a word.
 * 
 * The matrix is converted to graphy in order to to graph traversal, a node's
 * neighbors are the ones surrounding the node in matrix
 * 
 * then do depth first traversal from every node, and find all possible letter
 * combinations during traversal check if the words are in dictionanry, and
 * remember the one with longest length
 * 
 * @author ama
 *
 */
public class TDArrayGraphySolution {

 public static void main(String[] args) {
  final char givenArray[][] = { { 'A', 'B', 'P', 'R' },
    { 'S', 'H', 'E', 'P' }, { 'P', 'O', 'V', 'B' },
    { 'B', 'O', 'O', 'O' }, { 'C', 'P', 'T', 'K' } };
  final Set<String> dict = new HashSet<>(Arrays.asList("AMAZON",
    "ABEBOOK", "SHOPBOPT"));
  int row = givenArray.length;
  int col = givenArray[0].length;

  Vertex[][] graph = new Vertex[row][col];
  // initialize vertexes, it is similiar to the given array, but with
  // elements as vertex
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < col; j++) {
    graph[i][j] = new Vertex(String.valueOf(givenArray[i][j]));
   }
  }
  // make up graph by complete neighbor relationships
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < col; j++) {
    // moving left
    if (j > 0)
     graph[i][j].addNeighbor(graph[i][j - 1]);
    // move upper left
    if (i > 0 && j > 0)
     graph[i][j].addNeighbor(graph[i - 1][j - 1]);
    // move up
    if (i > 0)
     graph[i][j].addNeighbor(graph[i - 1][j]);
    // move upper right
    if (i > 0 && j < col - 1)
     graph[i][j].addNeighbor(graph[i - 1][j + 1]);
    // move right
    if (j < col - 1)
     graph[i][j].addNeighbor(graph[i][j + 1]);
    // move lower right
    if (i < row - 1 && j < col - 1)
     graph[i][j].addNeighbor(graph[i + 1][j + 1]);
    // move down
    if (i < row - 1)
     graph[i][j].addNeighbor(graph[i + 1][j]);
    // move down left
    if (i < row - 1 && j > 0)
     graph[i][j].addNeighbor(graph[i + 1][j - 1]);

   }
  }
  // then traverse it with DFS
  String longestWord = "";
  StringBuffer sb = new StringBuffer();
  for (int i = 0; i < row; i++) {
   for (int j = 0; j < col; j++) {
    longestWord = getStringByDFT(graph[i][j], sb, longestWord,
      longestLength(dict), dict);

   }
  }
  System.out.println("Longest in dict word is: " + longestWord);
 }

 /**
  * return longest length of word in dictionary
  * 
  * @param dict
  * @return
  */
 public static int longestLength(Set<String> dict) {
  if (dict == null)
   return -1;
  int length = 0;
  for (String word : dict) {
   if (word.length() > length)
    length = word.length();
  }
  return length;
 }

 /**
  * depth first traversal to traverse all the nodes in graph:
  * 
  * access a vertext, then its neighbors from left to right
  * 
  * to avoid repeatedly accessing a vertex, it will be marked as visited. you
  * can also use another structure to record what is visited so far.
  * 
  * it builds string while traversing. it does not need to go through all the
  * nodes because longest words in dictionary is one of exit condition.
  * 
  * since from every node, this recursion will repeat, so that when going
  * back to body of recursion function, the current node is marked as not
  * visited so that recursion form same level of neighbors can still access
  * this node.
  * 
  * The string being built changes its content while going in and going out
  * the recursion function to reflect the current access path.
  * 
  * @param vertex
  * @param toBuild
  * @param longestWordinDict
  * @param maxLength
  * @param dict
  * @return
  */
 public static String getStringByDFT(Vertex vertex, StringBuffer toBuild,
   String longestWordinDict, int maxLength, Set<String> dict) {
  if (vertex == null || dict == null)
   return null;

  // access the vertex
  toBuild.append(vertex.getVal());
  // System.out.println(toBuild.toString());
  if (toBuild.length() > maxLength) {
   vertex.setVisited(false);
   toBuild.deleteCharAt(toBuild.length() - 1);
   return longestWordinDict;
  }
  if (dict.contains(toBuild.toString())) {
   System.out.println("Found a word in dictionary:"
     + toBuild.toString());
   if (longestWordinDict.length() < toBuild.length()) {

    longestWordinDict = toBuild.toString();
   }
  }
  // then vertex's neighbors
  for (Vertex neighbor : vertex.getNeighbors()) {
   if (!neighbor.isVisited())
    longestWordinDict = getStringByDFT(neighbor, toBuild,
      longestWordinDict, maxLength, dict);
  }
  // because it needs to traverse the graph from another vertex so that
  // when going back, cleaning up its access status
  // but going forward, it's marked as visited so that same vertex won't
  // be used twice
  vertex.setVisited(false);
  toBuild.deleteCharAt(toBuild.length() - 1);
  return longestWordinDict;
 }

}

import java.util.Collection;
import java.util.LinkedList;

public class Vertex {
 private final String val;
   private final Collection<Vertex> neighbors = new LinkedList<Vertex>();
   private boolean visited;
   
   public Iterable<Vertex> getNeighbors(){
     return neighbors;
   }
   
   public boolean isVisited(){
     return visited;
   }
   
   public String getVal(){
    visited = true;
    return val;
   }
   
   public Vertex(String item) {
     this.val = item;
   }
   
   public void addNeighbor(Vertex neighbor) {
     neighbors.add(neighbor);
   }
   public void setVisited(boolean visited){
    this.visited = visited;
   }
}

Brief an Onsite Interview

Smart and nice interviewer

5 interview in a row, 45 to 60 minutes for each

Half of each interview is devoted to coding and OOD.

No asking on content of resume and yourself. They would figure that out by their questions.

Most frequently asked questions:

resolved a complex problem with simple solution.

Compromise in order to meet deadline.

How do you convince others to follow your approach

How to handle conflict

how do you mentor junior developers.
Etc

Coding questions are silmilar hardness the first 3 ones, the last coding question is much harder. They will give you clue if you are stuck.

Key to success: relax and confident. Think freely. Prepare the coding questions by going through career cups,leetcode etc. I did not spend much time on those due to time restriction, but I feel it will definitely help a lot after you go through all those challenges. My solution are most close to right answer, but still miss the last half step. It would be different if I have second chance or have gone through careercups.

You will feel tired for sure and your solution to the last couple coding and design questions would be dumber than you usually would be able to come up.

I think my interview is a failure but
Felt happy to meet those guys and got a chance to experience an interview that is so challenging.

Use Case Relationship

Key: forget about OOD concept

 You read <> associations in the direction of the arrow,while you read <> associations in the reverse direction. 

Generalization (denoted Use case B is a type of use case A)

it as an “overrides” relationship. it is just saying that these use cases are all "general" type of use cases. general case is just a concept instead of real implementation. e.g. pay, can have pay by credit, pay be paypal as special cases, you only need to implement pay by credit ad pay by paypal.

A<>B

similar to function call. half way through A, B is called. after B is finished, A continues its rest part.

A<>B

this is not inheritance.B is basic and complete use case, A is additional function can be added to B.

A<B

A happens before B

A<B
similar to includes

DFT and BFT

This is a good video resource about the theory behind it.
http://www.youtube.com/watch?v=zLZhSSXAwxI

For tree and graph.

DFT: drills down the linked nodes, process the far most not reached nodes the first, then going back for more not reached nodes from last node. stack is naturally exploited to track the nodes that need go back to revisit. it's done when there's no node in the stack. complete of a node's process is done by confirming there's no not visited neighbors.

BFT: have a current processed node, then track the current node's neighbor in a queue for further process. it's done when no node in the queue. Complete of a node's process is done by confirming there's no not visited neighbors.

Both of them require a mechnism to mark the visited nodes. set in java is good data structure for doing this. You can tell if the node is visited the same time you add it to the set.


Tree is special form of graph, the algorithm can be modified to not check if a node is visited.

In tree's case, for DFT, you can do
preorder: root,left,right
inorder : left, root, right
post order :left, right, root

traversal.


Recursive call is realized by stack mechanism and it can be converted to use stack to implement.

Some examples:

package tree;

public class TreeNode {
String val;
TreeNode left;
TreeNode right;

public TreeNode(String value){
this.val=value;
}
}


package tree;

import java.util.LinkedList;
import java.util.Queue;

public class Excercise {
static TreeNode aTree = new TreeNode("root");
static void prepareATree(){
TreeNode l = new TreeNode("0.left");
TreeNode r = new TreeNode("0.right");
aTree.left = l;
aTree.right = r;
l.left = new TreeNode("1.left");
l.right = new TreeNode("1.right");
r.left = new TreeNode("2.left");
r.right = new TreeNode("2.right");
r.right.right = new TreeNode("3.right");

}
/**
* @param args
*/
public static void main(String[] args) {
prepareATree();
// System.out.println(findHeight(aTree));
// System.out.println(findMaxNodeNumber(aTree));
// System.out.println(findMinNodeNumber(aTree));
// findShortestPath(aTree);
BFTraversal(aTree);
DFTraversal_PreOrder(aTree);
DFTraversal_InOrder(aTree);
DFTraversal_PostOrder(aTree);
}

//maximum edges between root and it's leafs
public static int findHeight(TreeNode root){
if (root==null)return -1;
//+1 is the calculation. for any none null child level, this will be added one up
return Math.max(findHeight(root.left), findHeight(root.right))+1;
}
//find a number of nodes on the height
public static int findMaxNodeNumber(TreeNode root){
if (root==null)return 0;
return Math.max(findMaxNodeNumber(root.left), findMaxNodeNumber(root.right))+1;
}

public static int findMinNodeNumber(TreeNode root){
if (root==null)return 0;
return Math.min(findMinNodeNumber(root.left), findMinNodeNumber(root.right))+1;
}
//analysis: check it layer by layer and identify out a first node that has no child. breadth first traversal
//in order to travel back 
public static void findShortestPath(TreeNode root){
TreeNode curNode;
if (root == null) return;
if(root.left==null && root.right==null){
System.out.println(root.val);
return;
}
Queue tmpQ = new LinkedList();
if(root.left!=null)
tmpQ.add(root.left);
if (root.right!=null)
tmpQ.add(root.right);
System.out.println(root.val);//visit the current node
while(!tmpQ.isEmpty()){
curNode = tmpQ.remove();//remove from head. queue is add to tail, remove from head
if(curNode.left!=null)
tmpQ.add(curNode.left);
if(curNode.right!=null)
tmpQ.add(curNode.right);
if (curNode.left==null && curNode.right==null){
System.out.println("final node:"+curNode.val);
break;
}
System.out.println(curNode.val);
}
}
public static void BFTraversal(TreeNode root){
TreeNode curNode;
if (root == null) return;
if(root.left==null && root.right==null){
System.out.println(root.val);
return;
}
Queue tmpQ = new LinkedList();
if(root.left!=null)
tmpQ.add(root.left);
if (root.right!=null)
tmpQ.add(root.right);
//using printing out as a way of access
System.out.println(root.val);//visit the current node
while(!tmpQ.isEmpty()){
curNode = tmpQ.remove();//remove from head. queue is add to tail, remove from head
//add the current node's children after the current layer's nodes
//we are lining up the nodes here
if(curNode.left!=null)
tmpQ.add(curNode.left);
if(curNode.right!=null)
tmpQ.add(curNode.right);

System.out.println(curNode.val);
}
}
public static void DFTraversal_PreOrder(TreeNode root){
if(root==null)return;
//this is to access the node
System.out.println(root.val);
DFTraversal_PreOrder(root.left);
DFTraversal_PreOrder(root.right);

}
public static void DFTraversal_PostOrder(TreeNode root){
if(root==null)return;
//this is to access the node
DFTraversal_PreOrder(root.left);
DFTraversal_PreOrder(root.right);
System.out.println(root.val);
}
public static void DFTraversal_InOrder(TreeNode root){
if(root==null)return;
//this is to access the node
DFTraversal_InOrder(root.left);
System.out.println(root.val);
DFTraversal_InOrder(root.right);

}
}

Merge Sort Practice

Merge sort is divide and conquer algorithm. it divides a problem into sub problems, and resolved the sub problems the first, then goes back to resolve problem based on resolved subproblems.

The idea of merge sort is to divide the list or array into smaller list or arrays until it can no longer be divided, that is, an one element array or list, then sort the divided array or list and merge them into sorted array or list to resolve original problem. the array or list with one element is considered as sorted.

Below is my practice on this algorithm with Java implementation. Array is passed by reference.

package array;

public class MergeSort {


public static void main(String[] args) {
int[] intOriginal = {0,10,32,3,44,15};
arrayTest(intOriginal);
for(int i=0;i System.out.println(intOriginal[i]);
mergeSort(intOriginal);
for(int i=0;i System.out.println(intOriginal[i]);
}
//this is to verify array is passed by reference
public static void arrayTest(int[] intA){
if (intA==null )return;
for(int i=0;i intA[i]+=1;

}
public static void mergeSort(int[] intA){
//array with one element is considered as sorted
if (intA==null||intA.length<2 p="" return=""> //longer than 1, then it is not sorted and we will try to sort it
//divide and conquer.
//divide the array into two subarrays. seperated from middle.
int mid = intA.length/2;
int[] leftA = new int[mid];
int[] rightA = new int[intA.length-mid];
System.arraycopy(intA, 0, leftA, 0, mid);
System.arraycopy(intA, mid, rightA, 0, intA.length-mid);
//do the same merge sort on the left and right subarrays
mergeSort(leftA);
mergeSort(rightA);
//after sorting left and right array, we need to merge the sorted array into original array
//this step does both sort and merge
mergeSortedArray(leftA,rightA,intA);
}
//content in intA can be overridden
public static void mergeSortedArray(int[] leftA,int[] rightA,int[] intA){
if(leftA==null||rightA==null || intA==null)return;
int i=0,j=0,k=0;
//it stops when one array is done the first
while(i if(leftA[i]<=rightA[j]){
intA[k]=leftA[i];
i++;
}
else{
intA[k] = rightA[j];
j++;
}
k++;
}
//then merge rest of array to target array
while(i intA[k]=leftA[i];
i++;k++;
}
while(j intA[k]=rightA[j];
j++;k++;
}
}

}

Misc Notes

hashCode and equals

hashCode is used to find a bucket, equals is used to further compare it with objects already in the bucket.

MapReduce

it is a program model that composed of a map() procedure that performs filtering and sorting, a reduce() procedure that performs summary operation.

'MapReduce' is a framework for processing parallelizable problems across huge datasets using a large number of computers (nodes), collectively referred to as a cluster (if all nodes are on the same local network and use similar hardware) or a grid (if the nodes are shared across geographically and administratively distributed systems, and use more heterogenous hardware)

"Map" step: The master node takes the input, divides it into smaller sub-problems, and distributes them to worker nodes. A worker node may do this again in turn, leading to a multi-level tree structure. The worker node processes the smaller problem, and passes the answer back to its master node.

"Reduce" step: The master node then collects the answers from all the sub-problems and combines them in some way to form the output – the answer to the problem it was originally trying to solve.

The Map and Reduce functions of MapReduce are both defined with data structured as (key, value) pairs. Map takes one pair of data with a type in one data domain, and returns a list of pairs in a different domain:

Map(k1,v1) → list(k2,v2)

The Map function is applied in parallel to every pair in the input dataset. This produces a list of pairs for each call. After that, the MapReduce framework collects all pairs with the same key from all lists and groups them together, creating one group for each key.

The Reduce function is then applied in parallel to each group, which in turn produces a collection of values in the same domain:

Reduce(k2, list (v2)) → list(v3)

Each Reduce call typically produces either one value v3 or an empty return, though one call is allowed to return more than one value. The returns of all calls are collected as the desired result list.

Thus the MapReduce framework transforms a list of (key, value) pairs into a list of values

Depth First Traversal

DFS only examines vertices connected to the source. less momery

usually uses recursion

void preorderTraversal( Node curNode){
    if( curNode== null ) return;
    curNode.printValue();
    preorderTraversal( curNode.getLeft() );
    preorderTraversal( curNode.getRight() );
}

What’s the running time on this algorithm? Every node is examined once, so it’s O(n).

Note that inorder and postorder traversals are almost identical; all you vary is the order in which the node and subtrees are visited:

void inorderTraversal( Node curNode){
    if( curNode== null ) return;
    inorderTraversal( curNode.getLeft() );
    curNode.printValue();
    inorderTraversal( curNode.getRight() );
}

void postorderTraversal( Node curNode){
    if( curNode== null ) return;
    postorderTraversal( curNode.getLeft() );
    postorderTraversal( curNode.getRight() );
    curNode.printValue();
}

Breadth first traversal

we usually use this to find shorted path.  use more  memory since you have to track the children of searched modes.

Traversal of tree visits nodes in order of their depth. it visits node at depth 0, then depth 1 and 2 and so on, from left to right.

Heap is a binary search tree with only left tree, plus adjacent nodes can be equal or less than.

Notes on REST

It is based on plain HTTP, statelessness. It is a architectural style instead of a standard.

http://docs.oracle.com/javaee/7/tutorial/doc/jaxrs.htm

-- resource identification though URI
--uniformed interface: put, get, delete, post
--self-descriptive message
--stateful interaction through hyperlink  link(every interaction itself is  stateless)

Safe method: read only
idempotent: same input same output. delete is idempotent because subsequent calling wonèt change the outcome. POST is not idempotent because calling it multiple times with same parameters can have  different outcomes.


components of RESTful web service:
- base uri for web service
- media type supported by ws
- methods or verbs used such as get, put, post, and delete.

JAX-RS
java api for representationalstate transfer is a specification defines a set of java apis for building web services conforming to REST style. it defines how to expose POJOs as web resources using HTTP as network protocal.

Practice:
-- create a RESTful root resourse
A root resource is a POJO annotated with @Path
(this function is my answer in Amazons phone interview :))

import java.io.*;
import java.util.*;

import javax.ws.rs.GET;
import javax.ws.rs.Path;
import javax.ws.rs.PathParam;

/**
 * root resource, exposed at algorithm
 * @author ama
 *
 */
@Path("/test")
public class Algorithm {
/*@GET
static String simpleTest() {
   
    return "I am on service";
}
*/
@GET
@Path("/{statement}")
//I forgot to make this method as public at first place, then it mademe struggled for more than one hour to figure out why it was not working
public String isValid(@PathParam("statement") String statement) {
    if (isValidStatement(statement))
    return "balanced";
    else
    return "imbalanced";
}

   static boolean isValidStatement(@PathParam("statement") String statement) {
       Stack sHelper = new Stack();
       Character tmp;
       Character leftP = new Character('(');
       Character rightP = new Character(')');
       Character leftB = new Character('[');
       Character rightB = new Character(']');
       if (statement == null) return false;
       for (int i=0;i            tmp = statement.charAt(i);
           if (tmp.equals(leftB) || tmp.equals(leftP)){
               sHelper.push(tmp);
           }else if (tmp.equals(rightB) ){
               if (!sHelper.isEmpty() && leftB.equals(sHelper.peek()))
                   sHelper.pop();
               else
               return false;
             
           }else if (tmp.equals(rightP) ){
               if (!sHelper.isEmpty() && leftP.equals(sHelper.peek()))
                   sHelper.pop();
               else
               return false;
           //need a } here
           }//thank you
       }
       return sHelper.empty();
   }

}

--make a web,xml to describe the web app. you do not  need  to define any servlet and servlet mapping in server let 3.0. in version prior to 3.0, I tried to use jersey to make it work.  the commented definination in the web.xml are under the help of jersey.

  my REST Example

--test it

http://localhost:8080/algorithm/test/abcdefg(fdfd)kll(ll