Microsoft Interview Question for Software Engineer Interns


Country: United States
Interview Type: Written Test




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

Use Kadane algorithm.

- nascent November 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public int Calculate(int[] array)
        {
            if (array == null || array.Length == 0)
                throw new ArgumentException();

            int max = array[0];

            for (int i = 1; i < array.Length; i++)
                max = Math.Max(max, Math.Max(array[i], array[i] + max));

            return max;
        }

- SM December 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this won't work in the case of [3,-2,5]. the max is 6 (arrays 0 to 2) but this function would return 5

- AdamF December 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh, you right. Thanks fot the note!
Mismatched the task. Solution is valid for sub-set of a set, but not for sub-array.

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

So would the solution to this be:
max = Math.Max(max, Math.Max(0, array[i] + max));

- Anonymous September 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Below is the python script, algorithm is simple I've commented so you could understand:

a = [1, 4, -5, -4, -8]

# max sum array indexes
n1=n2=0

# current positive array indexes
c1=c2=0

# maxium sum so far
m_sum=float("-inf")

# current sum
p_sum=0

for i in range(0, len(a)):
# current sum index
c2=i
p_sum = p_sum + a[i]
# current sum got larger then max sum
if p_sum > m_sum:
m_sum=p_sum
(n1, n2)=(c1, c2)

# if sum is -ve then don't carry it
if p_sum < 0:
p_sum=0
c1=i+1


print 'Max sum: %d, from index [%d - %d]'%(m_sum, n1, n2)

- Shivam kalra November 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

I put again the code, sorry about last post it does not format properly for the code.

a = [1, 4, -5, -4, -8]

# max sum array indexes                                                                                                
n1=n2=0

# current positive array indexes                                                                                       
c1=c2=0

# maxium sum so far                                                                                                    
m_sum=float("-inf")

# current sum                                                                                                          
p_sum=0

for i in range(0, len(a)):
    # current sum index                                                                                                
    c2=i
    p_sum = p_sum + a[i]
    # current sum got larger then max sum                                                                              
    if p_sum > m_sum:
        m_sum=p_sum
        (n1, n2)=(c1, c2)

    # if sum is -ve then don't carry it                                                                                
    if p_sum < 0:
        p_sum=0
        c1=i+1


print 'Max sum: %d, from index [%d - %d]'%(m_sum, n1, n2)

- Anonymous November 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Progamming Language Used : PHP
 * Algorithm Used : Kadane's algorithm
 * 
 * This method computes the maximum sum of subarray from the given array.
 * 
 * @return int sum of sub array
 * 
 * @author Varun Jalandery <varun.jalandery@gmail.com>
 */
function maximumSumOfSubArray(array $numbers)
{
    // Initialize variables here
    $maxSoFar = 0;
    $maxEndingHere = 0;
    for ($i = 0; $i < count($numbers); $i++) {
        $maxEndingHere += (int) $numbers[$i];
        if ($maxEndingHere < 0) {
            $maxEndingHere = 0;
        } else {
            $maxSoFar = $maxEndingHere;
        }
        if ($maxSoFar < $maxEndingHere) {
            $maxSoFar = $maxEndingHere;
        }
    }
    return $maxSoFar;

}

- Varun Jalandery November 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

/**
 * Progamming Language Used : PHP
 * Algorithm Used : Kadane's algorithm
 * 
 * This method computes the maximum sum of subarray from the given array.
 * 
 * @return int sum of sub array
 * 
 * @author Varun Jalandery <varun.jalandery@gmail.com>
 */
function maximumSumOfSubArray(array $numbers)
{
    // Initialize variables here
    $maxSoFar = 0;
    $maxEndingHere = 0;
    for ($i = 0; $i < count($numbers); $i++) {
        $maxEndingHere += (int) $numbers[$i];
        if ($maxEndingHere < 0) {
            $maxEndingHere = 0;
        } else {
            $maxSoFar = $maxEndingHere;
        }
        if ($maxSoFar < $maxEndingHere) {
            $maxSoFar = $maxEndingHere;
        }
    }
    return $maxSoFar;
}

- Varun Jalandery November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The code seems wrong to me. The answer to [2, -3, 1] should be 2 but I think the code will return 1?

- Sunny December 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the same posted by Varun Jalandery with a extra variable

public static void maximumSumOfSubArray(int[] numbers)
{
// Initialize variables here
int maxSoFar = 0;
int maxEndingHere = 0;
for (int i = 0; i < numbers.length; i++) {
int prevsum = maxEndingHere;
maxEndingHere += (int) numbers[i];
if (maxEndingHere <= 0) {
maxEndingHere =prevsum;

} else {
maxSoFar = maxEndingHere;
}
if (maxSoFar < maxEndingHere) {
maxSoFar = maxEndingHere;
}
}
System.out.println(maxSoFar);
}

- nivedha December 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In some sense, books like "cracking the.." and websites like this one add to the problem of allowing mediocre people beat out the really creative geniuses (who don't check careercup every week) in interviews.

There are a average folks who spend a lot of time here who would probably beat out Ken Thompson in these cookie cutter interviews.

- msft needs to improve December 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int maxSumSubArr(ArrayList<Integer> list){
	int ret = 0;
	int cur = 0;
	int max = Integer.MIN_VALUE;
	for(int i = 0; i<list.size(); i++){
		if(list.get(i) > max){
			max = list.get(i);
		}
		cur = max(0, cur + list.get(i));
		if(cur > ret){
			ret = cur;
		}
	}
	if(max < 0){
		return max;
	}
	return ret;
}

- ShiguangWang December 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaxSumSubArray {

static int maxSumSubArr(ArrayList<Integer> list) {
int ret = 0;
int cur = 0;
int max = Integer.MIN_VALUE;

for (int i = 0; i < list.size(); i++) {
if (list.get(i) > max) {
max = list.get(i);
}
cur = max(0, cur + list.get(i));
ret = max(cur, ret);
}
return ret;
}

private static int max(int i, int j) {
return (i < j ? j : i);

}

public static void main(String[] args) {
ArrayList<Integer> num = new ArrayList<Integer>();
num.add(-3);
num.add(-4);
num.add(5);
num.add(6);
num.add(-1);
num.add(-2);
num.add(-9);
num.add(-2);

int result = maxSumSubArr(num);
System.out.println("The result is::" + result);
}

}

- Anonymous December 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int GetMaxSumOfSubArray(int *n, int len)
{
    int tempMax = 0;
    int maxSum = -2147483648;
    int theLeft = 0;
    int theRight = 0;
    int tempLeft = 0;

    for (int i=0; i<len; i++)
    {
        tempMax += n[i];
        if (tempMax > maxSum)
        {
            maxSum = tempMax;
            theLeft = tempLeft;
            theRight = i;
        }

        if (tempMax < 0)
        {
            tempLeft = i+1;
            tempMax = 0;
        }
    }

    for (int i=theLeft; i<=theRight; i++)
    {
        printf("%d ", n[i]);
    }
    printf("\n");

    return maxSum;
}

int n[] = {2, 3, -1, -2, 5};
printf("%d\n", GetMaxSumOfSubArray(n, sizeof(n) / sizeof(int)));

2 3 -1 -2 5
7

- readma December 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class MaxSumSubArray
{
    static void Main()
    {
        int[] a = new int[] { -1,-2,-3 };
        int sum = Int32.MinValue;
        int max = 0;

        for (int i = 0; i < a.Length; i++)
        {
            if (max <= 0)
                max = a[i];
            else
                max += a[i];
            if (max > sum)
            {
                sum = max;
            }
        }

        Console.WriteLine(sum);
    }
}

- Anonymous December 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think I have an O(n) solution, but which is O(n) in space too.
The code would probably be messy so I'll just propose a sketch for the algorithm.
also, the sketch is concerned with finding the maximum sum itself,
but it can (somewhat) easily be modified to return start and end indices,
though, again, it will get even messier.

X :
Takes an array, A, of size n, and generates an array, B, of size m <= n, 
s.t the entries of B are the sums of the equi-signed-sequences of A.
e.g : A = (5, 6, -2, -1, -12, 7)  =>  B = (11, -15, 7)

then sends (B, m) to Y to retrive the maximum value and returns it.

Y : 
Takes an array, B, of size m, *with interchanging signs*, 
and generates an array, C, of size k <= 2m/3, 
s.t the entries of C are the sums of the triplets of B, 
centered in a negative value (boundry negatives are ignored), 
and the negated possitive values between them 
(for not counting them twice later).
e.g : B = (-17,2,-5,8,-7,1,-9, 2, -12) => C = (5,-8,2,-1,-6)

runs over B to find maximum value, and remembers it, 
then returns reccursively to X with C and k, to get the maximum from there,
compares it to the maximum it remembered, and returns the greater of them.

The complexity, both in space and time, is defined by the reccursive relation :
T(n) = T(2n/3) + O(n)
which yields an O(n) total.

The correctness is based on the following observations :

1. If we can take a positive value to the sum, we'll take it.
2. We'll never take a negative value,
unless it leads the way to a possitive value that compensate for it.
3. The algorithm checks all sums of sub arrays
that start and end with a positive value,
and are wrapped with negative values, or original array boundries,
thus returns the right value.

I'll be happy to hear opinions about it, as I just thought of it, so I might be missing out on something..
Also improvements will be welcomed.

- Elad December 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is an example of dynamic programming:

Here is the code for this

import java.util.Scanner;


public class FindMaxSubSeq
{
	int arraySize;
	int arr[];
	int sarr[];
	
	public FindMaxSubSeq()
	{
		Scanner s = new Scanner(System.in);
		System.out.println("Enter array size : ");
		arraySize = s.nextInt();
		System.out.println("Enter the elements : ");
		int i=0;
		sarr = new int[arraySize];
		arr = new int[arraySize];
		while(i<arraySize)
		{
			arr[i] = s.nextInt();
			i++;
		}
	}
	
	public void findTheSequence()
	{
		int i=0;
		while(i < arraySize)
		{
			if(i==0)
			{
				sarr[0] = arr[0];
			}
			else
			{
				sarr[i] = Math.max(arr[i], sarr[i-1] + arr[i]);
			}
			i++;
		}
		
		//Now evaluate the max we just found
		int k=0; int max = sarr[k];int max_index = 0;
		while(k<arraySize)
		{
			if(sarr[k] > max)
			{
				max = sarr[k];
				max_index = k;
			}
			k++;
		}
		
		
		//we found the max, just traverse backwards
		int z = max_index;
		int start = max_index;
		int end = max_index;
		int sumTillNow = 0;
		while (z >= 0)
		{
			sumTillNow = sumTillNow + arr[z];
			if(sumTillNow == max)
			{
				System.out.println(" The start index : " +end+ " The end index : " +start+ " The sum is : " + max);
				return;
			}
			z--;
			end--;
		}
	}
	
	public static void main(String args[])
	{
		FindMaxSubSeq s = new FindMaxSubSeq();
		s.findTheSequence();
	}
}

- devball December 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

CONSOLE OUTPUT:
==================

Enter array size :
20
Enter the elements :
2
-3
1
-2
3
-1
2
-3
1
-2
3
-1
2
-1
3
-2
1
-2
2
-1
The start index : 10 The end index : 14 The sum is : 6

- devball December 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaxSumArray {

    public static void main(String[] args){

        int[] array=new int[]{2,30,15,-7,9,14,-10,23,14,0};
        int[][] sum=new int[array.length][array.length];

        int i=0;
        int j=1;

        int max=0;
        int start=0,end=0;

        sum[0][0]=array[0];

         while(i<array.length && j<array.length) {

            if(sum[i][j-1] + array[j] >=sum[i][j-1])
            {
                sum[i][j]=sum[i][j-1]+array[j];


            }

            else
            {

               i=j+1;
            }

            if(max<sum[i][j])
            max=sum[i][j];

             j++;
        }


         System.out.println(max);
    }
}

- geekgirl December 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Better version of the above with complexity O(n)

public class MaxSum {
      public static void main(String[] args){

     int[] array=new int[]{2,3,-5,7,0,9,11,-10};

          int[] sum=new int[array.length];
          int max=0;
          sum[0]=array[0];

          for(int i=1;i<array.length;i++){

           if(sum[i-1]+array[i]>=sum[i-1])  {

               sum[i]=sum[i-1]+array[i];

           }

           else
            sum[i]=0;

         if(max<sum[i]){

             max=sum[i];
         }


          }

          System.out.print(max);

      }
}

- geekgirl December 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int maxSumSubArray(int a[], int size) {
int sum = 0, i = 0, max = 0;
for(i =0; i <size; i++){
sum = sum + a[i];
if(sum < 0) sum = 0;
if(sum > max) {
max = sum;
}
}
return max;
}

- __KB January 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Kadane algorithm itself

// test3.cpp : main project file.

#include "stdafx.h"

using namespace System;

#define SIZE 12

int main(array<System::String ^> ^args)
{
    int input[SIZE] = {-1,-2,+2,-4,-5,-6,-7,-1, -2, -3, -4, -5};

    int maxSum = -100000000;
    int maxStartIndex = 0;
    int maxEndIndex = 0;

    int currentMaxSum = 0;
    int currentStartIndex = 0;

    for (int currentEndIndex = 0; currentEndIndex < SIZE; currentEndIndex++)
    {
        currentMaxSum = currentMaxSum + input[currentEndIndex];

        if (currentMaxSum > maxSum)
        {
            maxSum = currentMaxSum;
            maxStartIndex = currentStartIndex;
            maxEndIndex = currentEndIndex;
        }        

        if (currentMaxSum < 0)
        {
            currentMaxSum = 0;
            currentStartIndex = currentEndIndex + 1;
        }
    }

    Console::WriteLine("maxSum: {0}", maxSum);
    Console::WriteLine("maxStartIndex: {0}", maxStartIndex);
    Console::WriteLine("maxEndIndex: {0}", maxEndIndex);

    return 0;
}

- J99 April 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The initial maxSum here should be like 0xFFFF...FFFF in theory according to the type definition.

- J99 April 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in k and q lang
f:{msf::meh::0;last{meh::meh+x;$[meh<0;meh::0;msf<meh;msf::meh;::];msf}'[x]};
/- Test - f[-2, -3, 4, -1, -2, 1, 5, -3] - output 7

- Anonymous December 22, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

why microsoft*

- msft needs to improve hiring methods November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is not about memorize, It is about understand the root of the problem. If you want to only memorized the solution, then good luck in your future work.

- .·´¯`·.´¯`·.¸¸.·´¯`·.¸><(((º> November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You came up with linear solution by yourself first time you saw this question? No.

- msft needs to improve hiring methods November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@msft...

Why not? Don't underestimate people, even if they are visitors of this site (;-))

I remember coming up with a linear time algorithm for this, based on cumulative sums.

- Loler November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The linear time, o(1) space algorithm took years to figure out. Look at history of kadane's algorithm.

msft has history of asking this kadane's problem and expecting that very same algorithm (search in careercup search)

- msft needs to improve hiring methods November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@msft...

There is no requirement of O(1) space in the question. What makes you think msft is expecting that algorithm?

- Loler (unregistered) November 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Loler

Because of the people who prepare know Kadane's and the person asking probably knows it, so the bar is raised. If you do the cumulative sum caching method it will get a less than perfect score even if you have no bugs.

- msft needs to improve hiring methods November 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@msft.

The cumulative summation method can be made O(1) space too.

But you are right. This is a bad question to ask in the interview as genuinely good candidates who haven't seen this before can perform worse on this than bad candidates who have seen this before. They better have other good questions to counteract this bad question.

Perhaps this question is to weed out the dishonest candidates, who breeze through this but perform average/below average on other questions.

- Loler (unregistered) November 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@loler

I know google (used to) has(have) a category for "speed" and often the interviewers give a high score for people who breeze through questions.

That's why the more mediocre people they hire get the best scores: gawker.com/5392947/googles-broken-hiring-process

- msft needs to improve December 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@msft.

Your read of the article "the more mediocre people get better scores" is completely off: that article and you have completely misunderstood Peter Norvig's comments about the hiring process. Look at the link in update2 which talks about "everything wrong".

As to earlier comments. Yes, speed matters. If you struggle and take 30 minutes to solve a problem while every other candidate finishes, with code, in 15, you will be in a bad position.

That is why Google strives not to ask questions which are well known as they are good indicators of the problem solving ability. I have even heard that the feedback on such questions might even get thrown out and the interviewer asked to pick better questions next time.

Also, the interview consists of multiple questions (and interviewers) with lot of discussion/designing systems/writing code etc.

It is unlikely that a mediocre candidate would have seen all the questions (especially with Google trying to keep them "fresh"). Even with well known questions, a good interviewer can ask subtle variations etc as a followup to really judge the candidate.

It is very very unlikely that a mediocre candidate will be able to fool every interviewer and the hiring committee. It is not impossible, though and I expect they will get fired soon if they manage to slip through the cracks.

Some amount of good candidates might be rejected, though. But that is expected.

Having a good hiring process is a hard problem.

- Loler (unregistered) December 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

norvig quoted:

One of the interesting things we've found, when trying to predict how well somebody we've hired is going to perform when we evaluate them a year or two later, is one of the best indicators of success within the company was getting the worst possible score on one of your interviews. We rank people from one to four, and if you got a one on one of your interviews, that was a really good indicator of success.

- msft needs to improve December 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@msft.

Well if you are quoting, here is a quote from link in the update2 (which I presume you never bothered to read) which has further clarifying comments (from Peter Norvig) to the article you linked.

What do you know? Valleywag got everything wrong. 
  
Google is hiring, not laying off. 
  
Also, our interview scores actually correlate very well with on-the-job performance. Peter Seibel asked me if there was anything counterintuitive about the process and I said that people who got one low score but were hired anyway did well on-the-job. 
  
To me, that means the interview process is doing very well, not that it is broken. 
  
It means that we don't let one bad interview blackball a candidate. We'll keep interviewing, keep hiring, and keep analyzing the results to improve the process.
  
And I guess Valleywag will keep doing what they do... 
   
    - Peter Norvig from Bookmarklet

- Loler (unregistered) December 01, 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