Coins in a line

This problem is from leetcode: http://articles.leetcode.com/2011/02/coins-in-line.html.

Number of coins lined up, two persons take turn to pick up coins from both ends, what is the maximum total sum of money first person can pick?

Many of the gaming type problems can be solved by dynamic programming. Say DP[i, j] presents the maximum value one person can gather if he/she is presented with coins from position i to j. The final answer will be DP[0][numofcoin-1].

When person presented with coins from i to j, he/she can either pick coin at i or j, after that, second person will pick the coins and we will assume second person is smart and will always make best move, that is, will minimize the first person can gain on the next step:

So we have the following formula for dynamic programming: 
DP(i,j) = Max(
         *     Min(DP(i,j-2), DP(i+1,j-1))+coins[j],
         *     Min(DP(i+2,j), DP(i+1,j-1))+coins[i])


Here is the code:

public static int coinsInALine(int[] coins){
        //assume we have more than 4 coins, otherwise the problem becomes too easy
        /*
         * DP(i,j) = Max(
         *     Min(DP(i,j-2), DP(i+1,j-1))+coins[j],
         *     Min(DP(i+2,j), DP(i+1,j-1))+coins[i])
         */
        int[][] table = new int[coins.length][coins.length];
        int[][] moves = new int[coins.length][coins.length];
        for(int i = 0; i<coins.length; i++){
            table[i][i] = coins[i];
            moves[i][i] = i;
        }
      
        for(int i=0; i<coins.length-1; i++){
            table[i][i+1] = Math.max(coins[i], coins[i+1]);
            moves[i][i+1] = coins[i] > coins[i+1]? i : i+1;
        }
      
        for(int step = 2; step<coins.length; step++){          
            for(int i=0; i+step<coins.length; i++){
                int a = coins[i+step] + Math.min(table[i][i+step-2], table[i+1][i+step-1]);              
                int b = coins[i] + Math.min(table[i+2][i+step], table[i+1][i+step-1]);
                table[i][i+step] = Math.max(a, b);  
                moves[i][i+step] = a > b? i+step : i;
            }
        }
      
        int i=0, j=coins.length-1;
        while(i<j){
            System.out.println("move: " + moves[i][j]);
            if(moves[i][j] == i)
                i++;
            else
                j--;
        }
        System.out.println("done");
        return table[0][coins.length-1];
    }

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.