## Interview Question

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

Great solution...
But I believe we need to do one more check...that if any of the partial sum themselves become zero, it means that the sub array starting from the beginning of the array till that point adds to zero, as we would not have any two partial sums to be the same in this case...
One more thing..was wondering how would the solution change of the array was to consist of zeros along with +ve and -ve integers??
Say 5 1 0 0 2 -3 6 1...then the partial sums would be 5, 6, 6, 6, 5...So does that mean we omit zeros while calculating partial sums or ignore if two consecutive partial sums are the same...Please correct me if i am wrong..

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

no dont omit them. Those are one of the subset whose sum is 0.

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

Hi, I did not understand the solution. Can you please elaborate with algorithm/ pseudo code

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

I assume the subarray is consecutive.
First compute all the partial sums. S_i = A[0] + A[1] + ... + A[i].
Finding the subarray with sum 0 is equivalent to finding two partial sums S_i and S_j that are the same, which can be solved by hashing in O(n) time or sorting O(n*logn) time.

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

nicely done

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

This is not entirely correct. Given a partial sum finding if it exists in the array take O(n) with hash and O(n*logn) with sort. However here you do not know what partial sum you are looking for.
You need something that exists for both the +ve and the -ve arrays... and there could be 2^n such partial sums that you would have to check for.

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

not able to understand , kindly elaborate

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

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

int main()
{
int a[6];
int i;
int zero_present = -1;

int min_positive;
int max_negetive;

for(i=0;i<6;i++)
{
scanf("%d",&a[i]);
}
min_positive = -1;
max_negetive = 0;

for(i=0;i<6;i++)
{
if(a[i] > 0)
{
if(min_positive == -1)
min_positive = a[i];
else if(a[i] < min_positive)
min_positive = a[i];
}

else if(a[i]==0)
zero_present = i;
else
{
if(max_negetive == 0)
max_negetive = a[i];
else if(a[i] > max_negetive)
max_negetive = a[i];
}
}
//Sum of min_positive and max_negetive will give the sum closest to zero
if(min_positive == -1 || max_negetive == 0)
{
if(zero_present)
{
if(min_positive == -1)
printf("%d\n",max_negetive); //closest sum to zero
else
printf("%d\n",min_positive);//closest sum
}
else
printf("Such sum not possible\n");
}
else
printf("%d\n",min_positive+max_negetive);

return 0;
}

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

``````package arrays;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class ZeroSumSubArray {

public static void main(String[] args) {
int a[] = { 3, 5, 6, -8, 1, -4, 9, 5, -9 };

// populate the sums
int sum = 0;
for (int i = 0; i < a.length; i++) {
sum += a[i];
a[i] = sum;
}

Map<Integer, ArrayList<Integer>> indices = new HashMap<>();

for (int i = 0; i < a.length; i++) {
indices.put(new Integer(a[i]), new ArrayList<Integer>());
}
for (int i = 0; i < a.length; i++) {
ArrayList<Integer> sumIndices = indices.get(new Integer(a[i]));
if (sumIndices.isEmpty()) {
} else {
}
}

for (Entry<Integer, ArrayList<Integer>> e : indices.entrySet()) {
ArrayList<Integer> list = e.getValue();
if (list.size() > 1) {
System.out.println("sub sequence with zero sum starts at " + list.get(0)+ " till "+ list.get(1));
}
}
}
}``````

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.