## Microsoft Interview Question for SDE1s

Country: United States
Interview Type: In-Person

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

If all the elements are -ve than print the one having smallest magnitude
else
take into account only +ve numbers.

``````#include<iostream>
using namespace std;
void maxsum(int arr[],int size);
int main()
{
int arr[] = {-23, -45, 78, 67, 45, 78, 23, -67, -45};
int size = sizeof(arr)/sizeof(arr[0]);
maxsum(arr,size);
return 0;
}
void maxsum(int arr[],int size)
{
int i,max;
for(i=0;i<size;i++)
{
if(arr[i]>=0) break;
}
if(i==size)
{
max = arr[0];
for(i=1;i<size;i++)
if(max<arr[i]) max = arr[i];
cout <<max;
}
else
{
bool a[size];max = 0;
for(i=0;i<size;i++) a[i] = false;
for(i=0;i<size;i++)
{
if(arr[i]>=0)
{
a[i] = true;
max += arr[i];
}
}
cout<<"Max Sum = "<<max<<"\nAnd the sequence is...\n";
for(i=0;i<size;i++)
if(a[i]) cout<<arr[i]<<" ";
}
}``````

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

I think the question actually means you have to find *contiguous* numbers in the array that give the highest sum. That's what I get from it when he asks to find a "subsequence". Not to form one out of the elements.

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

``````public static find_max_subarray(int[] a) {
// check arguments
if(a == null || a.Length == 0) throw new ArgumentNullException();

int max = a[0], tmp_max = a[0];
foreach(var i in a) {
if(tmp_max < 0) {
tmp_max = i;
} else {
tmp_max += i;
}
max = tmp_max > max ? tmp_max : max;
}
}``````

Comment hidden because of low score. Click to expand.
-2

hey buddy! check your code for {-6,2,-1,2,11} . It says 14.but answer is 13

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

@skyclouds, nice solution; @parthi, you are totally wrong!

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

``````int main ()
{
int arr[] = {-23, -45, 78, 67, 45, 78, 23, -67, -45};
int max_sum = 0, max_pos = 0, max_sz = 0;
int arr_sz = sizeof(arr)/sizeof(int);
for(int i=0; i < arr_sz; i++)
{
int sum = 0;
int cur_sz = arr_sz - i;
for(int j=0; j < cur_sz; j++)
{
sum += arr[i + j];
if(sum > max_sum)
{
max_sum = sum;
max_pos = i;
max_sz = j + 1;
}
}
}

for(int i = max_pos; i < max_pos+max_sz; i++)
printf("%d ", arr[i]);
}``````

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

``````int subseq (int array[], int length) {
int sum[length], i, j, max;
sum[0] = array[0];
for (i=1;i<length;i++) {
j = i - 1;
while (j >= 0) {
if (array[j] < array[i]
&& (sum[j] + array[j]) > sum[i]) {
sum[i] = sum[j] + array[j];
}
--j;
}
}
max = sum[0];
for (i=1;i<length;i++) {
if (max < sum[i])
max = sum[i];
}
return max;
}``````

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

``````static int[] Subsequence(int[] A)
{
int maxStart = 0;
int maxEnd = A.Length - 1;
int maxSum = 0;

int start = -1;
int end = 0;
int sum = 0;

for(int i = 0; i < A.Length; i++)
{
if(A[i] >= 0 && start < 0)
{
start = i; end = i; sum=A[i];
}
else if(A[i] >= 0 && start >= 0)
{
end = i; sum += A[i];
}
else if (A[i] < 0 && start >= 0)
{
if(sum > maxSum)
{
maxSum =sum;
maxStart= start;
maxEnd = end;
}

start = -1;
}
}

//last sum
if (start >= 0 && sum > maxSum)
{
maxSum = sum;
maxStart = start;
maxEnd = end;
}

return new int[]
{
maxSum,
maxStart,
maxEnd
};
}``````

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

great buddy

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

1) it wont work for all negatives in array
2) it wont work if max subarray will include negatives as you have not taken negative values into consideration. (example given above by parthi, {-6,2,-1,2,11} ). Here max should be 14, your code will return 13

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

``````public static int MaxSequenceSum(int[] nums)
{
if (nums == null || nums.Length == 0)
{
throw new ArgumentException();
}

if (nums.Length == 1)
{
return nums[0];
}

int sum = 0;
int maxSum = nums[0];
int lastEnd = 0;

for (int i = 0; i < nums.Length; i++)
{
if (nums[i] > 0 && lastEnd == i - 1)
{
sum += nums[i];
++lastEnd;
}
else if (nums[i] > 0 && lastEnd < i - 1)
{
sum = nums[i];
lastEnd = i;
}
else if (nums[i] < 0)
{
if (lastEnd != 0)
{
if (maxSum < sum)
{
maxSum = sum;
}
}
else
{
if (maxSum < nums[i])
{
maxSum = nums[i];
}
}
}
}

return maxSum;
}``````

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

Divided algo in few parts:
part 1:
1) get minimum negative value
2) get first positive sum of array
3) get start & end index of first positive sum
this will be current running sum
part 2:

``````1) get sum of all negative values
2) get sum of all positive values
3) compare current_sum with curr_sum + positive_sum + negative_sum
if max_sum < (curr_sum + positive_sum + negative_sum)
update max_sum
else
update curr_sum
if max_sum < positive sum
update max_sum with positive sum
4) also keep on updating indexes``````

I have written code, due to keep track of index, code has become little messy
please update me with compact code, if u have

``````void maxSubSeq (int *a, int n)
{
int max = -1;
int i = 0;
int max_e_i = 0;
int cur_s_i = 0;
int cur_e_i = 0;
int pos = 0;
int neg = 0;
int cur = -1;
int max_s_i = -1;
int l_n_v = -10000;
int next_p_index = 0;
int neg_i = 0;

while (i < n)
{
if (a[i] < 0 && a[i] > l_n_v && cur < 0)
{
l_n_v = a[i];
neg_i = i;
i++;
continue;
}

if (cur > 0 && a[i] < 0)
break;
if (a[i] >= 0)
{
cur = 0;
while (i < n && a[i] >= 0)
{
if (max_s_i < 0)
max_s_i = i;
cur += a[i];
i++;
}
break;
}
i++;
}
if (cur >= 0)
{
max = cur;
max_e_i = i-1;
}

while (i < n)
{
neg = 0;
pos = 0;

while (i < n && a[i] < 0)
{
neg += a[i];
i++;
}
if (i < n)
next_p_index = i;

while (i < n && a[i] > 0)
{
pos += a[i];
i++;
}

if ((cur + neg + pos) > max)
{
cur = max = cur+neg+pos;
cur_e_i = max_e_i = i-1;
}
else
{
cur = cur+pos+neg;
cur_e_i = i-1;
}
if (max < pos)
{
cur = max = pos;
cur_s_i = max_s_i = next_p_index;
}
}

if (max == -1)
{
printf ("no Positive sum. Least negative value is: %d at index: %d\n", l_n_v, neg_i);
}
else
{
printf ("Max sum is: %d\n", max);
printf ("Max SubSequence is: \n", max);
for (i = max_s_i; i <= max_e_i; i++)
printf ("%d ", a[i]);
printf ("\n");
}
}``````

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

I have run it for the following test cases:

``````int a[] = {-1,-2,1,3,11,-10,-3,1,-9,2,11,13,-11,25};
int a[] = {10,11,-15,-20,2,3,-7,15,30,-1,10,-1,30};
int a[] = {-20,-30,-40,-2,-9,-13};
int a[] = {-20,-30,-40,-1,0,-9,-13};
int a[] = {3,4,-3,1,-2,1,-1,-1,-1,-1,-1};
int a[] = {3,4,-3,1,-2,25,-1,-1,-1,-1,-1};``````

Update me for other tricky cases :)

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

//@saurabh. Your code looks good but you have used too many variables. Here is a simple one. Mine doesn't work for all -ve numbers because you don't need to handle that case because you won't have a seq in -ve numbers.

``````int* subseq(int *array, int length) {
int i = 0, max = 0;
int* new_array = (int *)malloc(sizeof(int*(length+1)));
new_array[0] = 0;
if (array == NULL || length == 0)
return;
for(i=0;i<length;i++) {
if((new_array[i] + array[i]) >= 0) {
new_array[i+1] = new_array[i] + array[i];
max = (max >= new_array[i+1]) ? max : new_array[i+1];
}
else
new_array[i+1] = 0;
}
return new_array;
}``````

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

This code find the max sum with the locations:

``````public void maxSubSeq(int[] data){
int s = 0, a = 0, b = 0, sum = 0, maxSum = 0;
for(int i = 0; i < data.length; i++){
sum = sum + data[i];
if(sum < 0){
sum = 0;
s = i + 1;
}
else if(sum > maxSum){
maxSum = sum;
a = s;
b = i;
}
}
System.out.println("Max sum is: " + maxSum + "  from location " + a + " to " + b);
}``````

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

I don't understand your code. I think you need 3 loops. At least my Code works.

struct index
{
int index_left,index_right;
};

index findLargestSubsequence(int arr[],int len)
{
int index_left=0;
int index_right=0;
int max_sum=0;
int sum = 0;
index my_index;

for(int i = 0 ; i<len ; i++)
{
for( int k = i ;k<len ; k++)
{
for( int j = i ; j<=k ; j++)
{
sum += arr[j];
}

if(sum > max_sum)
{
max_sum = sum;
index_left = i;
index_right = k;
}
sum=0;
}
}
my_index.index_left = index_left;
my_index.index_right = index_right;
return my_index;
}

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

public static long maxSumSequence(int[] arr){
long sum = arr[0];
long oldsum = arr[0];
for (int i = 1; i < arr.length; i++){
long newsum = arr[i], tempsum = sum + arr[i];
if(tempsum < sum){
if (oldsum < sum) oldsum = sum;
sum = newsum;
}else{
if ((newsum > tempsum) && (newsum > sum)) sum = newsum;
if ((tempsum > sum) && (tempsum > newsum)) sum = tempsum;
}
}
if (sum > oldsum)return sum;
return oldsum;
}

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.