Microsoft Interview Question
Country: United States
Interview Type: In-Person
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.
@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.
@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.
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) ;
}
@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
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.
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)
@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.
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)
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;
}
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).
@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 :)
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.
@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?
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.
@ 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.
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.
/*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;
}
// 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);
}
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???
#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();
}
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..
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();
}
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;
}
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]
- algos September 06, 2012ex: 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)