Binary Tree traversal - vertically and horizontally

Binary tree traversals are one of my favorite coding problems. They can follow into two categories: travel the tree horizontally level by level; or travel the tree vertically level by level.

For example, we have binary tree below:
     1
 2     3
4 5 6  7

horizontal traversal will output:
1
2 3
4 5 6 7

a variance of above is zig-zag traveral, which generate the below:
1
2 3
7 6 5 4

vertical traversal will output:
4
2
1 5 6
3
7

Here is the code:

/*
     * vertical traversal of binary tree
     */
    public static void verticalTraversal(Node root){
        Map<Integer, List<Node>> store = new HashMap<Integer, List<Node>>();
        verticalTraversalHelper(root, 0, store);
        int min=Integer.MAX_VALUE, max=Integer.MIN_VALUE;
        for(int k : store.keySet()){
            if(min>k)
                min = k;
            if(max<k)
                max = k;
        }
       
        for(int vLevel=min; vLevel<=max; vLevel++){
            for(Node n: store.get(vLevel)){
                System.out.print(n.data+" ");
            }
            System.out.println();
        }
    }
   
    private static void verticalTraversalHelper(Node node, int vLevel, Map<Integer, List<Node>> store){
        if(node==null)
            return;
        if(!store.containsKey(vLevel))
            store.put(vLevel, new ArrayList<Node>());
        store.get(vLevel).add(node);
       
        verticalTraversalHelper(node.left, vLevel--, store);
        verticalTraversalHelper(node.right, vLevel++, store);
       
    }
   
    /*
     * horizontally zig-zag traversal of tree
     * using 2 stacks
     */
    public static void zigZag(Node root){
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        s1.push(root);
       
        int level = 0;
        while(!s1.isEmpty()){
            while(!s1.isEmpty()){
            Node  cur = s1.pop();
            if(level%2==0){
                if(cur.left!=null)
                    s2.push(cur.left);
                if(cur.right!=null)
                    s2.push(cur.right);
            }else{
                if(cur.right!=null)
                    s2.push(cur.right);
                if(cur.left!=null)
                    s2.push(cur.left);
            }
            }
           
            level++;
            s1 = s2;
            s2 = new Stack<Node>();
        }
    }
   
    /*
     * level traversal of tree using a Queue
     */
    public void levelTraversal(Node root){
        Deque<Node> q = new ArrayDeque<Node>();
        q.add(root);
        while(!q.isEmpty()){
            Node cur = q.remove();
            System.out.println(cur.data);
            if(cur.left!=null)
                q.add(cur.left);
            if(cur.right!=null)
                q.add(cur.right);
        }
    }
  

find duplicate elements k indices away in matrix

There are two problems which are quite similar to each other.

Given an array of integer, find duplicates which are within k indices away.  See this link for reference:
http://www.geeksforgeeks.org/check-given-array-contains-duplicate-elements-within-k-distance/

Given a 2D array of integer, find duplicates which are within k indices away.

Both can be solved by using a sliding window of k indicies, maintain a hash storing the elements seen so far then check if the next element is in the hash, if not, remove the element at the start of sliding window and continue.

//for list of integers

public static boolean hasKDistanceDuplicate(int[] array, int k){

Set<Integer> store = new HashSet<Integer>();

for(int i=0, j=0; i<array.length; i++){

//maintain a sliding window of k size

while(j<array.length && j-i<=k){

if(store.contains(array[j])){

return true;

}else{

store.add(array[j]);

j++;

}

}

if(j<array.length)

store.remove(array[i]);

}

return false;

}

//for 2D matrix of integers

public static boolean determineKIndices(int[][] matrix, int k){

Map<Integer, Set<Pos>> store = new HashMap<Integer, Set<Pos>>();

for(int row=0; row<matrix.length; row++){

for(int col=0; col<matrix[0].length; col++){

int val = matrix[row][col];

if(store.containsKey(val)){

Set<Pos> set = store.get(val);

for(Pos p: set){

if(Math.abs(p.getRow() - row) + Math.abs(p.getCol()-col) <=k ){

return true;

}

      if(row - p.getRow() >k)
        set.remove(p);

}

set.add(new Pos(row, col));

}else{

Set<Pos> set = new HashSet<Pos>();

set.add(new Pos(row, col));

store.put(val, set);

}

}

}

return false;

}

Matrix rotation

There are two kinds of matrix rotation problems: one is to rotate the whole matrix clock-wise by 90 degree,

Input:
1 2 3
4 5 6
7 8 9

Output:
7 4 1
8 5 2
9 6 3

Think about the above a graph process software to rotate the pixels in an image. See this link:
http://www.programcreek.com/2013/01/leetcode-rotate-image-java/

Another way is to shift the elements clock-wise:


Input:
1 2 3
4 5 6
7 8 9

Output:
4 1 2
7 5 3
8 9 6

Here I present solutions to both:
/*
* essentially we treat elements in the matrix as circles, there are total Math.ceil(matrix.length/2) circles.
* However if matrix length is odd, the most inner circle contains one element, we don't need to rotate it.
* so we can deal with Math.floor(matrix.length/2) circles.
*/

public static void rotateMatrix(int[][] matrix){

int num = matrix.length;

for(int i=0; i<num/2; i++){

for(int j=i; j<num-i-1; j++){

int temp = matrix[i][j];

matrix[i][j] = matrix[num-j-1][i];

matrix[num-j-1][i] = matrix[num-i-1][num-j-1];

matrix[num-i-1][num-j-1] = matrix[j][num-i-1];

matrix[j][num-i-1] = temp;

}

}

for(int i=0; i<num; i++)

System.out.println(Arrays.toString(matrix[i]));

}

/*

 * shifting is similar above, we shift Math.floor(matrix.length/2) circle one by one

 */

public static void rotateMatrixByShiftElements(int[][] matrix){

int num = matrix.length;

for(int i=0; i<num/2; i++){

int start = matrix[i][i];

//shift up on column i

for(int row=i; row<num-i-1; row++){

matrix[row][i] = matrix[row+1][i];

}

//shift left on row num-i-1

for(int col=i; col<num-i-1; col++){

matrix[num-i-1][col] = matrix[num-i-1][col+1];

}

//shift down on column num-i-1

for(int row=num-i-1; row>i; row--){

matrix[row][num-i-1] = matrix[row-1][num-i-1];

}

//shift right on row i

for(int col=num-i-1; col>i; col--){

matrix[i][col] = matrix[i][col-1];

}

//the last one!

matrix[i][i+1] = start;

}

for(int i=0; i<num; i++)

System.out.println(Arrays.toString(matrix[i]));

}

Thoughts on foundational framework development

Foundational framework development is very important in any technology companies. It solves common problems shared across departments, teams or projects. It generally is lauded by management. Many great open-source frameworks, e.g. AngularJS, React, I believe, are stemmed from in-house framework development then taken from companies like Google and Facebook to public.

There are two schools of thoughts to develop foundational frameworks: bottom-up or top-down. Bottom-up approach is to build it prior to any applications by foreseeing and analyzing various potential needs of applications, finding the common area then developing it. Sometimes the analysis phase becomes a bit of guessing work and shot in the dark. And at organizational level if there is division between foundational team and application team, it could makes this approach even harder. However this approach fits well to develop a well-defined public API or standard like JDBC driver for an in-house database.

Top-down approach is more practical, teams, without the division of foundational team and application team, start to build the applications to meet business needs and both with well-defined architectures. During the course of development teams start to discover the relationship between difference layers and modules, continue to refine the architecture and code-base. At the end of project or even after project delivery teams set out to refactor and harvest a framework from the applications. This approach usually has grounded success since it is based on real-life applications to solve real problems. Also this approach is well aligned with refactoring and iterative agile development.

The following diagrams further illustrate my thoughts above:

The bottom-up approach tends to assume the interfaces between foundation layer and applications are well-defined or the boundaries can be easily discovered.

 

However in reality, the picture looks more like this:

 

 So bottom-up approach ends up like this: 

 

What happens above is that application logics are everywhere in the foundation layer. In the code we see lots of if/else, case/switch statements, and any changes in foundation layer to accommodate one application will impact other applications.  That foundational layer eventually becomes a monolithic application.

So what is best way to develop foundation layer? Based on my experiences, there are few OO design principles and patterns can greatly help us.

1. Foundational interfaces should be minimum. Try not solve everything, leave as much as you can to application unless you are sure the functionality is needed. Develop a toolkit not a specific problem solver.Using java's java.util.List as example, it provides a method called get(index) and doesn't provide method getFirst() or getLast() since it leaves the clients to do that. In that way you leave the client assembles the jdk methods to any requirement it may need to accomplish.

1. Close to change, open to extension.

2. Dependency injection (IoC) or Hollywood principle  - Don't call me, I call you.

3. Develop pluggable interfaces.

Generics related design patterns: part I

Generics, introduced in Java 6, is one of the powerful features in Java to help developer to better design class and method, enabling type safety and compiling time check.

Here I introduced couple useful generics related design patterns.

1. typesafe hetergenous map, as described in book "Effective Java"

Mostly of time map contains certain type of keys and values, unless you create object as key or values, but if you do that, you lose the control of type checking. Using class literal introduced Java 5, we can create typesafe map. Here is the implementation:

/*

 * Typesafe container pattern

 */

public class TypeContainer {

Map<Class<?>, Object> map = new HashMap<Class<?>, Object>();

public <T> void put(Class<T> key, T instance){

map.put(key, instance);

}

public <T> T get(Class<T> key){

return key.cast(map.get(key));

}

}

2. Generified singleton pattern

We know the singleton holder pattern which is thread-safe way to create singleton. So how we can create generified singleton?

The idea is to created a typesafe container to hold all of the potential singleton instances. Note this is not a clean way.

/* 

 * generic singleton pattern

 */

public final static class Singleton<T> {

private Singleton(){}

public Singleton<T> getInstance(Class<T> type){

        // check if type is supported if does then return the singleton

return (Singleton<T>)(SingeltonHolder.store.get(type));

}

private final static class SingeltonHolder {

private static final Map<Class<?>, Singleton> store = new HashMap<Class<?>, Singleton>(){{

put(String.class, new Singleton<String>());

put(Integer.class, new Singleton<Integer>());

                        //add all of the supported types here

}};

}

}

3. Generic singleton factory pattern

/*

 * generic singleton factory pattern 

 */

public interface MyInterface<T> {
   T doSomthing(T arg);
}

public static class GenericFactory {

public static <T> MyInterface<T> getImpl() {
return (MyInterface<T>)IMPL;
}

/* here we only need one generic implementation */

private static final MyInterface<Object> IMPL = new MyInterface<Object>() {

@Override

public Object doSomthing(Object arg) {
return arg;
}
};
}

Immutable vs Unmodifiable

Immutable is one of the most important programming language concepts. Immutable is an read-only object which can not be changed, if there is any changes, a new copy will be created with updated version. internally the object state can be altered but the changes won't be reflected from the outside.

Most of immutable are value object to represent a certain business domain. Unmodifiable, is "read-only view" of the object. Similar to immutable it can not be changed from outside, but internally the object state can be altered and the changes can be reflected on the view.

In the Java Collection tutorial, one of the way to create immutable object is to construct one without reference to it, so it can't be changed.

In classic "effective java" book, it presents 5 rules to create immutable class:
1. don't provide methods to change object state. This is how JDK's Collections.unmodifiable does.
2. all fields are final
3. all fields are private
4. class can't be subclassed, either by declared it final or don't provide public/protected constructor.
5. exclusive access to object mutable state.

Immutable is particularly useful in concurrent programming since it is thread-safe. In Java and many other languages as well, String, Float, Double and Integer are immutable.

Here are two unit test cases to demonstrate the immutable and unmodifiable.

@Test

public void unmodifiableTest(){

List<String> modifiable = new ArrayList<String>();

modifiable.add("1");

List<String> unmodifiable = Collections.unmodifiableList(modifiable);

assertTrue("should have the same size", modifiable.size() == unmodifiable.size());

modifiable.add("2");

assertTrue("should still have the same size", modifiable.size() == unmodifiable.size());

try{

unmodifiable.add("3");

assertTrue("should not succeed", false);

}catch(UnsupportedOperationException ex){

assertTrue("should throw exception", true);

}

assertTrue("should still have the same size", modifiable.size() == unmodifiable.size());

}

@Test

public void immutableTest(){

List<String> modifiable = new ArrayList<String>();

modifiable.add("1");

List<String> immutable = Collections.unmodifiableList(new ArrayList<String>(modifiable));

assertTrue("should have the same size", modifiable.size() == immutable.size());

modifiable.add("2");

assertTrue("should no longer have the same size", modifiable.size() != immutable.size());

try{

immutable.add("3");

assertTrue("should not succeed", false);

}catch(UnsupportedOperationException ex){

assertTrue("should throw exception", true);

}

}

group sort

This post is responding to my friend Li Peng's page. http://allenlipeng47.com/PersonalPage/index/view/173/nkey

Given an array of string, and sequence. Sort the array according to the given sequence.
For example:
String str = "DCBAEECCAAABBAEEE"; String sequence = "ABCDE";
output should be: AAAAABBBCCCDEEEEE

The counting sort like sort algorithms are the ones can be done in O(n).

public static char[] sort(char[] strs, char[] comp){

char[] sorted = new char[strs.length];

int[] count = new int[256]; 

for(char s : strs){

count[s]++;

}

int index = 0;

for(char c : comp){

int num = count[c];

while(num-->0)

sorted[index++] = c;

}

return sorted;

}

if it is required to sort in place:

public static char[] sort(char[] strs, char[] comp){

int[] count = new int[256]; 

for(char s : strs){

count[s]++;

}

int index = 0;

for(char c : comp){

int num = count[c];

while(num-->0)

strs[index++] = c;

}

return strs;

}

Sort the Double linked list in place:

/*

* in place sort DLL of Rs, Gs and Bs, so that Rs in front, followed by Gs and Bs

* assume DLL has the sentinel node to separate the head and tail

*/

public static void sortDLL(DLL head, DLL sentinel){
final char[] setOfChars= new char[]{'R', 'G', 'B'};

DLL curr, p;
curr = p = head;

//push all R to the front

while(p != sentinel){
if(p.data == 'R'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}

 

curr = p = head.pre.pre;

//push all B to the back

while(p != sentinel){
if(p.data == 'B'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.pre;
}
p = p.pre;
}
}

How about Singled LinkedList?

//here I use DLL node to represent the SLL

//in this case DLL.pre = null

void sortSLL(DLL head){
DLL curr = head, p = head;

//push all Rs to the front

while(p != null){
if(p.data == 'R'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}

//now all Rs at front and curr points at candidate 

//position for next char which is G

//push all Gs to the front

p = curr;
while(p != null){
if(p.data == 'G'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}
}