Microsoft Interview Question for Software Engineer / Developers


Country: India




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

Just search 3SUM on wikipedia. I swear I'm not making you look for porn.

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

It doesn't work for this case.

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

It works.
Hash all the possible sums and look for the numbers in c in the hash. Complexity is O(a.length*b.length)

- Naveen Reddy Mandadi August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you read the Wikipedia article, there's an algorithm that doesn't require hashing that also achieves O(n^2), except with a lower constant factor and deterministically.

- eugene.yarovoi August 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
7
of 7 vote

Here is the psudo code -

for each element x in C
find a pair A[i], B[j] from A and B such that A[i] + B[j] = -x
end

The outer loop will run for O(n) and inner loop also for O(n), so total complexity will be O(n^2).

To find a pair A[i], B[j] s.t A[i] + B[j] = k.
First make i point to the start of array A and point j to the end of array B.
check -
1. If A[i] + B[j] == k, we found our elements so just exit.
2. If A[i] + B[j] > k, we have to decrease our sum. Decrement j.
3. If A[i] + B[j] < k, we have to increase our sum. Increment i.

So this will run for O(n). Thus making the complexity of the complete method as O(n^2).

- Spock July 10, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is the best we can do.

- Water July 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

here we are assuming, elements are sorted in the array, but this fact is not mentioned in the question.

- sachin jain August 08, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Will not work..eg.
A={5,6};
B={7,15};
C={20,51};
To make the sum greater/lesser, how can u do it specifically by inc i or j?

- Avenger April 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

o(nlogm) solution can be done with some modification. Like take every element from a[0...n] subtract from and do binary search in the b[0...m].

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

that will be n^2 logn
pick every element from a, subtract from every element of c and binary search b

- sb June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is O(n^2 log n)

- Ashupriya June 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

private static class Pair
    {
        int a, b;
        
        public Pair(int a, int b)
        {
            this.a=a;
            this.b= b;
        }
        
        public String toString()
        {
            return "i: "+a+", j: "+b;
        }
    }
    
    public static void ultraQuickPrintArraySum(int[] a, int[] b, int[] c)//O(n)<=n^2 , Hashed. Get better hashing?
    {
        boolean CON= c[c.length-1]-c[0]<a[a.length-1]+b[b.length-1]-a[0]-b[0];
        int LEN= CON?c[c.length-1]-c[0]:a[a.length-1]+b[b.length-1]-a[0]-b[0];
        int OFFSET= CON?c[0]:a[0]+b[0];
        ArrayList[] hashedArray= new ArrayList[LEN+1];
        
        for(int i=0; i<a.length; i++)//o(n)=n^2. O(n)<=n^2
            for(int j=0; j<b.length; j++)
                if(a[i]+b[j]-c[0]>=0&&a[i]+b[j]-OFFSET<hashedArray.length)
                {
                    if(hashedArray[a[i]+b[j]-OFFSET]==null)
                        hashedArray[a[i]+b[j]-OFFSET]= new ArrayList<Pair>();
                    hashedArray[a[i]+b[j]-OFFSET].add(new Pair(i, j));
                }
        
        for(int i=0; i<c.length; i++)//o(n)=n. O(n)<=n
            if(c[i]-OFFSET<hashedArray.length&&hashedArray[c[i]-OFFSET]!=null)
                System.out.println(hashedArray[c[i]-OFFSET]+", k: "+i);
    }

- nj August 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static void resultHashedQuickPrintArraySum(int[] a, int[] b, int[] c)//O(n)<=n^2 . Efficient hashing.
    {
        boolean CON= c[c.length-1]-c[0]<a[a.length-1]+b[b.length-1]-a[0]-b[0];
        int MINMAX= CON?c[c.length-1]-c[0]:a[a.length-1]+b[b.length-1]-a[0]-b[0];
        int OFFSET= CON?c[0]:a[0]+b[0];
        
        String[][] hashedArray= new String[(int)Math.ceil((double)(MINMAX-OFFSET)/(0x1<<8))][];
        double alphaRatio= Math.ceil((double)(MINMAX-OFFSET)/(double)hashedArray.length);
        
        for(int i=0; i<c.length; i++)//o(n)=n. O(n)<=n
        {
            int correctedNumber= c[i]-OFFSET;
            int index= (int)((double)correctedNumber/alphaRatio);
            if(index>=0&&index<hashedArray.length)
            { 
                if(hashedArray[index]==null)
                        hashedArray[index]= new String[(int)Math.ceil(alphaRatio)];
                    
                    int offsetIndex= correctedNumber-(int)((double)index*alphaRatio);
                    
                    hashedArray[index][offsetIndex]=hashedArray[index][offsetIndex]==null?"":hashedArray[index][offsetIndex];
                    hashedArray[index][offsetIndex]+="k: "+i;
            }
        }
        
        for(int i=0; i<a.length; i++)//o(n)=n^2. O(n)<=n^2
            for(int j=0; j<b.length; j++)
            {
                int correctedNumber= a[i]+b[j]-OFFSET;
                int index= (int)(((double)correctedNumber)/alphaRatio);
                if(index>=0&&index<hashedArray.length&&hashedArray[index]!=null)
                {                     
                    if(hashedArray[index][(correctedNumber-(int)((double)index*alphaRatio))]!=null)
                        System.out.println(hashedArray[index][(correctedNumber-(int)((double)index*alphaRatio))]+", i: "+i+", j: "+j);
                }
            }
        
        
    }

- nj August 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@sb : was this in written test or interview ???

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

telephonic interview

- sb June 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String ar[]){
		int arr1[]={1,2,3,4,5,6};
		int arr2[]={1,2,3,4,5,6};
		int arr3[]={1,2,3,4,5,6};
		
		int i, j, k=0;
		
		while( k<arr3.length ){
			for( i=0;i<arr1.length;i++ ){
				if( arr1[i]<arr3[k]){
					for( j=0;j<arr2.length;j++ ){
						if( arr1[i]+arr2[j]==arr3[k] ){
							System.out.println( arr1[i]+"/"+arr2[j]+"/"+arr3[k] );
						}
						else if( arr1[i]+arr2[j]> arr3[k]){
							break;
						}
					}
				}
			}			
			k++;
		}
	}

output:
1/1/2
1/2/3
2/1/3
1/3/4
2/2/4
3/1/4
1/4/5
2/3/5
3/2/5
4/1/5
1/5/6
2/4/6
3/3/6
4/2/6
5/1/6

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

that is the simplest of the solution we can give for the problem with time complexity O(n^2) or O(mn)....

any idea how we can improve it

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

you are making a wrong assumption that all the arrays contains only positive numbers.

- rohithindustani2004 July 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think that is O(n^3)

- Water July 23, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be solved in O(n^2) time and O(n) space.

1. Store all the values of c array in a hashmap with value as index - O(n) space
2. Then get the sum of all the pairs of elements of array a and array b and check whether they are present in hashmap.
3. If present then print the values.

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

Assuming that each array contains n elements.
Can be easily modified for different elements also

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

Hashmap is no doubt a smart approach which reduces the computational complexity. But you missed one thing- what if c contains negative numbers?

- ramblersm July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@ramblesrm: It could be easily done by using C++ maps, would work for negative elements also

- alexander July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks for the information. I would like to read about that. Could you provide me a link please?

And help me out here, but our algorithm should be language-independent..

- ramblersm July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ww.cplusplus.com/reference/stl/map
check this

- alexander July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

A couple things. 1) there is absolutely no reason a HashMap couldn't work with negative numbers 2) to avoid needlessly wasting space, you should use sets instead of maps here. You only need keys here, not key-value pairs. 3) C++-style sets are called TreeSet in Java, and many languages have some sort of support for these.

- eugene.yarovoi July 05, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

i = j =k = 0;
while(k<k_max && i<i_max && j<j_max) {
    if (a[i] + b[j] == c[k]) {
         // print a,b,c
         k++;
    } 
    else if (a[i] + b[j] > c[k]) {
       k++; 
    } 
    else if (a[i] + b[j] < c[k]) {
       if (a[i+1] < b[j+1] )
           i++;
       else
           j++;
    }
}

UPDATE: this code does'n work.

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

Not working for:
a[]=3,5
b[]=1,6
c[]=6,18

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

to shondik:
I'm sorry I forget add '1' in line if (a[i] < b[j] ).
But it been in my mind.
Try it again.

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

This logic looks correct

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

This code assumes that there will be only one pair of (i,j) that would satisfy the given condition which is not correct.
Try with example a = b = [1,2,3], c= [4].

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

Are we assuming that i,j,k are always equal .. i.e. All array sizes are the same ?

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

to basha:
no it work for any i, j, k.
Feel free to try it without any questions :-)

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

Check you output for:
a[]=8,3
b[]=7,3;
c[]=6

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

to shondik
sorted ..

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

@zprogd : please write your final code including the statement { if(a[i]<b[j]) } which you forgot to write

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

fail case
a = 1,2
b = 1, 5
c = 6

- sb June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

to sb:
thank you.

- zprogd June 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.Take two pointers, i pointing to the start of a[] & j pointing to the start of b[].
2. for every item in c[], find a pair of items in a[] & b[](O(m+n)).
So, time complexity is: k(m+n) where c[] contains k elements.

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

@shondik:
Your algorithm doesn't give all the pairs
Take a[]={1,3,6}
b[]={1,6,7}

For an item = 7 in c
Your algo will print (1,6,7) and not (6,1,7)
Bcoz that can't be done in O(m+n) time

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

Ok, to print all pairs. when a pair is found ,don't stop continue the search by incrementing i & decrementing.[i++,j--]

- Aashish June 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<stdlib.h>
int main()
{
int i=0,a[]={1,5,7,9,12};
int j=0,b[]={3,8,14,15,19,20};
int k=0,c[]={5,12,17,23,25,26,30};
int ie=(int)sizeof(a)/sizeof(a[0]);
int je=(int)sizeof(b)/sizeof(b[0]);
int ke=(int)sizeof(c)/sizeof(c[0]);
int t=1;
while(1)
{
if(a[i]+b[j]==c[k])
{
printf("a[%d]=%d , b[%d]=%d , c[%d]=%d \n",i+1,a[i],j+1,b[j],k+1,c[k]);
j++;
k++;
}
else if(a[i]+b[j]>c[k])
{
if(a[i]>b[j])
while(1)
{ i--;
if(a[i]+b[j]<c[k])
{ k++;break; }
else if(a[i]+b[j]==c[k]) break;
}
else {
while(1)
{ j--;
if(a[i]+b[j]<c[k])
{ k++;break; }
else if(a[i]+b[j]==c[k]) break;
}
}
}
else {
if(a[i]>=b[j])
j++;
else i++;
}
if(i>=ie||j>=je||k>=ke)
break;
}
return 0;
}

- Shobhit June 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

indentation...:(

- mindboggler July 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
main()
{
int i,j,n,m;
int c[100];
int a[100];
int b[100];
printf("both array size are same\n");
scanf("%d",&n);
scanf("%d",&m);
for(i=0;i<n;i++)
scanf("%d",&a[i]);


printf("\n");
for(i=0;i<m;i++)
scanf("%d",&b[i]);

if(n==m)
{
for(i=0;i<n;i++)
c[i]=a[i]+b[i];
for(i=0;i<n;i++)
printf("%3d\n",c[i]);

}
else
printf("arrey size is note same");

}

- yogesh kumar sharma July 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main(string[] args)
        {
            int[] a = new int[2] { 1, 2};
            int[] b = new int[3] { 2, 4, 5};
            int[] c = new int[3] { 3, 4, 6};

            int i, j=0, k=0, alen = a.Length, blen = b.Length, clen = c.Length;

            for (i = 0; i < alen; i++)
            {
                j = k = 0;
                while(j<blen)
                {
                   
                    if (k >= clen)
                    {
                        j++;
                        continue;
                    }
                   
                    else if (a[i] + b[j] == c[k])
                    {
                        Console.WriteLine(a[i] + "-" + b[j] + "-" + c[k]);
                        k++;
                        if (j > blen-1)
                            break;
                       
                    }
                    else
                    {
                        k++;
                        if (k >= clen)
                        {
                            j++;
                            k = 0;
                        }
                     
                        
                    }

                 
                 
                }

- jeanclaude July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I initially had a O(n^3), but later brought this down to O(n^2). Not tried to check if it can still be brought down to linear (O(n)).

- jeanclaude July 19, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This still look like O(n^3) and not O(n^2)?

- imkul August 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.dsna.puzzles;

import java.util.HashMap;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;


//given 3 arrays, array a, array b, array c.
//find all pairs where a[i] + b[j] = c[k]
//a, b , c are sorted

public class ArrayAdditionPuzzle {

	int[] arrayA = new int[]{10,20,30,40,50,60,70,80,90,100,200};
	int[] arrayB = new int[]{20,40,60,80,300};
	int[] arrayC = new int[]{40,80,100};
	
	public static void main(String[] args) {
		new ArrayAdditionPuzzle().findPairs();
	}
	
	public void findPairs(){
		
		int maxArrayC = arrayC[arrayC.length-1];
		HashMap<Integer,Integer> arrayCContents = new HashMap<Integer, Integer>();
		for(int i=0;i<arrayC.length;i++){
			arrayCContents.put(arrayC[i], i);
		}
		
		
		
		for(int i=0 ; i< arrayA.length ; i++){
			if(arrayA[i] > maxArrayC){
				break;
			}
			for(int j=0; j<arrayB.length;j++){
				if(arrayB[j]> maxArrayC || arrayA[i]+arrayB[j] > maxArrayC){
					break;
				}else{
					if(arrayCContents.containsKey(arrayA[i] + arrayB[j])){
						System.out.println("arrayA[" +i + "] + arrayB[" +j + "] = arrayC[" + arrayCContents.get(arrayA[i]+arrayB[j]) +"]" );
					}
				}
			}
		}
		
	}
	
}

- Amit December 01, 2012 | 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