Interview Questions

Microsoft Interview Question for Software Engineers about Algorithm Arrays Coding

Microsoft Interview Questions and Answers


(Continued from previous question...)

Microsoft Interview Question for Software Engineers about Algorithm Arrays Coding

Question:
Find the maximum continuous sum in an array. The array will contain at least one positive integer. Report the actual sequence. If there are multiple sequences report any one.


maybe an answer:
Look below the code in java. It will print the sequence which makes longest sequence.But first the array need to be sorted.

static void getMax(int[] a)
{
int len=a.length;
int insq=0;
int count=0;
int maxcount=0;
int startin=0;
int endin=0;
for (int i=0;i<len-2;i++)
{
if (a[i+1]==a[i]+1)
{
insq=1;
count=0;
int subcount=0;
while(a[i+1]==a[i]+1)
{
count+=a[i];
i++;
subcount++;
}
count+=a[i];
if(maxcount<count)
{
maxcount=count;
startin=i-1;
endin=i+subcount-1;
}
}
}

System.out.printf("Sequence= ");
/*System.out.println(endin);*/
for (int p=startin;p<=endin;p++)
{
System.out.print(a[p-1]);
System.out.print(",");
}
System.out.printf("maximum size=%s", maxcount);
}


maybe an answer:
here is an O(N)solution max contain the maximum sum and maxstart and maxend contains the indexes whose sum is maximum

{{{
maxsum(int a[],int n)
{
int sum=0,maxsum=0,start=0,end=0,maxstart,maxend;
for(int i=0;i<n;i++)
{
sum=sum+a[i];
if(sum<0)
{
sum=0;
start=i+1;
}
if(sum>max)
{
max=sum;
maxstart=start;
maxend=end;
}
}

(Continued on next question...)

Other Interview Questions