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

- Sarthak Mall June 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- FoY January 26, 2014 | Flag
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;
    }
}

- SkyClouds May 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

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

- parthi May 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 votes

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

- veronica June 01, 2013 | Flag
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]);
}

- Shaibujan May 06, 2013 | Flag Reply
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;
}

- Time Pass May 16, 2013 | Flag Reply
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
            };
        }

- alexey May 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

great buddy

- parthi May 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- SK June 08, 2013 | Flag
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;
        }

- Anonymous June 05, 2013 | Flag Reply
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");
        }
}

- SK June 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 :)

- SK June 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Time Pass June 16, 2013 | Flag
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);
    }

- Novice June 16, 2013 | Flag Reply
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;
}

- Schedl August 01, 2013 | Flag Reply
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;
}

- Anonymous August 12, 2013 | Flag Reply


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