Amazon Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
1
of 1 vote

For contiguous subarray. how about use kadane's algorithm.

- jproboy July 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What should be the length of subarray??

- pinky884 July 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Obviously it has to be contiguous. Otherwise just sum up all the positive numbers.

- Vinod July 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def maxSubarray(arr:Array[Int]): Array[Int]= {
    
    var maxEndedArr = new Array[Int](arr.length)
    var maxArr = new Array[Int](arr.length)
    
        
    maxEndedArr(0) = max(0, arr(0))
    maxArr(0) = max(0, arr(0))
    
    var index = 1;
   
    while( index < arr.length ){
      
      val value = arr(index)
      
      maxEndedArr(index) = max(0, maxEndedArr(index-1) + value)
      maxArr(index) = max( maxArr(index-1), maxEndedArr(index) )
      
      index += 1
    }
    
    val maxSumValue = maxArr( maxArr.length-1)
    
    var i = maxEndedArr.length-1
    var from = -1
    var to = -1
        
    while( i >=0 && from < 0 ){
      
      if( maxEndedArr(i) == maxSumValue ){
        to = i
      }
      
      if( maxEndedArr(i) == 0 && to > 0 ){
        from = i+1        
      }
      
      i -= 1
    }    
    
    val maxSubarray = new Array[Int](to - from + 1)
    
    var copyIndex = 0
    
    while( from+copyIndex < to + 1 ){
      maxSubarray(copyIndex) = arr(from+copyIndex)
      copyIndex += 1
    }
    
    return maxSubarray 
  }

- m@}{ July 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Optimized version:

/**
   * Use one pass by original array.
   * Time: O(N)
   * Space: O(N)
   */
  def maxSubarray(arr:Array[Int]): Array[Int]= {
    
    if( arr == null ){
      throw new IllegalArgumentException("NULL array passed")
    }
    
    if( arr.length == 0 ){
      return new Array[Int](0)
    }    
           
    var maxEnded = max(0, arr(0))
    var maxAll = max(0, arr(0))   

    var firstNonZeroIndex = -1    
    var maxFromIndex = -1
    var maxToIndex = -1
    
    for( i <- 1 to arr.length-1){
      
      var newMaxEnded = max(0, maxEnded + arr(i) )
      var newMaxAll = max( maxAll, newMaxEnded )
                  
      if( maxEnded == 0 && newMaxEnded > 0 ){
        firstNonZeroIndex = i
      }
      
      if( newMaxEnded > maxAll ){
        maxFromIndex = firstNonZeroIndex
        maxToIndex = i
      }         
      
      maxEnded = newMaxEnded
      maxAll = newMaxAll
      
    }
   
    // up to N elements
    val maxSubarray = new Array[Int](maxToIndex - maxFromIndex + 1)
    
    for( i <- 0 to maxSubarray.length-1 ){
      maxSubarray(i) = arr(maxFromIndex + i)
    }
 
    return maxSubarray 
  }

- m@}{ July 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

good

- jingtianjiang July 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

what if -1 -2 -3 -4 -5 -6 -7 -8 -9 -10

- zhou July 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@zhou: the answer is 0 if all are negative
and the answer is sum of all numbers if all the numbers are positive

- anonymous July 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

After sorting leave first element and return the pointer of rest of the array. Does it meet your requirement? Or I misunderstood it?

- ASSERT(null) July 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This would be the naive solution to give first, but obviously too slow for the intention of this question.

- airfang613 July 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just keep track of current maximum sum, if the current element alone is bigger than the sum, then update the sum with current element.

See the code below in action: ideone.com/bPblj

int GetMaxSum(const vector<int>& array, int* max_lb, int* max_ub) {
  int maxsum = std::numeric_limits<int>::min();
  int sum = 0;
  
  int lb = 0;
  *max_lb = *max_ub = lb;
  
  int len = array.size();
  for (int i = 0; i < len; ++i) {
    sum += array[i];
    if (sum < array[i]) {
      sum = array[i];
      lb = i;
    }
    if (maxsum < sum) {
      maxsum = sum;
      *max_lb = lb;
      *max_ub = i;
    }
  }
  return maxsum;
}

- airfang613 July 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>

int main()
{
int arr[13]={-11,-2,6,4,5,10,7,-9,11,15,16,-5,-8};
int previous_sum=0;
int current_sum=0;
int i=0;
for(i=0;i<13;i++)
{
if(arr[i]<0)
{
if(previous_sum<=current_sum)
previous_sum=current_sum;
current_sum=0;
}
else
{

current_sum=current_sum+arr[i];

}

}
if(previous_sum>=current_sum)
{

current_sum=previous_sum;
}
printf("Value is %d\n",current_sum);
}

- Anonymous August 22, 2011 | 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