Microsoft Interview Question

  • microsoft-interview-questions
    0
    of 0 votes
    17
    Answers

    Can we do 3 sum problem on unsorted array in time (n logn) ?
    3 sum problem : given unsorted array you have to find 3 numbers such that their sum is zero.

    - ninja on June 27, 2012 Report Duplicate | Flag
    Microsoft



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

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

- Arup Upapadhayay on June 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on June 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

No we cannot.

- loveCoding on June 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

}

- ssaurabh on June 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on June 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Follow this link for more details: en.wikipedia.org/wiki/3SUM

- Aashish on June 27, 2012 | Flag Reply
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.

- eugene.yarovoi on June 27, 2012 | Flag Reply
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

- Pramod Chandoria on July 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- eugene.yarovoi on July 07, 2012 | Flag
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

- DarkKnight on July 23, 2012 | Flag Reply
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++;

  }
  }
}

- payal kumawat on June 27, 2012 | Flag Reply
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>();
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;
}

}

- Jeffery on July 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- eugene.yarovoi on July 22, 2012 | Flag
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++;
				}
			}
		}
		System.out.println("not found");
	}

- Anonymous on June 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- eugene.yarovoi on June 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- TechGroup on August 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- TechGroup on August 06, 2012 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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