Pages

Saturday, March 21, 2015

Electing Prime Cabinet Members of BAAP party!!!

Problem Statement -
Electing Prime Cabinet Members of BAAP party!!!
BAAP   party president Mr. Panna decided to choose the Prime Cabinet Members for his party from each state of the country Youngistaan.
The criterion decided by Mr. Panna is that from each state having a population of N, N votes will be casted.  If a candidate gets more than N/2 votes, he/ she will be elected as Prime Cabinet Member of BAAP party.
Given that population of each state be N, where N should be maximum 10, 00000 for each state. Assume that each individual will cast the vote.
Help Mr. Panna design an automated system to get the Prime Cabinet Members from each state, if any. If a member contesting for the cabinet member post from a state gets more than half (> N/2) of the total population votes, he/ she will be appointed as Prime Cabinet Member of BAAP party else the post will be vacant.
Write an algorithm to help Mr. Panna appoint the cabinet member for the BAAP party.
Each of the contesting members will be allotted a positive integer number.
Given the population of each state N, write a method int primeMember (int P []); which should return the prime member of array P, where P will be the population array of a given state of size N.  The method must return −1, if array P does not have a prime member.
Input Specification:
A population array P, of size N (a state population) in random order where each array index denotes a member’s vote of the given state for his/her candidate denoted by a positive integer (candidate number).
Output Specification:
Single integer value if the prime member exists, else -1(minus one).
Complexity:
Expected worst-case time complexity is O (N).
Expected worst-case space complexity is O (1).




Example 1:
For example, given population array P having candidate 2, 3, 4, 6 contesting from a state having the total population of N=12, such that each person from the state casted his/ her vote for one of the above candidate as below:
{4, 3, 3, 4, 2, 4, 3, 3, 6, 3, 3, 4}
The method should return −1, because the candidate 3 got the maximum vote 6 out of all the candidates contesting and 6 votes is not more than half of total population 12.
Example 2:
For example, given population array P having candidate 2, 3, 7, 10 contesting from a state having the total population of N=7, such that each person from the state casted his/ her vote for one of the above candidate as below:
{7, 3, 3, 10, 3, 3, 2}

The method should return 3, because the candidate 3 got the maximum vote 4 out of all the candidates contesting and 4 votes is more than half of total population 7.

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




Tuesday, December 24, 2013

Difference between Path and CLASSPATH

Path -> all the operating system application executable paths should be there.

CLASSPATH -> is specific to JAVA only. The compiled .class file should be present in the CLASSPATH location specified in the environment variables so as to get it executed from cmd prompt.
CLASSPATH should be set for the java file(in the environment variable) if we are executing the java class from cmd prompt. CLASSPATH should contain the path of the generated .class file.

When the jdk is first time installed to a m/c, user should put the jdk path upto bin in the 'Path' variable as jdk is an app for OS.

JAVA_HOME -> is used to replace the path till jdk ../../bin or lib in tomcat run.bat,etc

Wednesday, September 4, 2013

IE10 Cross domain issue - Access Denied error while making xhr call


The IE10 supports CORS fully. 
In some cases user may face "Access denied" while making a xhr call. 
Let me try to explain the scenario where the user will get "Access denied" error-

Before that we should be aware of the two terminology -

Origin : domain hosting the script content
Host : the domain requested by xhr call

Let the Origin in our case be *.adobe.co.uk & Host be *.adobe.com.

Now either both domains should be in the IE10 trusted site domain list or both should not be present in the list. To go to the IE trusted site settings, Go to Internet options -> Security -> Select trusted sites option & click on Sites(button). It will show all the trusted websites (domain)

If one of the Origin/ Host is present in the trusted site domain list, then the user will get Access denied error while making xhr call in the native open method of javascript. for example user will get Access denied error while making xhr call to *.adobe.com from the script hosted/running on *.adobe.co.uk

Cross domain reference link from MS blog -CORS for XHR in IE10

Working cross domain example - Cross-Site Upload
In the cross site upload example -

Origin - http://ie.microsoft.com/
Host - http://html5labs.interoperabilitybridges.com.

If we put either the Origin or Host in the Trusted Sites domain then while making the xhr call, Access Denied error will prevent file upload operation.