Microsoft Interview Question
Software Engineer InternsCountry: United States
Interview Type: Written Test
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;
}
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
Oh, you right. Thanks fot the note!
Mismatched the task. Solution is valid for sub-set of a set, but not for sub-array.
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)
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)
/**
* 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;
}
/**
* 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;
}
The code seems wrong to me. The answer to [2, -3, 1] should be 2 but I think the code will return 1?
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);
}
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.
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);
}
}
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
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.
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();
}
}
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);
}
}
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);
}
}
//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;
}
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.
@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.
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...
There is no requirement of O(1) space in the question. What makes you think msft is expecting that algorithm?
@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.
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
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.
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.
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.
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
Use Kadane algorithm.
- nascent November 29, 2013