Microsoft Interview Question


Country: United States




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

Well, how about this? .... Let the sum of all elements in the array be S. First, forget about the wrap-around case and find the max sum of the 1D array using the Kadane approach. Say its M. Next, modify the Kadane algo a bit to find the max negative sum. Say its -N. Now check if (S+N) > M. If yes, the answer is S+N, otherwise its M. I think this should work. However please let me know if you find any case for which this logic might fail.

- sam8dec February 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

looks like great logic....

- awan86 February 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

-9 -11 2 5 3 -12
sum=-9-11+2+5+3-12=-22

max neg sum=-22
-22+22=0
so acc to u
ans=0

while ans=10

- codez July 03, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey..nice one..looks like it works, but cant be sure unless ders a proof for it... can u prove it??

- chamy50 July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In response to codez's comment. I think we can do this in 2 iterations.
1) wraparound case : find total sum - most_negative_sum
2) normal Kadane algo

The maximum of the above should be the ans..Let me know what you guys this

- Mohit February 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

use kadane algo

- use kadane algo February 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

A simple solution is create a new array by concatenating the original one twice, 123 -123123

Now apply the usual one dimensional solution, with constraints like, start index < N, length <= N

- govind February 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 vote

Kadane's Maximum Sum in consecutive elements in a subarray.

- Sandipan February 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

well, the idea is correct but it's not going to work that easy: Remember the numbers are written on a *circle*.
while Kadane's algo just computes a maximal contiguous subsequence. How'd handle when you subsequence wraps around ?

- 111 February 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution to this is provided in stackoverflow question number 6047590.
max_start=0; max_end =0; maxv = 0; sum 0;
for i in range(arr):
sum+= arr[i];
if sum<0:
sum=0; max_start =i;
if maxv<sum:
maxv=sum; max_end = i;

#seocnd pass
for i in range(max_start):
sum+= arr[i];
if sum<0:
break;
if maxv<sum:
maxv=sum;max_end = i;

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

if I get it correctly, this algo can still miss some solutions:
Ie. consider {2, 5, -6, 3, 7}
after the first pass you'd have: max_start = 0, max_end = 4, maxv = 11. And the second pass is not executed since range(max_start) = 0. While the correct answer should be: 17.

- 111 February 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

To solve this problem, imagine that the array is triplied, I mean if we write 2, 5, -6, 3, 7 in the following way:
5, -6, 3, 7, 2, 5, -6, 3, 7, 2, 5, -6, 3. We can build an array with dimensions multiplied by 3 and It would O(3*n)=O(n).
The second and more efficient approach would be using modular numbers to transverse the array. The code could be the next:

int max=0; int tmp=0; int count=0;//We want to get at the maximum "length" numbers.
  for(int i=0;i<length*3;i++)
  {
     tmp=tmp+a[i%length];
    count++;
    if((tmp<0)||(count>length))
    {     
      tmp=0;count=0;
    }else if(tmp>max){
        max=tmp;
        
    }

  }

- gerardo.ruiz@aiesec.net February 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

[-3, 5, 6, -2, -2, 2, 2] max should be 12

- Anonymous February 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hint: modify the original DP solution in such a way to allow a max subsequence to
warp around. In each step check the length of subsequence. If it becomes greater than the size of array, move its left boundary. Remember that the max subsequence cannot from negative number!

- HINT February 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static int[] ReverseSubString(int[] Arr, int indx1, int indx2)
        {
            int Cnt = indx2 - indx1;

            for(int i=indx1; i<= indx1+(int)(Cnt/2);i++)
            {
                int tmp = Arr[i];
                Arr[i] = Arr[indx2 - (i - indx1)];
                Arr[indx2 - (i - indx1)] = tmp;
            }

            return Arr;
        }

       

        public static int FindMax(int[] Arr, int Cnt)
        {
            int MaxSum = 0;
            int TillSum = 0;

            for (int i = 0; i <Cnt ; i++)
            {
                TillSum = (TillSum + Arr[i] > 0) ? TillSum + Arr[i] : 0;
                MaxSum = (TillSum > MaxSum) ? TillSum : MaxSum;
            }

            return MaxSum;
        }

        public static int[] ReverseInCyle(int[] Arr, int Cnt)
        {
            int MidIndx = (int)Cnt / 2;           
            Arr = ReverseSubString(Arr, 0, MidIndx);
            Arr = ReverseSubString(Arr, MidIndx + 1, Cnt - 1);
            return Arr;
        }

        static void Main(string[] args)
        {

            int[] numbers = new int[10];
            numbers[0] = 1;
            numbers[1] = 14;
            numbers[2] = 11;
            numbers[3] = -2;
            numbers[4] = 9;
            numbers[5] = 4;
            numbers[6] = -5;
            int Cnt = 7;

            int Max1 = FindMax(numbers, Cnt);

            numbers = ReverseInCyle(numbers, Cnt);     

            int Max2 = FindMax(numbers, Cnt);

            int Max = Max2 > Max1 ? Max2 : Max1;

            Console.WriteLine(Max);
        }
    }

This will find the max in a circular way. The idea here is to first find max & then shift the array in circular way & again find the max. For e.g. {1,2,3,-4,5,6,-9} .. The first max will be
13. Then on circular shift, it will be {3,2,1,-9,6,5,-4}. Here the max will be 11. The max of both is 13. So answer is 13. The above code does the same. it's in c sharp. Let me know if it won't work under any cases?

- Hunter February 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

[-3, 5, 6, -2, -2, 2, 2]
-------------------------------------------------------------------------------
-3,5,11,9,7,9,11 < Maximum sub sequence at a given point>
Now do a wrap around
8 , End,

let us examine from where the sequene starts it is from 5

Are they any negetive numbers in between?
yes -2,-2

After every negetive number start the maximum subsequence again with hope that it may find more positive during wrap around..............(we can also optimize a bit here )

- Anonymous February 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the index of the smallest value and just skip it.
For example: { 2, 5,6, -15, 11, -10, 15}
The normal running sum wound be [ 11, -10, 15] = 16
The smallest index is 3 (-15).
if the index is at 3, increment it to 4.
The result is 29. { 11, -10, 15, 2, 5, 6 }

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

what if there is -6 in place of 6.
ur code will return answer=17
but the answer should be 23

- anshum June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The main idea is to wrap around the max sum..
1.find the max sum n nos using kadane's algo
2.Use DP to remember Max sum's
3.wrap around the sum..i.e start from each no
4.if the 1st no is -ve remove the no from max sum

eg..
-3 5 6 -2 -2 2 2

1.find max sum for the sq->11
2.start including circula wise start from 5 and include -3 in the sum element include .store the sum in a DP.
3.when startng from a -ve no dont include it in sum.For the array starting in -2 dont include it

finally max of DP array will give u the sum

content of DP array 11 8 8 10 12 10 8

hope u got my approach its O(n) with extra space of n

- hmmm February 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think so that its O(N) , You are visiting every node N times .. So it will be O(N * N)=O(N2)

- Nitin March 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the solution I think can work to get O(n) but will add a space of N (without any optimization) of array which is definitely better than using a hashtable or any other expensive inbuilt construct I think.
For each index in array A starting from 0, keep track of maxSum value and currentSum values for an index using two separate arrays say Current[n] and Maximum [n]. For each index i in A, keep updating the value of Current[] and update Maximum[] if exceeing the previous maximumsum for valid/qualified indexes which have been visited(started) once and have not been touched again yet. After we finish two rounds of trversals on array (with wrap around) we should have an answer for the maximum value for a given index from array Maximum[] i.e;Maximum[maxValueIndex]. Complexity is O(2n) for traversal + O(n) to look for max value in Maximum Array = O(3n) == O(n).

One can cut down on the memory space requirement by counting the number of +s numbers as those are the only valid starting point.

Here is more optimized solution.

The space requirement can greatly optimized by condensing the initial array's + and -patches and using a new array which sould be in the format
+, -,+ -,.....
or
-, +, -, +,.....
and having the Maximum and Minimum array lengths only for the number of positive numbers as negative condensed sums don't qualify as desireable staring points in my opinion.

As an example for overall optimized solution
{-3, 5, 6, -2, -2, 2, 2} = {-3,11,-4,4} --> Condensed Array. --> doesn't need to be actually created.
MAXIMUM={8,12} --> only for + starting points being useful.
Value of Current[] after each starting index complete cyclic iteration.(only for + values in condensed array)
CURRENT={8,8} --> only for +ve staring points as mentioned above.
Finally after searching in MAXIMUM for maximum value, we find that maximum value is for the second positive patch in original array starting at index 5.

Maximum Space complexity for the condensed solution = N for an original pure alternating pattern of +,-,+, -....for any other original pattern say +++,--,...etc, extra space complexity is less than n so O(N).

Note we don't actualy need to store the condensed array as it can be computed during run time by adding the patches. Time complexity is O(N)

Another Example as mentioned above
{2, 5, -6, 3, 7}. == {7,-6,10} --> Condensed
CURRENT={11,11}
--> Current array values after each complete iteration for positive patch would be always same.
MAX={11,17} --> 17 maximum value for second postive patch.

Another example discussed above.
{ 2, 5,6, -15, 11, -10, 15}== {13,-15,11,-10,15}
MAXIMUM={14,29,28} --> 29 is the max value starting at second positive patch.
current={14,14,14}

- rahulssk February 11, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

excellent solution. thank you!!!

- Anonymous February 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple solution will be to
1) create an array of size twice that of original one
2) copy the original array to new array twice. For example if the initial array is 1 2 3, new array is 1 2 3 1 2 3.
3) Now solve it normally like we do for non circular ones. The only constraint is the start of the max sequence should be < n (size of original array) and its length should be < n

- govind February 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

jdjjd

- jdjjd February 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;

int dp[1000];
int pos[1000];

int MaxSum(int* input, int num)
{
	int* dupInput = (int*)malloc(2*num*sizeof(int));

	for(int i = 0;i < num; i++)
	{
		dupInput[i] = input[i];
		dupInput[i + num] = input[i];
	}

	dp[0] = dupInput[0];
	pos[0] = 0;

	for(int i = 1; i < 2*num; i++)
	{
		if(dp[i-1]>0)
		{
			dp[i] = dupInput[i] + dp[i-1];
			pos[i] = pos[i-1];
		}
		else
		{
			dp[i] = dupInput[i];
			pos[i] = i;
		}
	}

	int max = -1000000;

	for(int i = 0; i < 2*num; i++)
	{
		if(dp[i] > max && i - pos[i] < num)
			max = dp[i];
	}

	return max;
}


int main()
{
	int a[] = {8, -8, 9, -9, 10, -11, 12};

	cout << MaxSum(a, 7) << endl;

	char c;
	cin >> c;

	return 1;
}

- qsgh February 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;

int dp[1000];
int pos[1000];

int MaxSum(int* input, int num)
{
	int* dupInput = (int*)malloc(2*num*sizeof(int));

	for(int i = 0;i < num; i++)
	{
		dupInput[i] = input[i];
		dupInput[i + num] = input[i];
	}

	dp[0] = dupInput[0];
	pos[0] = 0;

	for(int i = 1; i < 2*num; i++)
	{
		if(dp[i-1]>0)
		{
			dp[i] = dupInput[i] + dp[i-1];
			pos[i] = pos[i-1];
		}
		else
		{
			dp[i] = dupInput[i];
			pos[i] = i;
		}
	}

	int max = -1000000;

	for(int i = 0; i < 2*num; i++)
	{
		if(dp[i] > max && i - pos[i] < num)
			max = dp[i];
	}

	return max;
}


int main()
{
	int a[] = {8, -8, 9, -9, 10, -11, 12};

	cout << MaxSum(a, 7) << endl;

	char c;
	cin >> c;

	return 1;
}

- qsgh February 13, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaxCircularSubArraySum {
	private static int findMaxSubArraySum(int a[]) {
		int maxSum = Integer.MIN_VALUE, maxSumSoFar = 0;
		int minSum = Integer.MIN_VALUE, minSumSoFar = 0;
		int totSum = 0;
		boolean zeroExists = false;
		for (int i = 0; i < a.length; ++i) {
			if (a[i] == 0) {
				zeroExists = true;
			}
			totSum += a[i];

			if (minSumSoFar < 0) {
				minSumSoFar = 0;
			}
			minSumSoFar += -a[i];
			if (minSum < minSumSoFar) {
				minSum = minSumSoFar;
			}

			if (maxSumSoFar < 0) {
				maxSumSoFar = 0;
			}
			maxSumSoFar += a[i];
			if (maxSum < maxSumSoFar) {
				maxSum = maxSumSoFar;
			}
		}

		int ret = (maxSum < totSum + minSum) ? totSum + minSum : maxSum;
		if (!zeroExists & ret == 0) {
			ret = maxSum;
		}
		return ret;
	}

	public static void main(String[] args) {
		System.out.println(findMaxSubArraySum(new int[] { 8, -8, 9, -9, 10,
				-11, 12 }));
		System.out.println(findMaxSubArraySum(new int[] { 1, 2, 3, 4, 5 }));
		System.out
				.println(findMaxSubArraySum(new int[] {0, -1, -2, -3, -4, -5 }));
	}
}

- kartikaditya February 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void modifiedKadane (int elements [], int length )
{
        int maxSum = -1;
        int currentSum = 0;
        int maxStartIndex = 0, maxEndIndex = 0, s = 0, i = 0;

		/*
		 * Run algorithm for twice the length of the array to get the circular input effect.
		 */
        for (i = 0; i < 2 * length;  ++i)
        {
				/*
				 * Check to see if the numbers of elements used to get maxSum is not greater than length.
				 */
                if (i - s == length)
                {
                        currentSum = 0;
                        s = s + 1;
                        i = s;
                }

				/*
				 * Classic Kadane's algorithm.
				 */
               currentSum = currentSum + elements [i % length];
                if (currentSum > maxSum)
                {
                        maxSum = currentSum;
                        maxStartIndex = s;
                        maxEndIndex = i;
                }

                if (currentSum < 0)
                {
                        currentSum = 0;
                        s = i + 1;
                }
        }

        printf ("Sum = %d Start = %d End = %d\n", maxSum, maxStartIndex % length, maxEndIndex % length);
}

- Rajiv February 21, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As people suggested above, use DP:
1. Matrix A where row denotes the starting position and column denotes the element no. upto which sum is calculated.
Eg. A[5,3] = Sum of elements starting from 5th element to the 3rd element (considering elements are in circle)

A[N,K] = A[N,K - 1] + A[K,K] ... If K > 0
A[N,0] = A[N, last] + A[0,0] ... because of rounding sum

Remember the max entry in array and thus we can tell the start and end of sequence:
if A[X,Y] is max then array starts from X and ends in Y.

- Anonymous February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

As people suggested above, use DP:
1. Matrix A where row denotes the starting position and column denotes the element no. upto which sum is calculated.
Eg. A[5,3] = Sum of elements starting from 5th element to the 3rd element (considering elements are in circle)

A[N,K] = A[N,K - 1] + A[K,K] ... If K > 0
A[N,0] = A[N, last] + A[0,0] ... because of rounding sum

Remember the max entry in array and thus we can tell the start and end of sequence:
if A[X,Y] is max then array starts from X and ends in Y.

- Anonymous February 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int i=0;i<n;i++){
sum+=arr[i];

if(sum>sum_max){
sum_max=sum;
//sum=0;
}
else if(sum<sum_max)
sum=0;
}

I can bet this is the best answer.

- Raj May 28, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Duh ! Use Kadane's algo... A very simple DP approach... O(n) time and O(1) space. Google it... :)

- Rahul Arakeri August 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

this is easy

int currentMax = 0;
int maxSoFar = 0;

for (int i = 0; i < array.size() * 2 - 1; i ++)
{
currentMax += array[i % array.size()];
if (currentMax > maxSoFar)
maxSofar = currentMax;
if (currentMax < 0)
{
if ( i >= array.size())
break;
currentMax = 0;
}
}

- sam February 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

below example wont work for this code, answer is 17, but it is giving 18 because it is counting same elements twice
{2, 5, -6, 3, 7}

- Anonymous February 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 3 vote

If we find the least element in the array and make that our start or head pointer.. then we start summing up from that location using the following logic:

S(n): where S(n) is the max sum of the array ending a i'th index.

S(n) = Max { element(n), element(n) + S(n-1) }

So, for the 1st example, the arrays look like:

element(): {8,-8,9,-9,10,-11,12}. Here in the first linear pass, we find the least value element (which in this case is -11). We start couting from -11. So for simplicity sake, let us imagine the element() as:
{-11,12, 8,-8,9,-9,10}
S() : {-11,12,20,12,21,12,22}. now do a linear traversal to find the max sum in S()

For the 2nd example, we have the following:

element(): {2, 5, -6, 3, 7}. Again finding the least element in this array and starting from there, we have elements() as {-6, 3, 7, 2, 5}

So, S(n): {-6,3,10,12,17}

hence, the max is 17

- Jester February 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Jester: Nice solution, but it requires altering the original array (or creating new array to have a sequence starting from minimum element).
Most elegant solutions don't modify the input data.

- Learner February 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Learner we are not modifying the original array. im just using an extra node* to refer to the pseudo-starting location of the list. so the only overhead i incur is initializing thus pointer to the address of the least element. after the summation is done, memory occupied by this pointer is freed.

so we're not modifying the original list or creating a new one.. just one new pointer

- Jester February 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

[-3, 5, 6, -2, -2, 2, 2] max should be 12 ?

- ? February 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Jester, nice solution, but your algo would give an incorrect value to the above input.
i.e [-3, 5, 6, -2, -2, 2, 2] -> your algo gives 11 as the solution, whereas the correct answer should be 12.

- ayan_2587 February 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

@Jester: Just trying to correct my understanding here.
We are using a pseudo start pointer for the minimum value in the array. And thereafter we are calculating S(n) as in dynamic programming recursively. Right? I think thats what your algo indicates to me. Anyways, nice solution.

- Learner February 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

i guess divide and conquer can be used .....

- kushagr February 07, 2012 | 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