Sort A linked List with N numbers. Range of Numbers in ( 0, 1, 2 )

Sort a Linked List with N numbers. Range of Numbers in this Linked List in ( 0, 1, 2 )

For exmaple:

A Linked List with numbers : { 0, 0, 1, 2, 2, 1, 1, 0, 0, 1, 2 } OR { 2,0, 0, 1, 2, 2, 1, 1, 0, 0, 1, 2 }, etc

Below is the Program to sort this:

public class SortALinkedList {

    public Link sort(Link head) {
     

        if (head == null)
            return head;
        if (head.next == null)
            return head;

        Link k = head;
        Link _0 = null;
        Link _1 = null;

        if (head.value() == 0)
            _0 = k;
        else if (head.value() == 1)
            _1 = k;

        Link iter = head.next;
        Link iter_before = head;

        while (iter != null) {

            if (iter.value() == 2) {
                iter_before = iter;
                iter = iter.next;
                continue;
            }

            Link p = iter;
            iter = iter.next;
            iter_before.next = iter;

            if (p.value() == 1) {

                if (_1 == null) {
                    _1 = p;

                    if (_0 != null) {
                        p.next = _0.next;
                        _0.next = p;
                    } else {
                        p.next = head;
                    }
                } else {
                    p.next = _1.next;
                    _1.next = p;
                }

            } else if (p.value() == 0) {

                if (_0 == null) {
                    _0 = p;
                    p.next = (_1 == null ? head : _1);
                } else {
                    p.next = k;
                }
                k = p;
            }

        }

        return k;
    }

    public static void main(String[] args) {

        int[] arr0 = new int[] { 0, 0, 1, 2, 2, 1, 1, 0, 0, 1, 2 };
       
        int[] arr1 = new int[] {  1,0, 2, 2, 1, 1, 0, 0, 1, 2 };
       
        int[] arr2 = new int[] { 2,1, 0, 1, 2, 2, 1, 1, 0, 0, 1, 2 };
       
        int[] arr3 = new int[] { 2,0, 0, 1, 2, 2, 1, 1, 0, 0, 1, 2 };
       
        int[] arr4 = new int[] { 2,2,0, 0, 1, 2, 2, 1, 1, 0, 0, 1, 2 };
       
        int[] arr5 = new int[] {  1, 1, 0, 2, 2, 1, 1, 0, 0, 1, 2 };
       
        Link head = Link.build(arr0);

        SortALinkedList srt = new SortALinkedList();
        Link k = srt.sort(head);

        k.print(k);
   
    }

}

Eclipse Remote Debugging:

Failed to connect to remote VM. Connection timed out

 

The above error is the most frequently encountered by Developers working with different eclipse version.

It is almost too irritating all to get this error and spend a substantial portion of the day debugging it.

Some things to try to get past this error:

1. First check the network connection settings ( Assuming you can ping to the remote machine successfully )

Go to Window -> Preferences -> General -> Network Connections, and check if there is any proxy set here, change the 'Active Provider' to be 'Direct' and try again

For more see the below link:

http://stackoverflow.com/questions/9034147/getting-launch-error-failed-to-connect-to-remote-vm-connection-timed-out-whic

2. Increase the Debug timeout paramters:

http://stackoverflow.com/questions/5990438/eclipse-remote-debug-timeout-problem

3. Check the remote server Debug settings:

My Java debug options configured on the remote server:

set "JAVA_OPTS=%JAVA_OPTS% -Xrunjdwp:transport=dt_socket,address=8788,server=y,suspend=n"

where 8788 is the port to connect to for remote debugging.

This port, 8788 must be provided in the ecliipse settings

See this link for how to add the remote server name and remote server debug port:

http://java.dzone.com/articles/how-debug-remote-java-applicat

4. For more general information, see link:

http://javarevisited.blogspot.in/2011/02/how-to-setup-remote-debugging-in.html

 

QuickSort on an Array

Implement a QuickSort on an Array

public class QuickSort {

   

    int partition( int[] in ) {

        if ( in.length == 1) return 0;

   

        if ( in.length == 2 ) {

            if ( in[0] > in[1]) {

                swap(in , 0 ,1);

                return 1;

            }else if( in[0] == in[1])

                return 1;

            else return 0;

               

        }

       

        int pivot = in[0];

        int down = 1;

        int up = in.length - 1;

        int ele = -1;

       

        while ( up > down ) {

            // move down pointer

            while( in[down] <= pivot && down < in.length -1)

                ++down;

                   

            while( in[up] > pivot && up > 0)

                --up;

               

            if ( up > down) {

                swap(in, down, up);

                ele = down;

               

                ++down;

                --up;

            }

        }

        if ( in[up] > pivot) {

            swap(in, 0, ele);

        }else{

            swap(in, 0, up);

            ele = up;

        }

        return ele;

    }

   

    private void swap( int[] in, int lb, int ub ) {

        int tmp = in[lb];

        in[lb] = in[ub];

        in[ub] = tmp;

    }

   

    void print(int[] in) {

        for( int i: in )

            System.out.println(i);

    }

   

    public static void main( String[] args ) {

       

        int[] in = new int[] {57,25, 36, 69, 22, 99, 48, 98, 88, 79, 62 };

       

        int[] in1 = new int[] {25, 22, 21, 23, 24 };

       

        int[] in2 = new int[] { 21, 24, 26, 28, 49 };

       

        int[] in3 = new int[] { 25, 57, 48, 37, 12, 92, 86, 33};

       

        int[] in4 = new int[]{2,1,3,-2,0};

       

        int[] in5 = new int[]{2,1,0,6,-7};

       

        int[] in6 = new int[]{25,35,49,50,21,22,25};

       

        int[] in7 = new int[]  {2,1,2};

       

        int[] in8 = new int[]  {2,2};

       

        QuickSort sort = new QuickSort();

   

        System.out.println("--------------------");

       

        System.out.println(sort.partition(in));

        sort.print(in);

       

        System.out.println("-------------------------------");

        System.out.println(sort.partition(in1));

        sort.print(in1);

   

        System.out.println("-------------------------");

        System.out.println(sort.partition(in2));

        sort.print(in2);

       

        System.out.println("-------------------------------");

        System.out.println(sort.partition(in3));

        sort.print(in3);

       

        System.out.println("-------------------------------");

        System.out.println(sort.partition(in4));

        sort.print(in4);

       

        System.out.println("----------------------");

        System.out.println(sort.partition(in5));

        sort.print(in5);

       

        System.out.println("-------------------------");

        System.out.println(sort.partition(in6));

        sort.print(in6);

       

        System.out.println("---------------------------");

        System.out.println(sort.partition(in7));

        sort.print(in7);

       

        System.out.println("---------------------------");

        System.out.println(sort.partition(in8));

        sort.print(in8);

       

       

    }

}

implement a Queue from Two Stacks

Implement a Queue from Two Stacks

Below is a java program to Implement a Queue from two Stacks

public class QueueFromStack {

   

    Stack pushStack = new Stack();

    Stack otherStack = new Stack();

    int front = -1;

    int rear = -1;

   

    void queue(int val ) {

        pushStack.push(val);

    }

   

    boolean isEmpty() {

        return pushStack.isEmpty();

    }

   

    int dequeue() {

        int dequeuedVal = 0;

        boolean found = false;

        while( !pushStack.isEmpty()) {

            int val = pushStack.pop();

            otherStack.push(val);

        }

        if ( !otherStack.isEmpty() ) {

            found = true;

            dequeuedVal = otherStack.pop();

        }

        while ( !otherStack.isEmpty() ) {

            int val = otherStack.pop();

            pushStack.push( val );

        }

        if ( !found )

            throw new RuntimeException("Empty Queue");

       

        return dequeuedVal;           

    }

   

    void print() {

        int bottom = pushStack.getBottom();

        int top = pushStack.top();

        while( bottom <= top )

        System.out.println( pushStack.get(bottom++) );

    }

   

    public static void main( String[] args ) {

        QueueFromStack qfs  = new QueueFromStack();

        qfs.queue(2);

        qfs.queue(3);

        qfs.queue(5);

       

        qfs.print();

       

        System.out.println("-------------------------");

        qfs.dequeue();

        qfs.dequeue();

               

        System.out.println("-------------------------");

        qfs.print();

    }

}

------------------------------------ Stack class --------------------------------------------------------

public class Stack {

    public int max_size = 20;
    private int[] stack = new int[max_size];
   
    int top = -1;
   
    void push( int val ) {
        if ( top == max_size )
            throw new RuntimeException("Stack_Overflow");
        stack[++top] = val;
    }
   
    int top() {
        return top;
    }
   
    int pop() {
        if ( top == -1)
            throw new RuntimeException( "stack_underflow" );
        return stack[top--];
    }
   
    boolean isEmpty() {
        return top == -1;
    }
   
    int peek() {
        return stack[top];
    }
   
    void clear() {
        top = -1;
    }
   
    int getBottom() {
        return 0;
    }
   
    int get( int i ) {
        return stack[i];
       
        }
}

Implement a Stack from Two Queues

Implement a Stack from Two Queues

Below is a java program to Implement a Stack from Two Queues

public class StackFromQueue {
   
    Queue pushQ = new Queue();
    Queue popQ = new Queue();
   
    void push( int val ) {
        pushQ.enqueue(val);
    }
   
    int pop() {
       
        if ( pushQ.isEmpty() )
            throw new RuntimeException("empty_queue");
       
        int front = pushQ.front();
        int rear = pushQ.rear();
       
        while ( front++ < rear ) {
            int val = pushQ.dequeue();
            popQ.enqueue(val);
        }
       
        int ret = pushQ.dequeue();
       
        Queue a = pushQ;
        pushQ = popQ;
        popQ = a;
       
        return ret;
    }
   
    void print() {
        if ( !pushQ.isEmpty() ) {
            int front = pushQ.front();
            int rear = pushQ.rear();
           
            while ( front <= rear ) {
                System.out.println( pushQ.get(front++));
            }
        }
    }
    public static void main( String[] args ) {
        StackFromQueue sfq = new StackFromQueue();
        sfq.push( 2 );
        sfq.push( 3);
        sfq.push(4);
       
        sfq.print();
       
        System.out.println("--------------------------");
       
        System.out.println(sfq.pop() );
        System.out.println(sfq.pop() );
       
        System.out.println("---------------------------");
       
        sfq.print();
       
    }

}

-------------------------------------- Queue class ------------------------------

public class Queue {
   
    final int max_size = 20;
    int[] queue = new int[ max_size];
   
    int front;
    int rear;
   
    public Queue() {
        init();
    }
   
    private void init() {
        front = 0;
        rear = -1;
    }
   
    void enqueue( int val ) {
        if ( rear == max_size - 1)
            throw new RuntimeException("overflow");
        queue[++rear] = val;
    }
   
    int dequeue() {
        if ( isEmpty() )
            throw new RuntimeException("underflow");
        int retVal =  queue[front++];
        if ( front > rear ) {
            init();
        }
        return retVal;
    }
   
    int front() {
     return front;
    }
   
    int rear() {
        return rear;
    }
   
    int get( int i ) {
        if ( i >= front && i <= rear ) {
            return queue[i];
        }
        throw new RuntimeException( "index_out_of_bounds" );
    }
   
    boolean isEmpty() {
        return rear == -1 && front == 0;
    }
   
    void print() {
        if ( !isEmpty() ) {
            int front = front();
            int rear = rear();
           
            while ( front <= rear ) {
                System.out.println( get(front++));
            }
        }
    }
   
    public static void main( String[] args ) {
        Queue q = new Queue();
        q.enqueue(2);
        q.enqueue(3);
       
        q.print();
       
        System.out.println("------------------");
       
        System.out.println(q.dequeue() );
        System.out.println(q.dequeue());
       
        System.out.println("-------------------");
       
        q.print();
       
    }

}

Merge Two Sorted Link Lists into a Third Sorted List

Merge two Sorted Linked List into a Third Linked List

Java program to Merge two sorted lists into a third list. Below program has, both a recursive and iterative version methods

public class MergeLinkList {

    private Link mergeRecursive( Link l1, Link l2 ) {

        if ( l1 == null) return l2;

        if ( l2 == null ) return l1;

       

        Link mergedhead = null;

       

        if ( l1.value() < l2.value() ) {

            mergedhead = l1;

            mergedhead.next = mergeRecursive(l1.next, l2);

        }else {

            mergedhead = l2;

            mergedhead.next = mergeRecursive(l1, l2.next);

        }

        return mergedhead;

    }

   

    private Link mergeInterative( Link  l1, Link l2 ) {

        if ( l1 == null) return l1;

        if ( l2 == null ) return l2;

       

        Link p1 = l1;

        Link p2 = l2;

       

        Link mergedHead= null;

        Link last = mergedHead;

       

        while ( p1!= null && p2 != null ) {

        if ( p1.value() < p2.value() ) {

          if ( last == null ) {

              last = new Link(p1.value());

              mergedHead = last;

          }else {

              last.next = new Link( p1.value());

              last = last.next;

          }

         p1 = p1.next;

        }else {

             if ( last == null ) {

                  last = new Link(p2.value());

                  mergedHead = last;

              }else {

                  last.next = new Link( p2.value());

                  last = last.next;

              }

             p2 = p2.next;

        }               

        }

        if ( p1 != null ) {

            insertAll( p1, last );

        }else

            insertAll( p2, last );

       

        return mergedHead;

    }

   

    private void insertAll( Link p1, Link last ) {

        do {

            last.next = new Link(p1.value());

            p1 = p1.next;

        }while ( p1 != null );

    }

   

public static void main( String[] args ) {

       

        /*

          * .................n..........n.............n.........n.............n.......................n............n..........        ---> Number line for Array1, has 8 numbers in ascend

         * .....n...n...........n......... n...n..........n.........n.................................................................... 

             * */

       

            int[] ar1 = new int[] { 45, 56, 77, 89, 150, 187, 198};

            int len1 = 7;

           

            int[] ar2 = new int[] { 23, 29, 47, 59, 67, 80, 106 };

            int len2 = 7;

           

            Link l1 = Link.build( ar1 );

            Link l2 = Link.build(ar2);

           

            MergeLinkList merge = new MergeLinkList();

            Link mergedIter = merge.mergeInterative(l1, l2);

            mergedIter.print(mergedIter);

           

            System.out.println("Prining recursively");

           

            Link mergedRecursive = merge.mergeRecursive(l1, l2);

            mergedRecursive.print(mergedRecursive);

           

           

    }

}

Sort a given List using Insertion Sort

Sort a Linked List using Insertion Sort

C++ Code to sort a given list

 

void Sort(ListNode** pHead) {
if(pHead == NULL || *pHead == NULL)
return;

ListNode* pToBeSorted = pLastSorted->m_pNext;
while(pToBeSorted != NULL) {
if(pToBeSorted->m_nValue < (*pHead)->m_nValue) {
pLastSorted->m_pNext = pToBeSorted->m_pNext;
pToBeSorted->m_pNext = *pHead;
*pHead = pToBeSorted;
}
else {
ListNode* pNode = *pHead;
while(pNode != pLastSorted
&& pNode->m_pNext->m_nValue < pToBeSorted->m_nValue) {
pNode = pNode->m_pNext;
}
if(pNode != pLastSorted) {
pLastSorted->m_pNext = pToBeSorted->m_pNext;
pToBeSorted->m_pNext = pNode->m_pNext;
pNode->m_pNext = pToBeSorted;
}
else
pLastSorted = pLastSorted->m_pNext;
}
pToBeSorted = pLastSorted->m_pNext;
}
}

Merge Two Sorted Arrays

Merge Two Sorted Arrays into one of the Arrays

Given two sorted arrays, denoted as array1 and array2, 

Merge them into array1 and keep the merged array sorted.

** Assumption: Array1 has enough space to accomodate the elements of Array2

Java Program to Merge Two sorted arrays

public class MergeSortedArrays {

/**

 *                                                                                           |

 *                                                                                           index1

 * .................n..........n.............n.........n.............n.......................n............n...n............        ---> Number line for Array1, has 8 numbers in ascend

 * .....n...n...........n........ n...n..........n.........n....................................................................       ----> Number line for Array2

 *                                              index2

 *                                               |

 * In the above number line 'n' stands for a number in the number line for natural numbers for the given array

 *

 *

 */

   

    public int[] merge( int[] array1, int[] array2, int length1, int length2 ) {

        if ( array1 == null )

            throw new IllegalArgumentException("Invalid array to merge" );

       

        if ( array2 == null || array2.length == 0 )

            return array1;

       

        int index1 = length1- 1;

        int  index2 = length2 -1;

        int mergedBoundary = length1 + length2 - 1;

   

        while( index1 >= 0 && index2 >= 0) {

            if ( array1[index1] > array2[index2] ) {

                array1[mergedBoundary--] = array1[index1--];

            }else {

                array1[mergedBoundary--] = array2[ index2-- ];

            }

        }

        while ( index2 >= 0 ) {

            array1[ mergedBoundary--] = array2[index2--];

        }

       

        return array1;   

       

    }

   

    public static void print( int[] ar, int len ) {

        int i = 0;

        while ( len-- > 0)

            System.out.println( ar[i++ ]);

    }

   

    public static void main( String[] args ) {

        /*

      * .................n..........n.............n.........n.............n.......................n............n..........        ---> Number line for Array1, has 8 numbers in ascend

     * .....n...n...........n......... n...n..........n.........n.................................................................... 

         * */

   

        int[] ar1 = new int[] { 45, 56, 77, 89, 150, 187, 198, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

        int len1 = 7;

       

        int[] ar2 = new int[] { 23, 29, 47, 59, 67, 80, 106 };

        int len2 = 7;

        MergeSortedArrays merge = new MergeSortedArrays();

        int[] ar3 = merge.merge( ar1, ar2,  len1, len2 );

        print( ar3, len1+len2 );

    }

}

An array of Numbers with Multiple Duplicates

How to Find Duplicates in an Array of N numbers ranging from 0 to N-1.

An array contains n numbers ranging from 0 to n-1. There are some numbers duplicated in the
array. It is not clear how many numbers are duplicated or how many times a number gets duplicated. How to find a duplicated number in such an array? For example, if an array of length 7 contains the numbers {2, 3, 1, 0, 2, 5,
3}, the implemented function (or method) should return either 2 or 3.

Java Code:

int duplicate(int numbers[]) {
int length = numbers.length;
for(int i = 0; i < length; ++i) {
if(numbers[i] < 0 || numbers[i] > length - 1)
throw new IllegalArgumentException("Invalid numbers.");
}
for(int i = 0; i < length; ++i) {
while(numbers[i] != i) {
if(numbers[i] == numbers[numbers[i]]) {
return numbers[i];
}
// swap numbers[i] and numbers[numbers[i]]
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
throw new IllegalArgumentException("No duplications.");
}