## Microsoft Interview Question

• 0

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

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

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

The algorithm to solve 3 sum problem is explained beautifully in youtube, watch it at
youtu.be/hLabfN0zjeU

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

No we cannot.

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

``````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();
}

}``````

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

The algorithm to solve 3 sum problem has been explained in the video at youtube
youtu.be/hLabfN0zjeU

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

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

I don't think there's a proof that it's impossible, but no subquadratic algorithm is known for general inputs.

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

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

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

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?

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

It wont work if you search for each negative number as input can be -1,-2,0,3 i,e sum of -1-2=3

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

This is probably lame
1) Sort using merge sort O(nlogn)
2) Do 3SUM

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

this solution is without sorting the numbers. Also would work if you pass in k for kSum

``````static String[] sumzero(int[] intArr, int i, ArrayList<String> output) {

if(i >= intArr.length) {
return output.toArray(new String[output.size()]);
}

for(int k = 1; k < 4; k++) {
if(i+k+k < intArr.length) {
int sum = intArr[i] + intArr[i + k] + intArr[i + k + k];
if(sum == 0) {
//                        System.out.println(intArr[i] + ", " + intArr[i + k] + ", " + intArr[i + k + k]);
output.add(intArr[i] + "," + intArr[i + k] + "," + intArr[i + k + k]);
}
}
}
sumzero(intArr, i+1, output);

return output.toArray(new String[output.size()]);
}``````

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

``````#include<stdio.h>

void main()
{
int i,j;

int arr[]={-9,5,3,7,8,17,1};

for(i=0;i<7;i++)
{

int a=arr[i];
int b=i+1;
while(b<7)
{
int p=arr[b];

int s=p+a;

for( j=(b+1);j<=6;j++)
{
int y=arr[j];
int rs=y+s;
if(rs==0)
printf("found\n");
}
b++;

}
}
}``````

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

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

}

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

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.

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````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++;
}
}
}
}``````

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

Right, that is the N^2 solution. No asymptotically better solution is known.

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

Your code will work only if the array is sorted like you have taken.

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

Sorry,Have you tried this code with the array that you have taken
?.

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.