## Microsoft Interview Question

```
package results;
import java.util.HashMap;
import java.util.Iterator;
import java.util.*;
public class Main {
public int B[];
public int N;
Hashtable tbl;
int count;
Main() {
B = new int[N+1];
tbl = new Hashtable();
count=0;
}
public void threeSum(){
int A[] = {0, -25, -10, -7, -3, 2, 4, 8, 10};
int N =8;
for ( int i = 1; i <=N; i++){
for (int j =i; j <=N; j++){
tbl.put(A[i]+A[j],1);
}
}
Enumeration e= tbl.keys();
while ( e.hasMoreElements()){
System.out.printf("%d ",(Integer)e.nextElement());
}
for ( int k = 1; k <= N; k++){
int temp = -A[k];
if ( tbl.get(temp)!=null){
System.out.println("3 sum 0 exists"+temp);
}
}
}
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
Main o = new Main();
o.threeSum();
}
}
```

Can we take advantage of the fact that atleast one number must be negative.

say a + b + c = 0 and a = - (b+c);

say a is negative here. Then we search for combination of b and c such that summation is equal to negative of a. However our search is limited only for number of -ve number in the list. If list does not contain any negative number we probably can exit at start.

I am thinking we first sort the list

Then for each negative number do a search in nlog(n) time for the two number

O(n log n) + O(number of negative numbers * nlog(n))

= O(number of negative numbers * nlog(n))

For less number of negative numbers, this should work even better as O(nlogn), for large number of negative it should be O(n2)

Any comment

You can even do this in O(n log n) + O(number of negative numbers * n). Still, why the assumption that the number of negative numbers is small?

Hey, I have my code here, the solution is O(NlgN), any comments will be appreciated!

import java.util.ArrayList;

import java.util.Arrays;

public class Solution {

public static void main(String args[]){

int [] num = {-1, 0, 1, 2, -1, -4};

threeSum(num);

}

public static ArrayList<ArrayList<Integer>> threeSum(int[] num) {

// Start typing your Java solution below

// DO NOT write main() function

if(num.length<3 || num.length == 0 || num ==null)

return null;

Arrays.sort(num);

int i=0, j=num.length-1;

ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();

ArrayList<Integer> result;

while(i<j-1){

int v = 0 - num[i] - num[j];

if(binarySearch(num, i+1, j-1, v)){ //do binary search in between

result = new ArrayList<Integer>();

result.add(new Integer(num[i]));

result.add(new Integer(v));

result.add(new Integer(num[j]));

results.add(result);

if(num[i] == num[i+1]&&num[j-1]!=num[j]){ // handle the case when duplicates happens on the left

i++;

}

else if(num[i]!= num[i+1]&&num[j-1]==num[j]){// handle the case when duplicates happens on the right

j--;

}

else{ // if duplicates happens on both or neither happens

i++; j--;

}

}

else if(v > 0) // move to larger ones

i++;

else // move to slower ones

j--;

}

return results;

}

public static boolean binarySearch(int[] a, int lo, int hi, int key){

while (lo <= hi) {

// Key is in a[lo..hi] or not present.

int mid = lo + (hi - lo) / 2;

if (key < a[mid]) hi = mid - 1;

else if (key > a[mid]) lo = mid + 1;

else return true;

}

return false;

}

}

If only this algorithm were correct, it would be a pioneering research breakthrough, as solving this in subquadratic time is an important open research problem. Unfortunately, there's no reason to do i++ or j-- when you don't find the number in the binary search. You need a binary search for every *combination* of i and j, so making this correction, you'd end up taking O(n^2 logn) time.

```
public static void main(String arg[]){
int arr[]={-25, -1, -7, -3, 2, 4, 10, 10};
int length = arr.length;
for(int i=0; i<length; i++){
int a = arr[i];
int bInd = i + 1;
int cInd = length-1;
while( bInd<length ){
int b = arr[bInd];
int c = arr[cInd];
if( a+b+c ==0 ){
System.out.println( ""+a+"/"+b+"/"+c );
System.exit(0);
}
else if( a+b+c>0 ){
cInd--;
}
else{
bInd++;
}
}
}
System.out.println("not found");
}
```

At best we we do it in O(n^2).

- Arup Upapadhayay June 27, 2012