## Microsoft Interview Question

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
19
of 25 vote

take two arrays, sum array and index array of size n+1, fill the array with sum from 0 to i for all array elements, i.e sum[i] = sum of all elements from a[0] to a[i]
ex: 2 3 -4 9 1 7 -5 6 5
sum array : 0 2 5 1 10 11 18 13 19 24
index array: -1 0 1 2 3 4 5 6 7 8

now sort sum array in ascending order including index array.

sum array: 0 1 2 5 10 11 13 18 19 24
index array: -1 2 0 1 3 4 6 5 7 8

now find the absolute difference between any 2 elements is minimum from the above sum array. here from sum array (0,1), (1, 2), (10,11) and (18,19) absolute difference is minimum that is 1.

lets take case 1, 2
here the index is 0 and 2 so we need to take sum from index 1 to 2 in original array that is 3 to -4

lets take case 10, 11
here the index is 3 and 4 so we need to take sum from index 4 to 4 in original array that is 1 to 1

lets take case 18, 19
here the index is 5 and 7 so we need to take sum from index 6 to 7 in original array that is -5 to 6

time complexity O(n log n) that is for sorting and space complexity is O(n)

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

There's a small corner case here. You're not considering subarrays that start from the beginning of the array. The easiest way to consider this case is to make the sum array one value bigger than the input array and to always start by placing a 0 in the sum array.

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

bug is fixed. thanks for the finding.

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

How do you deal with overflows?

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

subarray means contiguous elements.

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

@Anonymous: The algorithm is stated mathematically, so it's just a matter of representing the data the algorithm calls for and there's no error in the algorithm as such. That's something to be careful about when implementing the solution, though!

If the input is ints we can probably do longs in the sum array; if the input is longs we will probably need something like BigInteger or some special type of our own making.

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

@algos take this corner case : all are negative you always increase the start index. How do you handle this.

-5 -3 -1 -8 -9 -3
so after sorting your elements will be like this
(5,-29)
(4,-26)
(3,-17)
(2,-9)
(1,-8)
(0,-5)
(-1,0)

so your start index will be 2 and end index will be 1.
So final answer becomes 2+1 = 3 to 1 which is odd.
So first you have to check which end is minimum and update the min index by +1.

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

just codes what algos said. Some modi as mentioned above.

``````#include <cstdio>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std ;

typedef struct element {
int index ;
int val ;
bool operator < (const element& ele) const {
return (val < ele.val);
}
}element ;

void findSubArraySumCloseToZero (vector<element> vec) {
sort (vec.begin(), vec.end()) ;
vector<element>::iterator it = vec.begin() ;
element prev = *it , cur, start = *it, end = *it;
int max = INT_MAX, sindex, eindex ;
for ( it ++ ; it < vec.end(); it ++ ) {
cur = *it ;
if ( (cur.val - prev.val) <= max ) {
max = cur.val - prev.val ;
start = prev ;
end = cur ;
}
prev = cur ;
}
sindex = (start.index > end.index) ? (end.index) : (start.index) ;
eindex = (start.index <= end.index) ? (end.index) : (start.index) ;
sindex ++ ;

printf ( "\nStart index = %d, end index = %d", sindex, eindex ) ;
}

int main () {
vector<element> vec ;
int num, size ;
scanf ( "%d", &size ) ;

element ele ;
ele.index = -1 ;
ele.val = 0 ;
vec.push_back (ele) ;

for ( int i = 0 ; i < size ; i ++ ) {
scanf ( "%d", &num ) ;
element ele, prev = vec.back();
ele.index = i ;
ele.val = num + prev.val ;
vec.push_back (ele) ;
}
findSubArraySumCloseToZero (vec) ;
}``````

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

@Psycho: print the elements from start+1 to end. here start = 1 and end = 2... so it prints from 2 to 2 that is -1.
start is min number and end is max number

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

Here we have considered only 2 elements. How would you deal with the case where the sub-array can have more than 2 elements and still the sum is close to 0.

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

it is not just considered 2 elements. absolute difference between 2 elements is minimum and the index of these 2 elements is lets 2 and 7 then the sub array sum close to zero is array index from 3-7 (5 elements)

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

@eugene: For correctness it might not matter (BigInt would do). For runtime, it does. You running time might no longer be O(n log n). Space usage also goes up.

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

This solution could not handle this case:
2, 3, -4, -1, 6

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

``````2 3 -4 -1 6
sum array:   0 2 5 1 0 6
index arra: -1 0 1 2 3 4
now sort the sum array including index array

0 0 1 2 5 6	(sum array)
-1 3 2 0 1 4 	(index array)

now check the absolute difference between any 2 elements is minimum in sum array...here difference between 0 & 0 is minimum that is 0
so the solution is starting from index -1+1 to 3 that is index 0 to 3 ( 2 + 3 + -4 + -1 = 0)``````

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

nice solution

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

here is O(n) solution. challenge accepted :)

``````/*
* File:   main.cpp
* Author: vsirohi
*
* Created on September 8, 2012, 9:21 PM
*/

#include <cstdlib>
#include<iostream>
using namespace std;
int mod(int a) // returns a positive integer
{
if(a<0)
a*=(-1);
return a;
}
int absmin(int a , int b) // returns the integer with  absmin magnitude of two
{                       // this do not consider sign (-ve or +ve
int aa=a, bb=b;
if(a<0)
aa = mod(a);

if(b<0)
bb= mod(b);
if(aa<bb)
{ return a; }
else
return b;
}
int min(int a, int b)
{
if(a<b)
return a;
return b;
}
int  greatestsumarraysum(int array[], int length)
{
int  minsum = 4444, sumsofar = 4444, absminsum=4444, absminsumsofar=4444, tempmin = 4444;
int start =0, end=0;
for(int i=0; i<length; i++)   // O[(n)
{
absminsum = absmin(array[i], array[i]+absminsum);
minsum = min(array[i], minsum+array[i]);

tempmin = absmin(minsum, absminsum);
tempmin = absmin(tempmin, sumsofar);

absminsumsofar = absmin(tempmin,absminsumsofar);
sumsofar = min(sumsofar, minsum);
}

return absminsumsofar;
}

int main(int argc, char** argv) {
int arr[3] = {-12, 2, 11}; //*/{-5, -3, -2 };//8, 15, -5, 3};
// some random test cases.
// int arr[7] = {5, 3, -12, 8, 15, -5, 3};
//int arr[2] = {5, 3};//, 2};//,8,15,-5,3};
// int arr[7] = {1, -1, -2, -1, 2, -1,2};
//int arr[7] = {-1, -2, -3, -1, -2, -2, -1};
//  int arr[7] = {0,-1,-2,5, 6,3,1};
// int arr[5] = {4,5,6, 3,1};
//  int arr[3] = {3, -5, 6};
// int arr[7] = {5, 3, -12, 8, 15, -5, 7};
int sum=0;
sum = greatestsumarraysum(arr, 3);
cout << " the sum is  : "<<sum<<endl;
return 0;
}``````

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

I took 4444 as the initial value for variables : sumsofar and maxsum.
it works in this case.
but actual thought was to take +INFINITY (MAX range on Int/double etc).
as you wish.
*maxsum = minsum(sorry for confusing var name).

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

@algos :
for i/p : int arr[3] = {-12, 2, 11};
O/p : the min sum array is :
2 the sum is : 2

RUN SUCCESSFUL (total time: 12ms)

for I/P : int arr[3] = {3, -5, 6};
int sum=0;
sum = greatestsumarraysum(arr, 3);
cout << " the sum is : "<<sum<<endl;
O/P : the min sum array is :
3 -5 the sum is : -2

RUN SUCCESSFUL (total time: 15ms)

for I/P : int arr[7] = {5, 3, -12, 8, 15, -5, 3};
int sum=0;
sum = greatestsumarraysum(arr, 3);
cout << " the sum is : "<<sum<<endl;

O/P : the min sum array is :
3 the sum is : 3

RUN SUCCESSFUL (total time: 11ms)

sorry; But you have to manually change the length of array while calling the fun "greatestsumarraysum" ;
Thanks for pointing.
Please up vote :)

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

Bullshit solution.

How can I make such a claim?

Because researchers have already proven that we cannot do better than nlogn. Lookup element distinctness problem. There is a trivial reduction from that to this.

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

@Eugene. See the comment about "certain models of computation" to rockstar's answer.

The solution posted in this answer fits the model with known lower bounds for the distinctness problem (I believe it is called the algebraic decision tree model).

So, even though we know there are trivially obvious average case O(n) solutions to distinctness problem, they are not really applicable to this answer.

So, what is your point?

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

Actually, the burden of proof is on the guy claiming O(n). Why don't you ask him to prove it first!

Frankly, people post crap without putting in too much thought. I don't see why I should be expected to post a full rebuttal.

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

@Eugene: No, I am not aware of one.

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

@ all Anonymous and others.

this can be easily done by using the technique called dynamic programming (given that you know about it).
In which we solve smaller problems memorize the result (called memoization ). then combine those solution to get the solution for actual problem. This is applicable for the overlapping problem.

Might be this solution needs some correction to cover all the edge cases.but it works fine in most of the cases.
the idea in itself is good.
@who wrote bullshit soln.
you can't digest new things which you don't know about unless you r willing to learn something new.
if you have; write a better solution than this. it is giving you result in O(n) time.
here is how :
I started with a larger minimum sum (basically infinity ,but 4444 in this case).
compare this with the 1st elem of array. if elem is less that this is new minimum absolute sum.
now, while considering every next element of the array , we have to decide which is the absolute minsum out of abs min sumsofar, current elem, current elem+abs min sum so far.
this can be easily done by memoizing the results of last iteration. if we find new min elem then we start our new abs min sum subarray from this point or if current elem contributes to new abs min sum then we include this in new min sum sub array. or else keep on searching for new abs min.
thus at the end we have the abs min sum for the original array.
in this case we made one decision at every elem of array. and loop runs only once.
this give you O(n) + some const time soln.
your feed backs for any improvement are always welcome.

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

*subarray is assumed to be contiguous.

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

@algos
thanks for ur feedback buddy.
the bug is fixed :) .
check now.

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

Consider a test input like 6 1 -7. Here the optimal choice is to take the whole array, at which point you get 0. You will instead first consider 6, then consider a choice of 6 1, 6, and 1 (and you'll pick 1), and then you'll consider a choice of 1, -7, and 1-7 (and you'll pick 1).So you'll end up picking just the subarray that includes the single number 1, which is the wrong answer.

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

hmmm.. :(
My attempt to optimize it was not that bad.
thanks anyway.
let me see if i can do something to keep the algo optimized and solve the prob.
fell free to use ur traditional approach ;).

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

``````/*Assuming subarray should be continuous*/

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include <stdio.h>

using namespace std;

main()
{
int n,i,cstart=0,pstart=0,end=0,temp;
cout<<"enter size\n";
cin>>n;
int *a = new int[n];
cout<<"enter array\n";
for(i=0;i<n;i++) cin>>a[i];
int sum=0,diff=999;
for(i=0;i<n;i++){
if((sum <= 0) && (a[i]>=0)){
sum = a[i];
cstart = i;
}
else sum+=a[i];
if(sum == 0) {
end =i;
pstart = cstart;
break;
}
temp = sum;
if(temp < 0) temp *= -1;
if(temp<diff)  {
diff = temp;
end =i;
pstart = cstart;
}

}
for(i=pstart;i<=end;i++) cout<<a[i]<<" ";
cout<<endl;
}``````

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

Counter example.
Array:
[3] [-1] [5] [-4] [3]
The algo outputs elements from 0(pstart) to 1(end). Sum = 2;
Should be (from 2 to 3. Sum = 5-4 = 1) or (from 3 to 4. Sum = -4 + 3 = -1)

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

// Time Complexity O(nLogn)

``````static class Node {

int sum;
int index;

public Node(int sum, int index) {
this.sum = sum;
this.index = index;
}

public int getSum() {
return sum;
}

public void setSum(int sum) {
this.sum = sum;
}

public int getIndex() {
return index;
}

public void setIndex(int index) {
this.index = index;
}
}

static class PrefixSumcomparator implements Comparator<Node> {

@Override
public int compare(Node o1, Node o2) {
return (o1.getSum() <= o2.getSum()) ? -1 : 1;
}

}

static void printPairWithMinimumsum(int[] input) {

int size = input.length;
Node[] prefixSum = new Node[size];

for (int index = 0; index < size; index++) {

int sum = input[index];
if (index > 0) {
sum += prefixSum[index - 1].getSum();
}

Node node = new Node(sum, index);
prefixSum[index] = node;

}

Arrays.sort(prefixSum, new PrefixSumcomparator());

int globalSum = Math.abs(prefixSum[0].getSum()), start = 0, end = prefixSum[0].getIndex();
for(int index=1; index < size; index++) {
int minSum = (prefixSum[index].getSum() - prefixSum[index-1].getSum());
if(Math.abs(prefixSum[index].getSum()) < globalSum) {
globalSum = Math.abs(prefixSum[index].getSum());
start = 0;
end = index;
} else if (minSum < globalSum) {
globalSum = minSum;
if (prefixSum[index - 1].getIndex() < prefixSum[index].getIndex()) {
end = prefixSum[index].getIndex();
start = prefixSum[index - 1].getIndex();
} else {
start = prefixSum[index].getIndex();
end = prefixSum[index - 1].getIndex();
}
}
}

System.out.println("start "+start+" end "+end+" sum "+globalSum);
}``````

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

are the elements need to be continuous?

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

see wikipedia's "maximum subarray problem"

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

@Anonymous: see wikipedia's entry for "Reading comprehension".

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

this can be done in O(n) time,just as we find largest subarray sum,by altering the conditions,we can find subarray with sum closest to ZERO.. was O(n) asked???

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

Think again.

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

If you have a specific O(n) algorithm in mind, the best thing to do is post it.

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

Yeah rockstar. I challenge you.

--

Ninjas are cool. Rockstars are annoying.

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

O(n) is impossible (at least in some models of computation).

Delusional.

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

#include<stdio.h>
#include<math.h>
#include<conio.h>
int main()
{
int arr[10]={-1,2,-3,4,0,5,-6,7,-10,11};
int i=0,n=10,sumtillnow=arr[0],sum=arr[0],start=0,end=0;
while(i<n)
{
sum=sum+arr[i];
if(abs(arr[i]-0) < abs(sumtillnow))
{
start=i;end=i;
}
if(abs(sumtillnow - 0) >= abs(sum - 0))
{
sumtillnow=sum;
end=i;
}
i++;
}
printf("the range is %d to %d",start,end);
getch();
}

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

challenge accepted @ Code Ninja...
@eugene.yaravoi u might have undrstood the idea,if ny flaws,please let me know,bt O(n) is possible dude..
@anonymous.. nothing delusional have a luk at the code..might be some test cases nt fulfilled.. i will design new1 for those,if u can make ny..

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

I have to say I was entertained by all those abs(whatever - 0) statements... I guess they either increase readability or optimize performance. Having said that, I did doubt for a while whether (anything - 0) is always equal to anything, which I think still holds.

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

her is O(n) code...
#include<stdio.h>
#include<math.h>
#include<conio.h>
int main()
{
int arr[10]={-1,2,-3,4,0,5,-6,7,-10,11};
int i=0,n=10,sumtillnow=arr[0],sum=arr[0],start=0,end=0;
while(i<n)
{
sum=sum+arr[i];
if(abs(arr[i]-0) < abs(sumtillnow))
{
start=i;end=i;
}
if(abs(sumtillnow - 0) >= abs(sum - 0))
{
sumtillnow=sum;
end=i;
}
i++;
}
printf("the range is %d to %d",start,end);
getch();
}

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

Your solution donot work for input 1,2,3,4,0,-4,-3,-2,-1 it simply returns 0 itself.

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

O(n) solution:

``````int ClosestZeroSubArray(int arr[], int len)
{
int sum, sumLeftIndex, sumRightindex;
int sumlast, lastLeftIndex, lastRightIndex;

sum = sumlast = arr[0];
sumLeftIndex = sumRightindex = lastLeftIndex = lastRightIndex = 0;

for (int i=1; i<len; i++)
{
if (abs(sumlast + arr[i]) < abs(arr[i]))
{
sumlast+= arr[i];
lastRightIndex = i;
}
else
{
sumlast = arr[i];
lastLeftIndex = lastRightIndex = i;
}

if (abs(sumlast) < abs(sum))
{
sum = sumlast;
sumLeftIndex = lastLeftIndex;
sumRightindex = lastRightIndex;
}
}

cout << "Subarray is between indexes " << sumLeftIndex << " and " << sumRightindex << " . Sum = " << sum;
return sum;
}``````

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

LOL!

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.