Cycle Detection in LinkedList

Say, we have a linked list
    6->8->9->10->4->3->10.....

If last but one node points to 10, then we will end up in an infinite loop.
So the question here is - how to detect this cycle.

This can be identified using the Floyd Cycle detection algorithm.

http://en.wikipedia.org/wiki/Cycle_detection 

This algorithm is also known as Tortoise and Hare algorithm, In this we will have two references, one reference jumps to one position and other one jumps to 2 positions, we do this continuously until we iterate all the elements from both the references or if both the reference points to same node, In each iteration we will compare the node value from reference one and two.

Below is the simple java code to find the cycle detection.

Here we have introduced two references
first and second,  
Iteration 1, first -> 6, second ->8
Iteration 2, first -> 8, second ->10
Iteration 3, first -> 9, second ->3
Iteration 4, first -> 10, second ->4
Iteration 5, first -> 4, second ->10
Iteration 6, first -> 3, second ->3

At iteration 6, both the node values will be equal and we stop the iteration.

 


 
     public static boolean isCyclic(LinkedList list) {
        LinkedList.Node first = list.head(); // get the head node
        LinkedList.Node second = list.head.getNext(); // get the second node
       
        while(true) {
            if(first !=null && second != null && first.getData() != null && second.getData() !=null) {
                if(first.getData().equals(second.getData())) {
                    return true;
                } else {
                    first = first.getNext();
                    if(second.getNext() != null)
                        second = second.getNext().getNext();
                    else
                        second =  null;
                }
            } else
                return false;
        }
    }

How to Merge two sorted arrays in O(n) time

Assume that we have two sorted arrays and we want to merge both the arrays efficiently into a single sorted array.

The algorithm we are going to use is - kind of DB sort merge Join algorithm.

While joining 2 tables in DB, DB sorts both the tables first and compare against the join columns.

For example, If we have two tables, Table A and Table B.

For simplicity, let us take only two columns.

empid	name
1	AAA
2	BBB
3	CCC
4	DDD
5	EEE
6	FFF

empid	ADDRESS
2	AAA
4	BBB
6	CCC

If we want to join these two tables using empid, then one among the DB join algorithm is Merge Join algorithm.

DB sorts these two tables using the join columns, In this case it would be empid.

It compares table 1 and table 2's empid.
Initially we start iterating each row, If the value of first table <  value of second table, then we ignore this row, Then we will iterate the next row only from first table.
Now we compare second row's value of first table against the first row value of second table, Bot matches it outputs this row.
Next we start iterating third row, Now if the value of first table > value of second table then we will start iterating from second table and continue the comparision.

In general, Initially we start with both the tables, After the comparison we will decide which table we want to iterate next, If left table value is smaller then we will iterate left table, If the right table value is small, we will iterate the right table. It continues until one among the table is iterated completely.


===============================================

The same principle applies to merge the sorted rows into a single sorted row.

Assume that we have the following arrays.

A = {1, 4, 6, 8, 10 }
B = { 2, 3, 5, 9 }


Now we want to merge these two arrays.

We start iterating both the arrays with two different variables, i and j refers to A and B.
Create an empty array with the length of (sum(Length A, Length B)).

If i < j then
start iterating values from B, add i to the new array then increment i.
else
start iterating values from B, add j to the new array then increment j.
Continue the iteration until i<A.length or j<B.length.

Now do the individual iterations of A and B seperately.
A:
Iterate until i<A.length.
    Get the element and add it to new Array.
B:

Iterate until j<B.length.
    Get the element and add it to new Array.

The Java code for this algorithm is given below.

In the example mentioned above, the first while loop would iterate for 8 times, second while loop iterate for 1 time, third for none, because of Length of B < Length of A.

The below code would complete the operation in O(n).



private static int[] merge(int[] a, int[] b) {
        int[] c = new int[a.length+b.length];
        int i=0, j=0;
        int k=0;
   
        while(i<a.length && j<b.length) {
            if(a[i]<=b[j]) {
                c[k] = a[i];
                i++;
            } else {
                c[k] = b[j];
                j++;
            }
            k=k+1;
        }
   
        while(i<a.length) {
            c[k] = a[i];
            i++;
            k=k+1;
        }

        while(j<b.length) {
            c[k] = b[j];
            j++;
            k=k+1;
        
        }
        System.out.println(k+"**********");
        return c;
    }

Adding Two Numbers using Linked List

In this blog, we will see adding two numbers using a LinkedList with the time complexity of O(n).

Represent both the numbers using Linked List in the reverse order.
For example, if we want to add two numbers

1234 +46 = 1280

LinkedList 1 would represent the values in the form of 4->3->2->1
LinkedList 2 would represent the values in the form of 6 -> 4

The resultantList will have the value as 1->2->8->0
  

The below code would iterate both the linkedlist as the same time.
Here is the algorithm.

1. Get the reference of both the LinkedList's head node and declare a flag to Identify whether the sum has 2 digits.
Iterate until node1.getData is not null or  node2.getData is not null

2. Get the values associated to the node and store it in a different variables.

3. Add both the values
4. For the first iteration, carried flag will be false.
       From second iteration onwards, this flag might be true depending upon the carried number, If we add 8 + 4, the carried number will be 1 here.
      If we have carried number then
           a. Get the head node value
           b. add it to the sum.
           c. remove the head node.
           d. Mark the carried flag as false.

5. If the number of digits is 2
    a)      then split the digits as ones and tens.
        For example if the sum is 12
          ones -> 2
          tens -> 1
        
        Add ones and tens to the resultant List
Such that the resultantList head always holds the value of the carried over number, In this case the head will have the value as 1, the subsequent node will have the value as 2.

    b.  If the sum value is single digit then
         Add the value to the resultant Linked List.

6. Traverse to the next node from List1 and List2, so that node1 -> node1.next, node2 -> node.next
7. Repeat the steps until both the list are completely traversed.
             

The below java code, iterates all the nodes in the list only one time, so we get the O(n) complexity.
The code inside the while loop are all constant time operations.

public static LinkedList add(LinkedList list1, LinkedList list2) {

        Node node1 = list1.head;

        Node node2 = list2.head;

        LinkedList returnList = new LinkedList();

        boolean isCarried = false;

        while((node1 != null && node1.getData() !=null) || (node2 !=null && node2.getData() != null)) {

            int k=0;

            int l=0;

            if(node1 != null && node1.getData() !=null) {

                k = Integer.valueOf(node1.getData());

            }

            if(node2 != null && node2.getData() !=null) {

                l = Integer.valueOf(node2.getData());

            }

            int m = k + l;

            if(isCarried) {

                isCarried = false;

                m += Integer.valueOf(returnList.head.getData());

                returnList.remove(0);

            }

            String value = String.valueOf(m);

            if(value.length()==2) {

                returnList.add(0, value.substring(1));

                returnList.add(0, value.substring(0,1));

                isCarried = true;

            } else {

                returnList.add(0, value);

            }

            if(node1 != null) {

                node1 = node1.getNext();

            }

            if(node2 != null) {

                node2 = node2.getNext();

            }

        }

        return returnList;

    }

HashMap Implementation in Java

HashMap is a data structure used to store the key value pairs.
It uses the hash function for mapping the keys to values.

For More Info,Refer the wiki page.
en.wikipedia.org/wiki/Hash_table

Here I've given a sample implementation in Java.

Given very basic implentation which uses the simple collision avoiding technique known as Horizontal Chaining with list heads.

Binary Tree Implementation in Java

Binary Tree:

A binary tree is a tree data structure  in which every node has at most two children usually left and right node.
left node < parent node < right node

Binary tree gives the best case performance of O(log n) and the worst case performance of  0(n), meaning if the inputs are given in sorted sequence then the binary tree representation would be in the form of Linked List, and which is of O(n) complexity.

Binary Tree can be traversed by

Depth First Traversal(In Order, Pre Order and Post Order)
Breadth First Traversal.

DepthFirst uses Stack as Datastructure and the Breadth First uses Queue as the data structure.

The implementation is given below.

For more information please refer to

http://en.wikipedia.org/wiki/Binary_Tree
en.wikipedia.org/wiki/Tree_traversal



import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * This class is a sample implementation of Binary Tree and its traversals
 * @author hbalakrishnan
 *
 */

public class BinaryTree {
    /**
     *
     * Just a static class Node, which holds it value
     * and references to left and right nodes
     *
     */
    static class Node {
        private Node left;
        private Node right;
        private int value;
       
        public List<Node> getChildren() {
            List children = new ArrayList<Node>();
            if(left != null)
                children.add(left);
           
            if(right != null)
                children.add(right);
           
            return children;
        }
       
        public Node(int value) {
            this.value = value;
        }
    }
   
    public static void main(String[] args) {
        Node rootNode = new Node(50);
        insert(rootNode, 11);
        insert(rootNode, 15);
        insert(rootNode, 17);
        insert(rootNode, 51);
        insert(rootNode, 71);
        insert(rootNode, 61);
        System.out.println("In Order Traversal");
        printInOrder(rootNode);
//        System.out.println("Pre Order Traversal");
//        printPreOrder(rootNode);
//        System.out.println("Post Order Traversal");
//        printPostOrder(rootNode);
       
        //bfs(rootNode);
    }
    /**
     * Method to insert the node in the form of binary tree which satisfies the below condition
     * If value is less than node.value, insert left
     * If value is greater than node.value, insert right
     * @param p
     * @param value
     */
   
    public static void insert(Node p, int value) {
        // insert at left
        if(value < p.value) {
            if(p.left != null) {
                insert(p.left, value);
            } else {
                System.out.println("Node inserted with value:"+value
                        +" to the left of::"+p.value);
                Node newNode = new Node(value);
                p.left = newNode;
            }
        }
       
        // insert at right
        if(value > p.value) {
            if(p.right !=null) {
                insert(p.right, value);
            } else {
                System.out.println("Node inserted with value:"+value
                        +" to the right of::"+p.value);
                Node newNode = new Node(value);
                p.right = newNode;
            }
        }
       
    }
   
    /**
     * In order traversal
     * Traverse left, root and right
     * It is a kind of DFS, which traverses the left node first until it reaches the depth, then root
     * Finally it traverses the right node
     * Outcome of the traversal would be in sorted sequence
     * @param node
     *
     * [Result: 11, 15, 17, 50, 51, 61, 71]
     */
   
    public static void printInOrder(Node node) {
       
        if(node != null) {
            printInOrder(node.left);
            System.out.println("In Order Node traversed ::"+node.value);
            printInOrder(node.right);
        }
    }
   
    /**
     * Pre order traversal
     * Traverse root, left and right
     * It is a kind of DFS, which traverses the root node, left and right node
     * @param node
     */
   
    public static void printPreOrder(Node node) {
        //ssSystem.out.println("Pre Order Traversal");
        if(node != null) {
            System.out.println("Pre Order Node traversed ::"+node.value);
            printPreOrder(node.left);
            printPreOrder(node.right);
        }
    }
   
    /**
     * Post order traversal
     * Traverse  left, right and root node
     * It is a kind of DFS, which traverses the  left ,  right node and root node
     * @param node
     */
   
    public static void printPostOrder(Node node) {
        //System.out.println("Post Order Traversal");
        if(node != null) {
            printPostOrder(node.left);
            printPostOrder(node.right);
            System.out.println("Post Order Node traversed ::"+node.value);
        }
    }
   
    /**
     * This uses the the simple DFS algorithm which uses stack as the Datastructure
     * without recursion
     * dfs
     * @param rootNode
     */
   
    public static void dfs(Node rootNode) {
        Stack<BinaryTree.Node> stack = new Stack<BinaryTree.Node>();
        stack.push(rootNode);
        //System.out.println("Visited Node::"+rootNode.value);
        while(!stack.isEmpty()) {
            Node workNode = stack.pop();
            System.out.println("Visited Node::"+workNode.value);
            for(int j =0; j<workNode.getChildren().size(); j++) {
                Node childNode = workNode.getChildren().get(j);
                if(childNode.getChildren() == null) {
                    System.out.println("Visited Node::"+childNode.value);
                } else {
                    stack.push(childNode);
                }
            }
        }
    }
   
   
    /**
     * This uses the the simple BFS algorithm which uses queue as the Datastructure
     * Here I have used LinkedList to represent Queue
     * without recursion
     * bfs
     * @param rootNode
     */

    public static void bfs(Node rootNode) {
        LinkedList<BinaryTree.Node> queue = new LinkedList<Node>();
        queue.add(rootNode);
        System.out.println("Visited Node::"+rootNode.value);
        while(!queue.isEmpty()) {
            Node workNode = queue.remove();
            //System.out.println("Visited Node::"+workNode.value);
            for(int j =0; j<workNode.getChildren().size(); j++) {
                Node childNode = workNode.getChildren().get(j);
                System.out.println("Visited Node::"+childNode.value);
                queue.add(childNode);
            }
        }
    }
   

}