Never Do This Again

Few days ago, I watched one TED speech Your body language shapes who you are (http://www.ted.com/playlists/171/the_most_popular_talks_of_all). Suddenly one of major reason why I failed Amazon onsite appears clearly to me: I did too much dominant postures instead of show how modest I am. Imagine that, will you hire a candidate who was sitting on the table and you were keeping stretching or opening your arm to try to dominant back?

Jesus, I wish I watched it before my interview.

Understanding HBase Table Definition

Hbase: distributed column-oriented database built on top of HDFS. It’s used when you require real-time (read/write) random-access to very large data set. Its table is like table in RDBMS, but cells are versioned, rows are sorted, and columns can be added on the fly as long as column family is already there. Has simpler API for basic CRUD operations, plus a scan function to iterate over large key ranges.

It's able to deal with many small files and low latency situations.

A table in HBase is a sparse, distributed, persistent, multidimensional map, which is indexed by row key, column key, and a timestamp. looks like this:

(Table, RowKey, column Family, Column, Timestamp) → Value

Putting it in data structure, it's like this:

SortedMap<                         //table

    RowKey,                         //a row

                List<                   //content of a row, is another map, 

        SortedMap<                 //one map is one column family

            Column, List<          //within on column family, you can dynamically have multiple columns

                Value, Timestamp  //for each key, it can have multiple version of values, sorted descendingly

                                 >

                           >

                        >

           >

I struggled the first to understand it's table definition, mainly because of wrong impression on column. it's said column can be added on the fly, but actually column here is just a key of a key-value pair within a grid value, if you treat column family the column as concept in RDBMS.

So to summarize, at least what will help me to understand it, is to think it this way:

1. viewing it as spreadsheet or RDBMS table, columns are column families

2. within each grid in the table, the data is organized in a form of a map of [key value+timestamp]-->value. so far, this maps to 2D normal table model

3. if you want to go further and insist to call key values in grid's data as columns, now you have a 3D vision of value of keys (row+column family+timstamp). In 3D version of view, each piece of data is called a cell. a cell is tagged/located by (RowKey, column Family, Column, Timestamp)

Now checking further the table scan result from hbase, it calls it column+cell. column=column family:key identifier, with timestamp, it tagged a value. Here is an example.

ROW                   COLUMN+CELL                                               

 row1                 column=cf1:key1, timestamp=1417140625098, value=value1    

 row1                 column=cf1:key2, timestamp=1417140642014, value=value2    

 row1                 column=cf1:key3, timestamp=1417141283628, value=newValue  

 row1                 column=cf2:key1, timestamp=1417140752958, value=value1    

 row1                 column=cf2:key2, timestamp=1417140761428, value=value2    

 row2                 column=cf1:key1, timestamp=1417141754748, value=ama       

 row2                 column=cf1:key21, timestamp=1417140781886, value=value21  

 row2                 column=cf1:key22, timestamp=1417140892737, value=value22  

 row2                 column=cf2:key1, timestamp=1417140909231, value=value1  

Now check the put statement:

put "test","row1","cf1:key3","value4"

It is to insert a value into a cell tagged by: row1+column family+column, in the cell, there are multiple versions of data, up most value is displayed by simple scan statement.

I drew a diagram to help myself to understand it

Web Server Information

Using telnet, connect to web port, usually 80, then issue these commands to get web server information: telnet website 80 get / host:website

Realm Etc

Realm is a basic concept, but I never make it clear to me. It's time to review it.

https://docs.oracle.com/javaee/7/tutorial/doc/security-intro005.htm

A realm is a security policy domain defined for a web or application server.

A realm contains a collection of users, who may or may not be assigned to a group.

In some applications, authorized users are assigned to roles. In this situation, the role assigned to the user in the application must be mapped to a principal or group defined on the application server

A realm is a complete database of users and groups identified as valid users of one or more applications and controlled by the same authentication policy.

To be simple, Realm is a way of user database implementation. can be in file, then called file realm,

in a certification database, then called certificate realm, etc

Group is purely grouping user together for management convenience. it's service wise.

Role is about access control. An abstraction of relationship between user and resource access. it's application wise.

Role can be mapped user directly or indirectly via group, but the target is to grant user access privileges.

Last Non-repeat Element

Given a stream of object, make a function to return last non repeating object.
(I was confused by definition of steam, it can simply mean a collection of object)

Solution:
use a Set or HashMap to figure out the repeating of objects, then use a Deque to access head or tail in O(1) time. Collection has convenient method to remove object: remove(o).

package LastNonRepeatCharacter;

import java.util.Arrays;
import java.util.Collection;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;
import java.util.stream.Stream;
/**
* return last non-repeating object
*
* @author Andrew Ma
*
*/
public class SolutionObject {
 Deque<Object> nonRepeating = new LinkedList<Object>();
 Set<Object> metSoFar = new HashSet<Object>();
 Object getLastNonRepeatCharacter(){
  if(nonRepeating.isEmpty())return null;
  return nonRepeating.getLast();
 }
 public void reset(){
  nonRepeating.clear();
  metSoFar.clear();
 }
 public void stream(Collection<Object> inStream){
  stream(inStream.stream());
 }
 public void stream(Stream<Object> inStream){
  inStream.forEach(e->{
   if(!metSoFar.add(e)){
    nonRepeating.remove(e);//this is from collection, and might be expensive and worst at O(n) depending on implementation
   }
   else
    nonRepeating.addLast(e);
  });

 }

 public static void main(String[] args) {
  SolutionObject s = new SolutionObject();
  String[] str = new String[]{"abc","bcd","cde","def","fee"};
  String[] str2 = {"abc","bcd","cde","def","fee","fee"};
  s.stream(Arrays.asList(str));
  System.out.println("test1:"+s.getLastNonRepeatCharacter());
  s.reset();
  s.stream(Arrays.asList(str2));
  System.out.println("test2:"+s.getLastNonRepeatCharacter());
 }
}

A Furniture Testing OOD

My lessons learned: do not try to surprise the other people, just model the real world in a simple way. keep the objects decoupled and cohesive.

Check if a String is Balanced on Brackets

Tried the source code beautifier and love it! For the first time, I was able to easily post Java code on blogspot. :)
The new post is a solution I gave out in a phone interview. Later I found somebody has posted similar solution on the Internet.
I felt glad to see my thoughts was so right at its first reaction.
Problem: please figure out if a given string is balanced on special brackets pairs.
the bracket pairs are () and [].
"abcdeee" is balanced.
"abc(deddd)ffsd" is balanced because ) closes (
"abc(dfsdfsd]dfsdfsd" is not balanced because ( has no closing ) and ] has no openning [
":abc([sdfdfd)]sdfdfs" is not balanced because the bracket can nest in another bracket but they can not overlap the others

Solution: using stack to check if the brackets are matching.

this code can be improved by using predefined string to compare run time string. e.g. leftB.euqals(tmp) instead of tmp.equals(leftB) to avoid null pointer exception.

static boolean isBalanced(String statement) {
         Stack<Character> sHelper = new Stack<Character>();
         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<statement.length();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;
             }
         }
         return sHelper.empty();
     }

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);

}
}