## xyz Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

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

If you are allowed extra buffer, this solution might work.
It is using the fact that the pair add up to zero only if the two integers are opposite

``````public static void oppositePairs(int[] input){
Set<Integer> map = new HashSet<>();
for(int a: input){
if(!map.contains(a)){
}
if(map.remove(-a)){
System.out.println(a + " " +(-a));
map.remove(a);//will fail if the pair (a, -a) appear more than once
//(eg. if input is {1,2,-1,-2,-1,1}, will return the pair twice
}
}
}``````

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

If you are allowed extra buffer, this solution might work.
It is using the fact that the pair add up to zero only if the two integers are opposite

``````public static void oppositePairs(int[] input){
Set<Integer> map = new HashSet<>();
for(int a: input){
if(!map.contains(a)){
}
if(map.remove(-a)){
System.out.println(a + " " +(-a));
map.remove(a);//will fail if the pair (a, -a) appear more than once
//(eg. if input is {1,2,-1,-2,-1,1}, will return the pair twice
}
}
}``````

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

1. O(n2) comparison
2. O(n) Hashing with key value and -value

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

Two approaches:
1. Sorting the array (costs O(n log n)), iterating elements and for each element look for its negative value with binary search (again, O(n log n)). Overall time is n log n.
2. Iterate elements. For each element, add to a hash table, and search for its negative value in the hash table.

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

make a hashMap: Z+ -> {-1,0,+1}
0 if not exists
+1 if +ve value exists
-1 if -ve value exists

``````for each elt in array
if map[|elt|]
return (map[|elt|]*|elt| + elt ==0)
if elt<0
map[|elt|]=-1
else
map[|elt|]=+1``````

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

That's too less for an explanation

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

here's a simple solution in O(n*log(n))

``````sort()
i = 0;
j = ArraySize - 1
while ( i<j)
{
if ( -A[i] > A[j] )  i++
else if ( -A[i] < A[j] )  j++
else You have found a pair, i++, j++

}``````

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

This is like finding duplicates in an array. Just slight change to the logic for duplicates.

Maintain one Hashmap. Keep inserting into the Hashmap element,null. If -(element) comes up, replace null with that value.

Once the array walk is complete, find all the elements in the Hashmap with value!=null

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

My O(n) solution in Scala:

``````object ZeroSumArray {
def findZeroSumPairs(arr: Array[Int]): List[(Int, Int)] = {
val v = arr.toList.groupBy(x => x)
def go(s: List[Int]): List[(Int, Int)] = {
s match {
case Nil => Nil
case (h::t) if h < 0 => go(t)
case (h::t) if h > 0 =>
val pairs = v.getOrElse(-h, Nil).map(_ => (h, -h))
pairs ++ go(t)
}
}

go(arr.toList)
}

def main(args: Array[String]): Unit = {
val arr1 = Array(1, 4, 5, 7, 8, -1, -1, 1, -6, -8, -3)
println(findZeroSumPairs(arr1))
}
}``````

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

By the way, my solution allows duplicate pairs.
E.g. if 3 values of x are in the array and also 3 values of -x, you'll get 9 pairs.

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

Here is one that has tail recursion (optimization that avoids stack overflows):

``````object ZeroSumArray {
def findZeroSumPairs(arr: Array[Int]): List[(Int, Int)] = {
val v = arr.toList.groupBy(x => x)

@tailrec
def go(in: List[Int], result: List[(Int, Int)]): List[(Int, Int)] = {
in match {
case Nil => result
case (h::t) if h < 0 => go(t, result)
case (h::t) if h > 0 =>
val pairs = v.getOrElse(-h, Nil).map(_ => (h, -h))
go(t, pairs ++ result)
}
}

go(arr.toList, Nil)
}

def main(args: Array[String]): Unit = {
val arr1 = Array(1, 4, 5, 7, 8, -1, -1, 1, -6, -8, -3)
println(findZeroSumPairs(arr1))
}
}``````

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

``````li = [3,4,1,-2,-4,5,2]
di = {}
for x in li:
if(di.get(x*-1)):
print x, -x
else:
di[x] = True``````

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

``````a=[1,-1,2,3,4,5,-5,6,-6,-3,4,5,67,76,-67]
a_dict={}
b=[]

for i in a:
if i in a_dict:
continue
elif i not in a_dict:
if (i*-1) not in a_dict:
a_dict[i]=5
else:
a_dict[i*-1]=i
j=1
for i in a_dict:
if a_dict[i]==5:
continue
else:
print "Pair number %d is: %d <---> %d"%(j,i,a_dict[i])
j +=1``````

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

``````// ZoomBA : non optimal Theta(n^2)
arr = [ -1, 0 , 1, 0 , 2, - 2 , 3 , 10 ]
r = [0:#|arr|]
pairs = join( r, r ) :: {
continue ( \$.o.0 >= \$.o.1 )
arr[\$.o.0] + arr[\$.o.1] == 0
} -> { [ arr[\$.o.0] , arr[\$.o.1] ] }
println( pairs )
// ZoomBA : optimal Theta(n) with Theta(n) space
#(s,l) = lfold( arr , [ set() , list() ] ) ->{
s = \$.p.0 ; l = \$.p.1
if ( -\$.o @ s ){ l.add ( [ \$.o, -\$.o ] ) ; continue }
s += \$.o
\$.p = [ s, l ]
}
println(l)``````

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

Sort both array one in asending one indesending = 2*nlogn
for all items if(pve[i]+nve[i]==0)count++

TimeComplexity = 2 * nlogn + n =O(nlogn)

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

There is only one array.

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

``````func printPair(arr []int) {

mymap := make(map[int]int)

for _, e := range arr {
var key int
if e > 0 {
key = e
} else {
key = -e
}
val, ok := mymap[key]
if ok == false {
mymap[key] = e
} else if ok == true {
if (val +  e) == 0 {
fmt.Printf("[%d, %d]\n", val, e)
}
}

}
}``````

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

``````sort (A, n);

for (i=0, j = n; i<n, j >-1;)
{
temp = A[i] + A[j];
if (temp < 0)
{
i++;

}
else if (temp == 0)
{
cout << "Pair: " << A[i] << " " << A[j] << endl;
i++; j--;
} else
{
j--;
}
}``````

I guess this should solve it.
Complexity: O(nlogn) + O(n)

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

python
O(n)

``````def sum_0(l):
new = []
dn = dict()
dp = dict()
for i in l:
if i >= 0:
z = dp.get(i, 0)
z += 1
dp[i] = z
else:
z = dn.get(i, 0)
z += 1
dn[i] = z

for j in dp:
if (-j) in dn:
new.append((j, -j))

return new

z = sum_0([1, -1, 3, 2])
print(z)``````

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

Python:

``````def compareSum(compArr):
listDic={}
listNegDic={}

for i in range(len(compArr)):
for j in range(len(compArr)):
if i == j:
continue
if(compArr[i]+compArr[j]==0):
if listDic.get(i) is None or listNegDic.get(i) is None:
if compArr[i]>0:
listDic[compArr[i]]= compArr[j]
if compArr[i]<0:
listNegDic[compArr[i]]=compArr[j]

return listDic

probArr = [2,1,-1,4,5,-2,-5,-4,7,8,-8]
print compareSum(probArr)``````

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

#include<stdio.h>
int main(){
int i,n,j,temp;
scanf("%d",&n);
int arr[n];
for(i=0;i<n;i++)
scanf("%d",&arr[i]);

for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
temp=arr[i]+arr[j];

if(temp==0){
printf("%d %d\n",arr[i],arr[j]);
}
}

}

return 0;

}

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

``````public static void main(String[] args) {
int[] A = { 2, 3,  4,1 };
int sumNum = 0;
Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();
for (int i : A) {
pairs.put(i, sumNum-i);

}
int count = 0;
for(int key:pairs.keySet()){
if(pairs.containsKey(sumNum-key)){
count++;
}
}
System.out.println(count/2);

}``````

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.