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.

- Anonymous August 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- maverick August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Naveen Reddy Mandadi August 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

how is sub-sequence different from sub-array?

- Naveen Reddy Mandadi August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Psycho August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Naveen Reddy Mandadi August 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Psycho August 31, 2012 | Flag
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;

- rockstar August 28, 2012 | Flag Reply
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 ;
}

- Psycho August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No, u will destroy the array.

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

- Animesh Pratap Singh November 05, 2013 | Flag
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.

- Bruce October 27, 2012 | Flag Reply
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;
  }
}

- Rahul Arakeri August 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rahul Arakeri August 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Martin August 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rahul Balakavi August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Siva Krishna August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Venki August 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Psycho August 29, 2012 | Flag
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;
}

- Martin August 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

Your answer would be -3
correct answer 0

- Yogesh August 26, 2012 | Flag
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;
    }

- nj August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- mailsforsourav August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- videolaps December 21, 2017 | Flag
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();
}

- sourav August 26, 2012 | Flag Reply
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;
}

- Ashish Singh August 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

code is valid even if all the elements are negative.

- Ashish Singh August 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check for kadane algorithm :)

- shashank7android September 01, 2012 | Flag Reply
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

- t.deepak.iitg September 04, 2012 | Flag Reply
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;
}

- Anonymous September 28, 2012 | Flag Reply
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);
}

- Anonymous July 27, 2013 | Flag Reply
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;
}

- veeru August 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wont work for {10 -8 12}.

- nj August 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- Anonymous August 13, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More