Microsoft Interview Question
Software Engineer in TestsTeam: Server and tools in microsoft erp
Country: United States
Interview Type: In-Person
int getMaxSum(int *arr, size_t len, size_t &start, size_t &end) {
start = end = 0;
size_t ti = 0;
int sum = 0;
int max_sum = 0;
for(size_t i = 0; i < len; ++i) {
sum += arr[i];
if(max_sum < sum) {
max_sum = sum;
start = ti;
end = i;
} else if(sum < 0) {
sum = 0;
ti = i + 1;
}
}
return max_sum;
}
private void getBiggestSumSubset(int []arr){
int sum = 0;
int max =0;
for (int i = 0; i < arr.length-1; i++) {
for(int j=i+1;j<arr.length;j++){
sum=0;
for(int k=i;k<j;k++){
sum = sum+arr[k];
}
if(sum>max){
max=sum;
System.out.println("i="+i+"=j="+j);
System.out.println("arr[i]="+arr[i]+"=arr[j]="+arr[j]+"=max="+max);
}
}
}
}
private void getBiggestSumSubset(int []arr){
int sum = 0;
int max =0;
for (int i = 0; i < arr.length-1; i++) {
for(int j=i+1;j<arr.length;j++){
sum=0;
for(int k=i;k<j;k++){
sum = sum+arr[k];
}
if(sum>max){
max=sum;
System.out.println("i="+i+"=j="+j);
System.out.println("arr[i]="+arr[i]+"=arr[j]="+arr[j]+"=max="+max);
}
}
}
}
#include<stdio.h>
int main()
{
int *arr,n,sum=0,max=0,o_start,o_end,c_start=0,i;
scanf("%d",&n);
arr=malloc(n*sizeof(int));
for(i=0;i<n;i++)
scanf("%d",arr+i);
for(i=0;i<n;i++)
{
if(arr[i]<0)
{
if(sum>max)
{
max=sum;
o_start=c_start;
o_end=i-1;
}
}
if(sum+arr[i]<=0)
{
c_start=i+1;
sum=0;
}
else
sum=sum+arr[i];
}
if(c_start==i)
printf("no +ve elements\n");
else
{
if(sum>max)
{
o_start=c_start;
o_end=i-1;
}
printf("start-->%d , end-->%d\n",o_start,o_end);
}
}
The O(n) solution is using Kadane's algorithm
- Anonymous April 22, 2012