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)){
				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
			}
		}
	}

- Anonymous October 30, 2015 | Flag Reply
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)){
				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
			}
		}
	}

- castro October 30, 2015 | Flag Reply
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

- ankushbindlish November 01, 2015 | Flag Reply
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.

- JonathanBarOr November 01, 2015 | Flag Reply
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

- sumitgaur.iiita November 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's too less for an explanation

- Asif Garhi November 04, 2015 | Flag
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++

   }

- koosha.nejad November 03, 2015 | Flag Reply
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

- Anonymous November 08, 2015 | Flag Reply
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))
  }
}

- akmo75 November 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- akmo75 November 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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))
  }
}

- akmo75 November 15, 2015 | Flag
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

- Swastik November 22, 2015 | Flag Reply
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

- Soumil Kulkarni April 21, 2016 | Flag Reply
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)

- NoOne October 08, 2016 | Flag Reply
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)

- kundansdere October 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

There is only one array.

- vaibhavjha94 October 30, 2015 | Flag
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)
                        }
                }

        }
}

- cutail.capricorn October 31, 2015 | Flag Reply
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)

- Varun November 01, 2015 | Flag Reply
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)

- anish531213 November 02, 2015 | Flag Reply
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)

- saikat1239 November 02, 2015 | Flag Reply
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;

}

- Mukesh November 23, 2015 | Flag Reply
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);

	}

- mail.smritiraj May 07, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More