## Microsoft Interview Question for Applications Developers

Country: United States
Interview Type: In-Person

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

if sub-sequence then take all positive integers.
if sub-array, then this is a classic problem.

Comment hidden because of low score. Click to expand.
0

``oh baby!! what if all are negative numbers ? :D``

Comment hidden because of low score. Click to expand.
0

Then it depends. Does your definition of sub-sequence consists of the empty sequence? Is the sum of the empty sequence 0? Then answer is 0.

If you don't allow empty sequence, then pick the largest number.

Comment hidden because of low score. Click to expand.
0

If all are negative obviously the max sum will be 0 with no elements.

Comment hidden because of low score. Click to expand.
0

"Obviously"? A word often used by geniuses and fools.

Comment hidden because of low score. Click to expand.
0

how is sub-sequence different from sub-array?

Comment hidden because of low score. Click to expand.
0

Sub array means contiguous blocks and sub sequence means the elements may or may not be contiguous.

Comment hidden because of low score. Click to expand.
0

then i actually mean sub-array. Is there a way to change my question or may be drop this one and add a more appropriate one?

Comment hidden because of low score. Click to expand.
0

Then it is kadane's algo. Maximum sum subarray.

Anyway, go to your account, then go to questions tab. Find your question and you will find an edit option and edit this one. This problem is also good.

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

int find_max_sum(int *arr, int n)
{
int current_max, max_so_far,i;
int start=0,end =0;
current_max= max_so_far=0;

for(i=0;i<n,i++)
{
max_so_far+=a[i];
if(max_so_far<0){
max_so_far=0;start =++i;}
if(current_max<max_so_far)
{ current_max=max_so_far;
end = i;}
}
}
for(i=start;i<=end;i++)
printf("%d",arr[i]);
return;

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

Use dutch national flag algorithm. One thing is that it destroys the original array.

``````#include <stdio.h>
#include <limits.h>

void swap (int *a, int *b) {
int temp = *a ;
*a = *b ;
*b = temp ;
}

int maxSubSequence (int a[], int size) {
int i, high = size-1, start = 0, mid = 0;
int sum = 0, mid_flag = 0, max_min = INT_MIN;

/* Similar to dutch national flag */
while ( mid < high ) {
if ( a[mid] < 0 ) {
swap (&a[start], &a[mid]);

/* check for maximum of minimum */
if ( max_min < a[start] )
max_min = a[start] ;
start ++ ;
mid ++ ;
} else if ( a[mid] == 0 ) {
mid_flag = 1 ; /* denotes there is atleast one zero */
mid ++ ;
}
else {
swap (&a[mid], &a[high]) ;
sum += a[high] ; /* adds the sum */
high -- ;
}
}
if ( sum )
return sum ;
if ( mid_flag )
return 0 ;
return max_min ; // returns the maximum of all negative numbers
}

int main () {
int a[] = {-4, -9, 0, -3, -1, -2, 0, -2, -8} ;
int size = sizeof(a) / sizeof(a[0]) ;
printf ( "\nMaximum sum sub-sequence : %d\n", maxSubSequence(a,size)) ;
return 0 ;
}``````

Comment hidden because of low score. Click to expand.
0

No, u will destroy the array.

Question states "sub-array", u cant destroy the array itself.

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

for an array maintain a sum array where sum[i] will be sum of all elements from 0 to i-1
Once you do that, find out the 2 elements in this array whose difference is max.

for example
array 1 2-1 -9 11 23 0
sum 0 1 3 2 -7 4 27 27

here it will be 27 and -7 so answer would be subarray from index 4 to 6. There could be bugs regarding choosing right index but i hope you got the idea.

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

- Kadane's solution... O(n) time and O(1) space...

``````int find_max_sum(int *arr, int n)
{
int current_max, max_so_far,i;
current_max= max_so_far=0;

for(i=0;i<n,i++)
{
max_so_far+=a[i];
if(max_so_far<0)
max_so_far=0;
if(current_max<max_so_far)
current_max=max_so_far;
}
}``````

Comment hidden because of low score. Click to expand.
0

i forgot to insert the return stmt... after the loop exits, the value of current_max needs to be returned !

Comment hidden because of low score. Click to expand.
0

This gives max sub sequence sum, not the sequence itself. Should return start and end indices.

Comment hidden because of low score. Click to expand.
0

What if the sequence is "-2 , -1" ? For a sequence of negative numbers the answer would be zero i suppose as per the code.

Comment hidden because of low score. Click to expand.
0

All the numbers are negative case is the only special case,you can check for all the numbers are negative or not if negative return small negative integer otherwise proceed with kandens algo

Comment hidden because of low score. Click to expand.
0

If we keep

``````if(current_max<max_so_far)
current_max=max_so_far;``````

before checking less than 0 condition we can handle the all negative value input also

Comment hidden because of low score. Click to expand.
0

Kadane is used for sub-array. Here we want sub-sequence which is different from the sub-array.

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

``````pair<int, int> max_sub_sequence(const vector<int>& data) {
int curr_sum = 0;
int curr_start = 0;
int max_sum = -numeric_limits<int>::max();
pair<int, int> max_seq = make_pair(-1,-1);
for (int i = 0; i < data.size(); i++) {
curr_sum += data[i];
if (curr_sum > max_sum) {
max_sum = curr_sum;
max_seq = make_pair(curr_start, i+1);
}
if (curr_sum < 0) {
curr_sum = 0;
curr_start = i+1;
}
}
return max_seq;
}``````

Comment hidden because of low score. Click to expand.
0

May want to updated the condition (curr_sum > max_sum) with
(curr_sum >= max_sum)

Bug : try with a[10] = { -3, -4, -1, 0, -5}

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````public static int maximumSubArray(int[] array)
{
int max= array[0]>0?array[0]:0;
int trail= max;
for(int i=1; i<array.length; i++)
{
trail= trail + array[i]>array[i]? trail+array[i] : array[i];
max= max>trail?max:trail;
}
return max;
}``````

Comment hidden because of low score. Click to expand.
0

int max= array[0]>0?array[0]:array[0]-1;
would work if all the terms in the array are negative

Comment hidden because of low score. Click to expand.
0

The question was to return a sub-array, not its max sum?

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

#include "stdio.h"
#include "conio.h"

int main(){

int a[10]={-10,-2,3,-4,5,-1,0,8,-8,-11};
int max=a[0]-1;
int i,j,start,end,sum=0;
for(i=0;i<10;i++){
sum=0;
for(j=i;j<10;j++){

sum=sum+a[j];
if(sum>max){
max=sum;
start=i;
end=j;
}
}
}
printf("Max of the integers is %d starts at %d to %d ",max,start,end);
getch();
}

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

``````#include<stdio.h>
int p1,p2;
int maxsubarr(int arr[],int s)
{
int max=0,i,j,z,max_neg=arr[0];
int max_so_far=0;
for(j=1;j<s;j++)
{
if(arr[j]<0)
{
if(arr[j]>=max_neg)
{max_neg=arr[j];
p1=p2=j;}

}
else
break;
if(j==s-1)
{
return max_neg;}

}

if(j!=s-1){
for(i=0;i<s;i++)
{

max_so_far+=arr[i];
if(max_so_far<0)
{
max_so_far=0;
//z=i;
p1=i+1;
}
else if(max<max_so_far)
{
//if(z==i+1)
//p1=i;
max=max_so_far;
p2=i;
}

}
return max;
}
}
int main()
{
int s,p,i,max_neg;
int arr[]={-22,-6,-7,-41,-11,-51};
s=sizeof(arr)/sizeof(arr[0]);
printf("%d\n",maxsubarr( arr, s));
for(p=p1;p<=p2;p++)
printf("%d ",arr[p]);
//if all elements are negative

return 0;
}``````

Comment hidden because of low score. Click to expand.
0

code is valid even if all the elements are negative.

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

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

this is maximum subarray problem you have to do using dynamic programming refer cormen

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

public static int maxSmReturn(int[] num)
{
int maxSum=0, i;
int sum=0;
for(i=0;i<num.length;i++)
{
sum+=num[i];
if(maxSum<sum)
maxSum=sum;
if(sum<0)
sum=o;
}
return maxSum;
}

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

//i think recursion is best suited for this

#include<stdio.h>
#define SIZE 8
int max_left_index;
int max_right_index;

int max_sub_array(int A[],int,int);
int max_sub_crossing(int A[],int,int,int);
int main()
{
int A[SIZE],i,j;
printf("enter the element in the aarry");
for(i=0;i<SIZE;i++)
{
scanf("%d \n",&A[i]);
}
int low,high,mid;
low=0;
high=SIZE-1;
mid=(low+high)/2;
int s=max_sub_array(A,low,high);
printf("The max sum=[%d] \n",s);
printf("index of sax array=[i=%d]""[j=%d]",max_left_index,max_right_index);
return 0;
}

int max_sub_array(int A[],int low,int high)
{
int a,b,c,mid;

if(low==high)
return(A[low]);
else
{
mid=(low+high)/2;
a=max_sub_array(A,low,mid);
b=max_sub_array(A,mid+1,high);
c=max_sub_crossing(A,low,mid,high);
}
if(a>=b&&a>=c)
return(a);
else if(b>=a&&b>=c)
return(b);
else if(c>=a&&c>=b)
return(c);
}

int max_sub_crossing(int A[],int low,int mid, int high)
{
int i,j,k;
int leftsum=-10000000;
int sum=0;
for(i=mid;i>=low;i--)
{
sum=sum+A[i];
if(sum>leftsum)
{
leftsum=sum;
max_left_index=i;
}
}

int rightsum=-10000000;
sum=0;
for(j=mid;j<=high;j++)
{
sum=sum+A[j];
if(sum>=rightsum)
{
rightsum=sum;
max_right_index=j;
}
}
return(leftsum+rightsum);
}

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

``````The following function satisfy for all the cases.

int findMaxSubArraySum(int[] arr) {
int r=0, s=0;
for(int i = 0; i < arr.length; i++) {
s += arr[i];
if(r < s)
r = s;
else
s = 0;
}
return r;
}``````

Comment hidden because of low score. Click to expand.
0

Wont work for {10 -8 12}.

Comment hidden because of low score. Click to expand.
0

int _tmain(int argc, _TCHAR* argv[])
{
int array[] = {80,18,-56453,53,14,90,80,-70,100,105};
int size_of_array = sizeof(array);
std::cout<<"size_of_array"<<size_of_array<<std::endl;
int size_of_int = sizeof(int);
std::cout<<"size_of_int"<<size_of_int<<std::endl;
int n = sizeof(array)/sizeof(int);

int max_sum=0;
int sum=0;

for(int i = 0; i < n; i++)
{
//if (sum+array[i]>=max_sum) {sum=sum+array[i]; max_sum=sum;}
if (array[i]+array[i+1]>=max_sum) {sum=array[i]+array[i+1]; max_sum=sum;}
else sum=0;
}

std::cout<< max_sum;
getchar();
return 0;
}

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.

### 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.