Pages

Tuesday, June 10, 2014

Sort array containing only 0, 1 & 2 in Complexity O(n)

Java Implementation -
public class SortArrayContaining012Only {

    public static void main(String[] args) {
        int arr[] = { 0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1 };
        int arr_size = arr.length;
        sort012(arr, arr_size);
        System.out.println("Sorting done");
    }

    private static void sort012(int a[], int arr_size) {
        int lo = 0;
        int hi = arr_size - 1;
        int mid = 0;

        while (mid <= hi) {
            switch (a[mid]) {
            // swap lo and mid
            case 0:
                int temp = a[mid];
                a[mid] = a[lo];
                a[lo] = temp;
                lo++;
                mid++;
                break;
            case 1:
                mid++;
                break;
            // swap mid and high
            case 2:

                temp = a[mid];
                a[mid] = a[hi];
                a[hi] = temp;
                hi--;
                break;
            }
        }
    }
}

Sunday, May 25, 2014

Find the next higher number with same digits

Problem :  Given a number, write an algorithm to find the next higher number with the same digits.

For example : If the input is 45156, then the next higher number with the same digit is 45516.

Solution :

Algorithm -
1. Scan the digits of the given number from right to left starting from tenth digit (current index).
2. At each iteration we check,
    if the digit at the right is greater than the current index, then
   {we stop - Follow step 3 }
    else
   {continue left}
3. The current index value is the pivot element.
4. Find the smallest digit (x) higher than the pivot element.
5. Swap the pivot element with x.
6. Now the pivot digit is x.
7. Sort all the digits to the right of pivot digit in increasing  order.

Java Implementation -
import java.util.Arrays;

public class NextHigherNoWithSameDigits {

    public static void main(String[] args) {
        int input[] ={4,5,1,5,6};
        System.out.println("Input No. ======>" + intArrToString(input));
        int[] output = higherNo(input);
        System.out.println("Output No. ======>" + intArrToString(output));
    }

    private static int[] higherNo(int[] arr) {
        for (int i = arr.length - 1; i >= 0; i--) {
            // scan the no. from right starting at 10's place, if the element at
            // the right is greater then left is the pivot element
            if (arr[i] > arr[i - 1]) {
                // get the pivot element index
                int j = i;
                // sort the element to the right of the pivot element
                Arrays.sort(arr, i, arr.length);
                while (true) {
                    if (arr[i - 1] < arr[j]) {
                        // swap the pivot element with the smallest digit higher
                        // than the pivot element on the right
                        swap(arr, i, j);
                        break;
                    }
                    j++;
                }
                break;
            }
        }
        return arr;
    }

    /**
     * Helper method to swap two elements of the array
     * 
     */
    private static void swap(int arr[], int i, int j) {
        int temp = arr[i - 1];
        arr[i - 1] = arr[j];
        arr[j] = temp;

    }

    /**
     * Helper method to print the input/ output as numbers
     * 
     */
    private static StringBuilder intArrToString(int a[]) {
        StringBuilder input = new StringBuilder();
        for (int i = 0; i < a.length; i++) {
            input = input.append(a[i]);
        }
        return input;
    }
}



Sunday, January 12, 2014

Setting up Code Collaborator(SmartBear) for Git

Code Collaborator GUI client is available for git for can be integrated with git code reviews process -

Following steps are -

1) Search for the installed ccollabgui.app (Code Collaborator GUI app)

2) Click on the application. Below window will open up -



3) Click on the "Add" button. SCM configuration window will open up -


Enter the following configuration param values -

a) Local Source Code location -
b) Git executable location (enter the path like /usr/bin/git)
c) Click on validate button to validate the settings

Once the validation is done your configuration is done. You are ready to share the code for the review part.

For sharing the code for review in git there are two options available -
1) Add Changes
2) Add Git Diffs