## Interview Question

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

1. Sort the array -- nlogn
2. take two index one at start and one at end.
3. let element1 and element2 are the two elements whose sum is closest to zero.
4. element1 = start
5. element2 = end

``````while(start<=end)
{
if(abs(a[start] + element2) <= abs(element1 + element2))
{
element1 = a[start];
start++;
continue;
}
if(abs(a[end] + element1) <= abs(element2 + element1))
{
element2 = a[end];
end--;
continue;
}

if(abs(a[start] + element2) > abs(element1 + element2) && abs(a[end] + element1) > abs(element2 + element1))
{
start++;
end--;
}
}``````

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

I think after while block add
if(abs(a[start]+a[end])<abs(element1+element2)){
element1=a[start];
element2=a[end];
}
check for array {-100,-2,1,97}

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

Find 2 values closest to zero - O(n) - 2 passes

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

won't work for
100 1 -2 -100

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

``````//dynamic programming. O(n^2)
void f(int[] s)
{
if(s==null || s.len<2) return;

int min=MAX;//min is the min distance to 0. which is non-negative.
int minA, minB; // the indexes of elements in s whose sum is closest to 0.
for(i=1;i<s.len;++i)
{
lmin=MAX;
for(j=0;j<i;++j)
{
lmin=min(lmin,|s[i]+s[j]|);
if(lmin==0)
{
print(lmin,i,j);
return;
}
}

if(min>lmin)
{
min=lmin;
minA=i;
minB=j;
}
}

print(min, minA, minB);
}``````

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

I got on solution n(logn):
1. use 0 minus each element in the array, put result in a new array --- n
2. binary search each element in new array within old array, record distance. --- nlogn
3. pick the one with smallest distance --- n

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

The Simple Solution is ..,
1. Sort the array O(nlogn) .
2. Find the index of first positive and first negative number . O(n).
3. Start subtracting positive number from negative numbers until you find a value which is close to zero.

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

You mean add the positive and the negative number to see if their sum is closest to zero.

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

Hash all the values and then find if sum-number is available in the hash. Now if number = sum/2, you need to handle it separately.

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

O(n) Solution.

currentbestpair[2] = [a[0],a[1]];
currentbestpairval = abs((a[0]+a[1]-0)
for(i=2;i<n-1;i++) {
currentval = abs(currentbestpair[0]+a[i])-0);
if(currentval < currentbestval) {
currentbestpair[1] = a[i];
currentbestpairval = currentval;
}
currentval = abs(currentbestpair[1]+a[i])-0);
if(currentval < currentbestval) {
currentbestpair[0] = a[i];
currentbestpairval = currentval;
}
}

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

I got a solution in O(n). The logic is to find the max_negetive number and min_positive number. Please let me know if they are correct.

``````#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.
1
of 1 vote

I keep get the feeling that everybody here is mistakingly thinking that the answer must consist of one positive number and another negative number.
Look at {-100, -30, 1, 2, 7} for instance. The answer should be 1 and 2 since 3 is the closest sum the zero.

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

Very nice point!

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

1.sort the array
2.find min element
3.compare the sun of min+left and min+right to find the ans

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

i mean find min element in term of distance from 0

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

Given an array A of n integers, give an ecient algorithm to check whether there are
two numbers in A whose sum is zero.

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.