xyz Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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)){
map.add(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
}
}
}
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.
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
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
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))
}
}
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.
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))
}
}
// 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)
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)
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)
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);
}
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
- Anonymous October 30, 2015