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.");
}

Reverse a Link List

 

 Program to Reverse a Link List

public class ReverseLinkList {

     public static Link reverse( Link head ) {
        Link last = null;
        Link p0 = head;
        Link p1 = p0 != null ? p0.next: null;
        Link p2 = p1 != null ? p1.next : null;
       
        return reverse( p0, p1, p2, last );
    }
   
    private static Link reverse( Link p0, Link p1, Link p2, Link last ) {
        if ( p0 == null ) return p0;
        if ( p1 == null ) {
            p0.next = last;
            return p0;
        }
        if ( p2 == null ) {
            p1.next = p0;
            p0.next = last;
            return p1;
        }
       
        // reverse middle, p2 can be null at this point
        p1.next = p0;
        p0.next = last;
       
        // reset pointers
        last = p1;
        p0 = p2;
        p1 = p0.next;
        p2 = p1 != null ? p1.next: null;
       
        return reverse( p0, p1, p2, last );   
       
    }

  public static Link build( int count) {
       
        if ( count == 0 ) return null;
        Link head = new Link( 1 );
        Link last = head;
        int a = 1;
        while ( count-- > 1 ) {
        Link link  = new Link( ++a );
        last.next = link;
        last = link;
        }
        return head;
    }
   
    public static void print( Link head ) {
        if ( head == null ) return;
        int count = 1;
    Link k = head;
        do {
            System.out.println( count++ + "::"+ k.name());
            k = k.next;
        }while( k != null );
    }

public static void main( String[] args ) {
        Link head = build(10);
        print( head );
        Link reverseHead = reverse( head );
        System.out.println("Reversing");
        print( reverseHead );
    }


}

class Link {
    private String name;
    Link next;
   
    Link( int name, Link next ) {
        this.name = name + "";
        this.next = next;
    }
   
    Link ( int name ) {
        this( name, null );
    }
   
    String name() {
        return this.name;
    }
   
}

Find Second largest Element in an Array

Find Second largest Element in an Array in Minimum Time Complexity

1. State different ways and the Complexities involved with them

• Keep two pointers, largest, second_largest. Let the first element is largest and second element as second_largest. Compare. After comparison, largest, second_largest will point to right array indices. Move from the third index till the end of array. At each entry to loop, again compare and reset the pointers: largest and second_largest. This solution is of order n, o(n) as there are almost 2n comparisons

A general variation of this problem will be to find out the kth largest in an array of N numbers

• Kth largest logically means that in a set of K elements , find the smallest element. This smallest in the set of K elements is the Kth largest for the set of K. So steps include

Using Min-heap

• Get the first K elements. Construct a min-heap of it. Order of Complexity of constructing this heap = kLog(k)
• Root of this min-heap, which is the smallest of this heap, is the currently the kth largest on this set of k
• a: Iterate over the array from k+1 index. Get the k+1 element of array. If it is less, ignore it
• b: If k+1 th element is greater then root, then insert this element in the min-heap. Order of Complexity for this Log(k)
• c: Remove the smallest , which is the new root. order of Complexity for this is again Log(k)
• d: Now the min-heap again contains K elements, the new root is now the K th largest.
• Do the steps a, b, c, d, for the rest of the elements of array

Order of Complexity in this case:

Order of Complexity to construct the min-heap of K elements = kLog(k)- one time

order of Complexity to insert a new element = kLog(k) - ( n-k) times

order of Complexity to remove the root = kLog(k) - ( n-k) times

Total complexity, order :

kLog(k) + 2*(n-k)*Log(k)