Google Interview Question with Solution (Technical Support)

SumToTarget (a[], ar_size, sum)
1) Sort the array in ascending order using merge sort for low complexity.
2) Initialize two index variables to find the candidate
   elements in the sorted array.
       (a) Initialize first to the leftmost index: first_index = 0
       (b) Initialize second  the rightmost index:  last_index = ar_size-1
3) Loop while first_index < last_index.
       (a) If (A[first_index] + A[last_index] == sum)  then return 1
       (b) Else if( A[first_index] + A[last_index] <  sum )  then last_index++
       (c) Else first_index--   
4) If no candidates in whole array - return 0

import java.util.*;
import java.lang.*;
 
class Main
{
        public static void main (String[] args) throws java.lang.Exception
        {
        int a[]={4,1,2,7,9,3};
        int length=a.length;
        length--;
        mergesort(a,0,length);
        if(SumToTarget(a,0,length,4)==1)
        System.out.println("Duplicates exist in the array");
        else 
        System.out.println("Duplicates does not exist in the array");
        }   
        
    /* Function to check whether the duplicates whose sum equal to target num exist or not */
    public static int  SumToTarget(int a[],int start,int last , int num)
    {
        int first_index=start;
        int last_index=last;
       /*if first_index becomes greater than last_index it means duplicates does not exist */
        while(first_index<last_index)
        {
        /* if sum of dupliactes is equal to required sum it means duplicates are present hence returning 1  */
        if((a[first_index]+a[last_index])==num )
            {
                 System.out.println("Two numbers are:->"+a[first_index]+" "+a[last_index]);
                 return 1;
                 
            }
        /*if sum of two number is greater than the required sum then the last_index will be decreased*/
        else if((a[first_index]+a[last_index])>num)
            {
                last_index--;
            }
        /*if sum of two number is less than the required sum then the first_index will be increased*/    
        else if((a[first_index]+a[last_index])<num)
            {
                first_index++;
            }
        }
        
     /*program will reach here only if there no duplicates equal to sum consequently will return 0 */
           return 0;
    }
 
    public static void  mergesort(int a[],int start,int last)
    {
        if(start<last)
        {
            int mid=(start+last)/2;
            mergesort(a,start,mid);
            mergesort(a,mid+1,last);
            merge(a,start,last,mid);
        }
    }
    public static void merge(int a[],int start ,int last,int mid )
    {
        int j,k,l;
        int c[]=new int[a.length];
        j=start;
        k=start;
        l=mid+1;
        while(j<=mid && l<=last )
        {
            if(a[j]<a[l])
            {
                c[k]=a[j];
                k++;
                j++;
            }
            else
            {
                c[k]=a[l];
                k++;
                l++;
            }
        }
        while(j<=mid)
        {
            c[k]=a[j];
            k++;
            j++;
        }
        while(l<=last)
        {
        c[k]=a[l];
        k++;
        l++;
        }
       
        for(int i=start;i<=k-1;i++)
        {
            a[i]=c[i];
        }
    }
}