Microsoft
3.6 of 5
www.microsoft.com Redmond, WA 5000+ Employees

# MicrosoftSoftware Development Engineer (SDE) Interview Question (student candidate)

"1- Given an array of integers, positive and negative. find an interval in that array, whose elements constitutes the maximum sum"

Part of a Software Development Engineer (SDE) Interview Review - one of 2,772 Microsoft Interview Reviews

1
of 2
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 < input.size(), i++) {
sum += input[i];
if (sum < 0) sum = 0;
if (sum > largest) largest = sum;
}
cout << largest;
}

This solution disregards the cases with all negative numbers, and empty array
- moataz on Oct 5, 2012 Flag Response
1
of 1
vote
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 < arr.length; i++) {

if (arr[i] < 0 && i != arr.length - 1) {
currSeqLeft = i + 1 ;
currSeqRight = i + 1;
curr = arr[i+1];
} else if (arr[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 Flag Response
0
of 1
vote
@moataz, that is not a good solution, it fails to identify the greater subinterval and also the maximum interval
- Paul on Nov 18, 2012 Flag Response

### Microsoft – Why Work for Us?

What do you want in a job? Do you want more than a paycheck? At Microsoft, you can discover potential you didn’t know you had, push your limits, turn your ideas into reality and make a real impact on the industry and…

Provided by employer [?]

### Salaries by Company

Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Microsoft interview questions and advice. All interview reviews posted anonymously by Microsoft employees and interview candidates.