Microsoft Interview Question: 1- Given an array of integers... | Glassdoor

Interview Question

Software Development Engineer (SDE) Interview(Student Candidate)

1- Given an array of integers, positive and negative. find

  an interval in that array, whose elements constitutes the maximum sum
Answer

Interview Answer

3 Answers

1

This is a fairly known problem, but I was too stressed at the time to think straight. first I offered a brute force solution through generating all intervals using 3 into one another for loops, with complexity O(n^3), but then he wanted to do it on O(n), he helped really alot but I didn't figure it out. anyway here's the solution

void calc( ) {
  int input[] = {3, 5, -1, -5, 4,3, -3}
  int sum = 0, largest = 0;
  for (int i = 0; i largest) largest = sum;
  }
  cout << largest;
}

This solution disregards the cases with all negative numbers, and empty array

moataz on Oct 5, 2012
1

Complete solution covering all -1 and returning the interval indexes:

 int [] arr = {-123,-3,-9,-222,-44,-1,-66};

     int currSeqLeft = 0;
     int currSeqRight = 0;
     int curr = arr[0];
     int largestSeqLeft = 0;
     int largestSeqRight = 0;
     int largest = arr[0];

     for (int i = 1; i = 0 ){
             curr += arr[i];
             currSeqRight = i;
         }

         if (curr > largest) {
             largest = curr;
             largestSeqLeft = currSeqLeft;
             largestSeqRight = currSeqRight;
         }
     }

     System.out.println(largestSeqLeft + "," + largestSeqRight);

ozitab on Nov 12, 2012
0

@moataz, that is not a good solution, it fails to identify the greater subinterval and also the maximum interval

Paul on Nov 18, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.