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:

We use backtracking to identify the elements not surrounded by 'X' and we mark those with a temporal symbol ('$'). The elements not surrounded by 'X' means that exists a path of elements 'O' to a border. So we start the backtracking algorithm with the boarders.

The last thing is replacing the temporal element by 'O' and the rest elements to 'X'.

We have used a non-recursive implementation of backtracking, using a stack. This implementation is more efficient in space. For instance, this algorithm in its recursive implementation does not pass the test due to overflowing the stack.

public class Solution {
    final static char TEMPORARY_MARKED ='$';
    final static char TO_CAPTURE = 'O';
    final static char CAPTURED ='X';
    
    public void solve(char[][] board) {
        if(board.length ==0 )
              return;
        int numberRows = board.length;
        int numberCols = board[0].length;
        for(int col=0; col<numberCols; col++)
        {
            mark(board,0,col);
            mark(board,numberRows-1,col);
        }
        for(int row=0; row<numberRows; row++)
        {
            mark(board,row,0);
            mark(board,row,numberCols-1);
        }
        
        for(int row=0; row<numberRows; row++)
        {
            for(int col=0; col<numberCols; col++)
            {
                board[row][col]= board[row][col]==TEMPORARY_MARKED ? TO_CAPTURE : CAPTURED;
            }
        }
    }
    
    public void mark(char[][] board, int row, int col)
    {
        int position = row*board[0].length + col;
        ArrayDeque<Integer> stack = new ArrayDeque<Integer>();
        stack.push(position);
        while(!stack.isEmpty())
        {
            position = stack.pop();
            row = position / board[0].length;
            col = position % board[0].length;
            if( board[row][col] != TO_CAPTURE)
                continue;
            board[row][col] = TEMPORARY_MARKED;
            if (row>0)
                stack.push((row-1)*board[0].length + col);
            if (col>0)
                stack.push(row*board[0].length + col-1);
            if (row<board.length-1 )
                stack.push((row+1)*board[0].length + col);
            if (col<board[0].length-1 )
                stack.push(row*board[0].length + col+1);
        }
    }
}

Leetcode: Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree

   1
    \
     2
    /
   3

return [1,2,3].

Solution 1:

We want to implement this algorithm using constant extra space,  i.e.,  we cannot use recursion or a stack to keep the parent node.

Modifying the original tree
Creating threaded links to the next node to be processed and as the tree can be modified, there is not need to remove them.

We show an example of the algorithm in the next figure, where the dotted lines show the false links used to traverse the tree.

public class Solution {

    public ArrayList<Integer> preorderTraversal(TreeNode root) {

        ArrayList<Integer> solution = new ArrayList<Integer>();

        TreeNode current, temp;

        current=root;

        while(current != null)

        {

            solution.add(current.val);

            if(current.left == null)

            {

                current = current.right;

            }

            else

            {

                temp = current.left;

                while(temp.right != null && temp.right != current)

                    temp=temp.right;

                if(temp.right == null)

                {

                    temp.right = current.right;

                    current = current.left;

                }

                else

                //temp == current (We already have processed the left tree)

                {

                    temp.right = null; //We remove the threading links

                    current = current.right;

                }

            }

        }

        return solution;

    }

}

Solution 2 Without modifying the original tree
In this case we have to use threaded trees (http://en.wikipedia.org/wiki/Threaded_binary_tree).

The links marked are removed after traversing the links.

public class Solution {

    public ArrayList<Integer> preorderTraversal(TreeNode root) {

        ArrayList<Integer> solution = new ArrayList<Integer>();

        TreeNode current, temp;

        current=root;

        while(current != null)

        {

            if(current.left == null)

            {

                solution.add(current.val);

                current = current.right;

            }

            else

            {

                temp = current.left;

                while(temp.right != null && temp.right != current)

                    temp=temp.right;

                if(temp.right == null)

                {

                    solution.add(current.val);

                    temp.right = current.right;

                    current = current.left;

                }

                else

                {

                    temp.right = null; //We remove the threading links

                    current = current.right;

                }

            }

        }

        return solution;

    }

}

Leetcode: Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Solution:

This problem's solution is straightforward, only having to be careful to check that you have not arrived to an end of a list. We reuse the nodes to create the solution in order to use constant space.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null)
            return l2;
        if(l2==null)
            return l1;
        int carryOn = (l1.val + l2.val)/10;
        int sum;
        l1.val = (l1.val + l2.val)%10;
        ListNode temp = l1;
        while(temp.next != null && l2.next != null)
        {
            sum = carryOn;
            sum += temp.next.val;
            sum +=  l2.next.val;
            temp.next.val = sum % 10;
            carryOn = sum / 10;
            temp = temp.next;
            l2 = l2.next;
        }
        if(temp.next==null)
            temp.next = l2.next;
        while(temp.next != null)
        {
            sum = carryOn;
            sum += temp.next.val; 
            temp.next.val = sum % 10;
            carryOn = sum / 10;
            temp = temp.next;
        }
        if (carryOn != 0)
            temp.next = new ListNode(carryOn);
        return l1;
    }
}

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.

Our solution

Our algorithm is based on two pointers, denoted by pointerEnd and pointerBegin, Both pointers traverse the list distanced by n elements. When the pointerEnd reaches the last element, the pointerBegin points to the previous element than the one to remove.
Again, we use the trick of a dummy node at the beginning so the algorithm is identical for all the cases and we remove it at the end.

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode head2 = new ListNode(0);
        head2.next = head;
        ListNode pointerEnd = head2, pointerBegin = head2;

        // We advance pointerEnd n positions
        for(int i=0; i<n; i++)
            pointerEnd = pointerEnd.next;

        //We advance both elements at the same speed
        while(pointerEnd.next != null)
        {
            pointerBegin = pointerBegin.next;
            pointerEnd = pointerEnd.next;
        }

        pointerBegin.next=pointerBegin.next.next;
        return head2.next;
    }
}

Leetcode: Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Solution:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode list = dummy;
        ListNode pointer= head;
        while(pointer != null )
        {
            if(pointer.next != null && pointer.val == pointer.next.val)
            {
                int value = pointer.val;
                while(pointer!=null && pointer.val == value)
                    pointer = pointer.next;
            }
            else
            {
                list.next = pointer;
                list = list.next;
                pointer = pointer.next;
            }
        }
        list.next = null;
        return dummy.next;
        
    }
}

Leetcode: Length of last word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example, 
Given s = "Hello World",
return 5.

Our solution:

We base our solution on a DFA with two states:

and we present the input in reverse order, to get the last word length.

The code assuming that the input contains only letters and spaces as mentioned is:

public class Solution {
    public int lengthOfLastWord(String s) {
        int count = 0;
        int state = 0;
        for(int i = s.length()-1; i>=0; i--)
        {
            switch (state)
            {
                case 0: if(s.charAt(i) != ' ')
                        {
                            state = 1;
                            count++;
                        }
                        break;
                case 1: if (s.charAt(i) != ' ')
                            count++;
                        else
                            return count;
            }
        }
        return count;
    }
}

Leetcode: valid number

Validate if a given string is numeric.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true

Our solution:

This problem deals with a common problem in compilers in the lexical analysis, i.e.  knowing if a certain string is a valid token.

We accept the following regular grammar, shown as UNIX regular expression by simplicity:
\s*[\+\-]?(([0-9]+(\.[0-9]*)?)|\.[0-9]+)([eE][+-]?[0-9]+)?\s*
where \s represents [ \t].

This regular expression is accepted by the underneath DFA(Deterministic Finite Automata):

where any transition not shown takes to an error state, that in the code is represented by -1.

public class Solution {
    public boolean isNumber(String s) 
    {
        int state = 0;
        for(int i=0; i<s.length();i++)
        {
            state=getNextState(state, s.charAt(i));
            if (state==-1)
                return false;
        }
        state = getNextState(state, ' ');
        return state == 8;
    }
    
    private int getNextState(int state, char c)
    {
        int[][] transitionTable = { {0,2,1,3,-1,-1},
                                    {-1,2,-1,3,-1,-1},
                                    {8,2,-1,4,5,-1},
                                    {-1,4,-1,-1,-1,-1},
                                    {8,4,-1,-1,5,-1},
                                    {-1,7,6,-1,-1,-1},
                                    {-1,7,-1,-1,-1,-1},
                                    {8,7,-1,-1,-1,-1},
                                    {8,-1,-1,-1,-1,-1}};
        return transitionTable[state][getSymbol(c)];
    }
    
    private int getSymbol(char c)
    {
        switch(c)
        {
            case ' ': case '\t': return 0;
            case '0': case '1': case '2':case '3': case '4': case '5': case '6': case '7': case '8': case '9': return 1;
            case '+': case '-': return 2;
            case '.': return 3;
            case 'E': case 'e': return 4;
            default: return 5;
        }
    }
}

More information:
[1, Chapter 1] J. Glen Brookshear, "Theory of Computation: Formal Languages, Automata, and Complexity", Addison-Wesley.

[2, Chapters 2-3] Rajeev Motwani, Jeffrey Ullman, and John Hopcroft, "Introduction to Automata Theory, Languages, and Computation", Addison-Wesley.

Mapreduce

Due to the need of huge capture files from CAIDA (hundreds of Gigabytes) for my research, I decided to create a cluster and use a Map-Reduce programming model, namely I use Hadoop.

Installing hadoop
The first step is installing Hadoop (I found useful the following tutorials):
https://hadoop.apache.org/docs/r1.2.1/single_node_setup.html
https://hadoop.apache.org/docs/r1.2.1/cluster_setup.html
http://www.michael-noll.com/tutorials/running-hadoop-on-ubuntu-linux-multi-node-cluster/


HDFS
Then we create a HDFS system with two folders, input and output, and we upload the files to process into the input folder.

someone@anynode:hadoop$ bin/hadoop dfs -ls
Found 2 items
drwxr-xr-x   - username supergroup          0 2013-12-22 12:51 /user/username/input
drwxr-xr-x   - username supergroup          0 2013-12-22 12:50 /user/username/output

More info: http://developer.yahoo.com/hadoop/tutorial/module2.html

The input to our program, after preprocessing, are a file:
132.156.180.68 22 146.25.6.199 33980 1070631061.367672000

Map Reduce (number of packets):
We start with an easy program to know the number of packets each server receives and sends.

We develop a custom key class to pass from the map to the reduce. This class has to implement WritableComparable. (cf. [1, Example 4.7] or http://developer.yahoo.com/hadoop/tutorial/module5.html)

Code coming pretty soon.



Reference guide for me:
[1] Tom White, "Hadoop: The Definitive Guide", O'Reilly

Bash Scripting

Bash Scripting Tutorials and Exercises:

Are you willing to learn bash scripting? This post will be used to post my recommendations.

Basic:
http://www.tldp.org/LDP/Bash-Beginners-Guide/html/
http://www.freeos.com/guides/lsst/ch08.html

A bit more advanced:
http://tldp.org/LDP/abs/html/index.html