Amazon Interview Question for SDE-2s


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
2
of 4 vote

This can be solved in single pass through the array .. It is called Kandane's Algorithm

public class Kadane {
 
    public static void main(String[] args) {
    	int[] intArr={3, -1, -1, -1, -1, -1, 2, 0, 0, 0 };
    	//int[] intArr = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
    	//int[] intArr={-6,-2,-3,-4,-1,-5,-5};
        findMaxSubArray(intArr);
    }
 
    public static void findMaxSubArray(int[] inputArray){
 
        int maxStartIndex=0;
        int maxEndIndex=0;
        int maxSum = Integer.MIN_VALUE; 
 
        int cumulativeSum= 0;
        int maxStartIndexUntilNow=0;
        		
        for (int currentIndex = 0; currentIndex < inputArray.length; currentIndex++) {
        	
            int eachArrayItem = inputArray[currentIndex];
            
            cumulativeSum+=eachArrayItem;
 
            if(cumulativeSum>maxSum){
                maxSum = cumulativeSum;
                maxStartIndex=maxStartIndexUntilNow;
                maxEndIndex = currentIndex;
            }
            else if (cumulativeSum<0){
            	maxStartIndexUntilNow=currentIndex+1;
            	cumulativeSum=0;
            }
        }
 
        System.out.println("Max sum         : "+maxSum);
        System.out.println("Max start index : "+maxStartIndex);
        System.out.println("Max end index   : "+maxEndIndex);
    }
   
}

- nsaichand April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

The above program doesn't work for the input { -9, 3, 3, 4, 3, -7, -5, 1, -2, 5, 4, 2, -5, 4 };

- geekyjaks April 27, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

We do not need 'nlogn', we only need O(n). As mentioned above, it is a Kadane Algorithm.

int length ;
        int a[]={-12, 14, 0, -4, 61, -39};  
        length = a.length;

        int absoluteMax=0, localMax=0, startIndex=0, lastIndex=0, tempStartIndex=0;
        
        for (int index = 0; index < length;index++) {
            localMax= localMax + a[index];
            if(localMax < 0){ localMax=0; tempStartIndex = index + 1;}
            if(absoluteMax < localMax) {
                absoluteMax = localMax; 
                lastIndex = index; 
                startIndex = tempStartIndex;
            }
        }

- soodongStudying April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Raaz,

Can u please clarify this
P = {4,6,-3,1,5,9,-2} is the array
S ={1,5,9} has sum of 15
but Q = {4,6,-3,1,5,9} has sum of 22.
so is S is correct or Q...?

- bhupal April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hello Bhupal,
My mistake..correct output should be Q = {4,6,-3,1,5,9}.

- Razz April 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why isn't this array the max?
{4,6,1,5,9}

- puneet.sohi April 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not max because you're skipping elements in the output array. Remember, the sub array "Must have the same sequence"

- RandomMecanic April 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

First thought is brute force, that thats just a start.
Second thought would be to think of the array as the bottom tier of a quasi-binary tree, building up towards the final sum as the 'root' of the tree.
You could then walk the tree from the root, looking at each individual tier, looking for the maximal node combination

- RandomMecanic April 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Specially, think MinMax or AlphaBeta search routines for this one.

- RandomMecanic April 26, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

//linear time O(n), traverse from left to right

//initialize variables
int i = 0;
int maxSum = 0; // sum of current maximum array
int LastSum = 0; // sum of current extending array
int maxBegin = 0; //start position of current maximum array
int LastBegin = 0; //start position of current extending array
int maxLength = 1; // length of current maximum array
int LastLength = 1; // length of current extending array

for(i=0; i<arr.length(); i++)
{
	//if LastSum and the current integer are both non-negative or LastSum >= |arr[i]|, merge them
	if(LastSum >= 0 && (arr[i] >= 0 || LastSum >= -arr[i]))
	{
		LastSum += arr[i];
		LastLength ++;
	}

	//if arr[i] < 0, and |arr[i]| > LastSum , restart the calculation
	else if arr[i] < -LastSum //note that LastSum  is maintained non-negative
	{
		LastLength = 0;
		LastSum = 0;
		if(i< arr.length) 
LastBegin = i+1;
	}

	///compare LastSum and maxSum, if LastSum  is greater, update the array which has maximum sum.
	if( LastSum >= maxSum )
	{
maxSum = LastSum;
maxBegin = LastBegin;
maxLength = LastLength;
	}

}

- mikezebin April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is called Maximum Sub Array problem (refer MIT Introduction to Algorithms by Cormen)

public class MaxSubArray {

  private static class SubArray {
    int start;
    int end;
    int sum;

    SubArray(int start, int end, int sum) {
      this.start = start;
      this.end = end;
      this.sum = sum;
    }
  }

  private SubArray findMaxCrossingSubArray(int[] data, int start, int mid,
      int end) {
    int sum = 0;
    int leftSum = Integer.MIN_VALUE;
    int maxLeft = mid;
    for (int index = mid; index >= start; index--) {
      sum += data[index];
      if (leftSum < sum) {
        leftSum = sum;
        maxLeft = index;
      }
    }

    int rightSum = Integer.MIN_VALUE;
    int maxRight = mid + 1;
    sum = 0;
    for (int index = mid + 1; index <= end; index++) {
      sum += data[index];
      if (rightSum < sum) {
        rightSum = sum;
        maxRight = index;
      }
    }

    return new SubArray(maxLeft, maxRight, leftSum + rightSum);
  }

  public SubArray findMaxSubArray(int[] data, int start, int end) {

    if (start == end)
      return new SubArray(start, end, data[start]);

    int mid = (start + end) / 2;
    SubArray ls = findMaxSubArray(data, start, mid);
    SubArray rs = findMaxSubArray(data, mid + 1, end);
    SubArray mcs = findMaxCrossingSubArray(data, start, mid, end);

    if (ls.sum >= rs.sum && ls.sum >= mcs.sum)
      return ls;
    else if (rs.sum >= ls.sum && rs.sum >= mcs.sum)
      return rs;
    else return mcs;
  }

  public static void main(String[] args) {

    int[] data = { -9, 3, 3, 4, 3, -7, -5, 1, -2, 5, 4, 2, -5, 4 };
    MaxSubArray msa = new MaxSubArray();
    SubArray sa = msa.findMaxSubArray(data, 0, data.length - 1);
    System.out.println("Start: " + sa.start + ", End: " + sa.end + ", Sum: "
        + sa.sum);
  }
}

The code runs in O(n log n)

- geekyjaks April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dp

public static  void findMaxSeq(int [] seq){
		int [] dp = new int [seq.length] ;
		dp [0] = seq [0] ;
		int max = Integer.MIN_VALUE ;
		int end = -1 ;
		int start = -1 ;
		for (int i = 1 ; i < seq.length ; ++i){
			if (seq[i] + dp[i-1]  <= 0 ){
				dp [i] = seq[i] ;
			}else{
				dp [i] = seq[i] + dp[i-1] ;	
			}
			
			if (dp[i] > max){
				max = dp [i];
				end = i;
			}
		}
		
		end = dp [0] > max ? 0 : end;
		
		for (int i = 0 ; i < dp.length ; ++i){
			if (dp[i] >= 0){
				start = i ;
				break;
			}
		}
		
		System.out.println("from " + start + " to "  + end);

}

- Scott April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

o(n) solution,  in two passes we should be able to find the max sub array without disturbing the sequence

public static void maxSubArray(int[] arr)
	{
	  
	  int cummaltive = 0;
	  int max = 0;
	  int maxIndex = 0;
	  
	  //one pass - find the max index that produces max sub array
	  for(int i = 0; i< arr.length; i ++)
	  {
		  cummaltive = cummaltive+arr[i];
	       
	       if(cummaltive > max)
	       {
	            max = cummaltive;
	            maxIndex = i;
	       }
	  }
	  
	  //second pass loop till max pointer
	  
	  
	  for(int i = 0; i<=maxIndex; i ++)
	  {
	      System.out.println(arr[i]);
	  }
	  
	}

- fsheriff April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution only takes into account arrays that start from the 0th element to n (where n is some index in the array).

- John April 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void max(int a[],int n)
{
     int i=0,sum=0,max=0,end=0;
     for(i=0;i<n;i++)
     {
         sum = sum+a[i];
         if(sum>max)
         {
            max=sum;
            end=i;
         }
         if(sum<0)
            sum=0;
     }
     printf("Maximum Sum is %d\n",max);
     while(max>0)
     {
         printf("%d\t",a[end]);
         max = max-a[end];
         end--;
     }
     printf("\n");
}

- Nitin April 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ function:

{
int * maxSequence(int * arr, int length)
{
	int max = 0, start = 0, end = 0, actual_start = 0, sum = 0;
	for(int i = 0; i < length; i++)
	{
		sum += arr[i];
		if(sum < 0)
		{
			sum = 0;
			start = i + 1;
		}
		else if(sum > max)
		{
			max = sum;
			end = i;
			actual_start = start;
		}
	}
	
	int extension = end - actual_start + 1;
	int * result = new int[extension];
	for(int i = 0; i < (extension); i++)
		result[i] = arr[i + actual_start];
	
	return result;
}

}

- NL May 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a[] = { -9, 3, 3, 4, 3, 20, -50, -5, 4};
int sum=0;
int max=0;
int pos=0;
for(int i=0;i<a.length;i++)
{
sum+=a[i];
if(sum>=max)
{
max=sum;
pos=i;
}
}
System.out.println(max+ " "+pos);

- Asmi May 14, 2014 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More