Microsoft Interview Question for Software Engineer Interns


Country: United States
Interview Type: Phone Interview




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

Here is straight forward and simple solution ....no magic behind this... just putting all unique sums in a min heap.. and returning 3rd element from the heap.

public static int getNthElement(int[] A, int[] B){
		MinHeap<Integer> maxHeap = new MinHeap<Integer>();
		int m = A.length;
		int  n = B.length;
		int maxLength = Math.max(m,n);
		
		for(int i = 0; i < m; i++){		
				for(int j = 0; j < n; j++){
					maxHeap.insert(A[i] + B[j]);
				}
		}

		return maxHeap.getNthElement(3);
		
	}

- Ajeet November 02, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't think your solution will work. As minHeap can only return the min element but there is no guarantee that minHeap.get(i + 1) > minHeap.get(i), except for i = 0

- Kelvin November 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Kelvin
I missed to mention getNthElement(int N) method. here it is ...
I am using concept of heap sort to find Nth element ..But I am not sorting all elements. it will sort only N elements.

public int getNthElement(int N){
 int result = 0;
 for(int i =0; i<N; i++){
    result = minHeap.removeRoot();
    minHeap.heapify();
 }
 return result;

- Ajeet November 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can first insert elements (a[i], b[0]) into a heap for all i. When we pull out (a[i], b[j]) from heap, we can insert (a[i], b[j+1]) into the heap.

- WKS November 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

Could you please give an example ?

- amber October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

suppose that array A is {1,3,4,8,10}, array B is {20, 22, 30, 40}. then the sum set will be{21(1+20),23(1+22 or 3+20), 25(3+22), 24(4+22)...} the 3rd element in the sum set is 25.

- ophis.W October 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

The task is not clear, but i guess, that we are speaking about finding K-th sum from a[i]+b[j] for ANY {i, j}. Becouse if i==j, it is simply binary search, and there is no reason to complicate the task description.
___________________________

This task reduced to another popular task, which has been discussed here many times:
Find K-th element in Sorted Matrix.

Let's imagine that we have N*M Matrix: S[i][j] = a[i]+b[j];

a[0]+b[0]	a[0]+b[1]	...	a[0]+b[m]
a[1]+b[0]	a[1]+b[1]	...	a[1]+b[m]
...
a[n]+b[0]	a[n]+b[1]	...	a[n]+b[m]

A and B was sorted list. So each column and each row is sorted too.
Here is the link to solution:

question?id=6335704
or you can find it, as the most commented question from Google's interview.

I use word 'imagine', becouse we don't need to build it for real.
To solve derivative problem, all numbers from matrix are needed only once, so we can calculate sum in runtime, without saving to matrix.

- Darida October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

findSumAtNthElement(A1,A2,N)
{
   int diff= A1-A2;
   if(diff==0){
		SumAtN = A1[n-1]+ A2[n-1];		
   }
   
   if(diff<0)
   {
        SumAtN = A2[n-1] 
   }else{
		SumAtN = A1[n-1]-
   }

}

- yami1 October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

We can assume matrix with these two array... like A represents rows and B represents    columns.
We need only 3rd element, it will lie in 3X3 matrix if more than 7 sums are not same(duplicate). 
   So first we will check in first 3X3 matrix than move to 6X6 ...9X9 .... so on.

int m = length of first array;
int n = length of second array;
MaxHeap maxHeap = new MaxHeap(3); // Max heap without duplicate, add() method will check if there is duplicate.
int maxLength = max(m,n);
for(k = 0; K < maxLength; K = K+3){
	for(int i = K; (i < K+3) && (i < m); i++){		
		for(int j = K; (j < K+3) && (j < n); j++){
			maxHeap.add(A[i]*B[j]);
			if(maxHeap.size() == 3){
				return maxHeap.root();
			}	
		}

	}
}

- Ajeet October 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Avoid * ... it is typo .. it should be +

- Ajeet October 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you explain why you used matrix 3x3? If you need only 3rd element, why don't you use matrix 2x2, which gives the first four sums?

- Anonymous October 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We need to find 3rd element, it will be 3rd in row (if row elements are smaller than columns - like in this question) and similar for column, if column's elements are smaller than rows.
If we have duplicates than we have to check for bigger array in next iteration.

- Ajeet October 31, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't think this is correct. Think about the below sample arrays. It cannot get the correct result 8

ArrayA: 1, 1, 1, 2, 2, 2, 3, 3, 3
ArrayB: 5, 5, 5, 10, 10, 10, 20, 20, 20

- digjim November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@digjim
Thanks pointing that out ... this approach will not work. I tried to reduce the number of iteration. It will work with all unique sums in heap. No magic behind this.

public static int getNthElement(int[] A, int[] B){
		MinHeap<Integer> maxHeap = new MinHeap<Integer>();
		int m = A.length;
		int  n = B.length;
		int maxLength = Math.max(m,n);
		
		for(int i = 0; i < m; i++){		
				for(int j = 0; j < n; j++){
					maxHeap.insert(A[i] + B[j]);
				}
		}

		return maxHeap.getNthElement(3);
		
	}

- Ajeet November 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually, If there is no duplicated items in Array, your solution is pretty good. What do you think about my solution I posted below. I added below three condition in the for().

i < nth
j < nth
i+j < nth

- digjim November 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If having the asumption - no dup numbers in each array. Matrix [3*3] is a better solution. I think this is a good point to talk with interviewer.

- changjia2007 November 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since the arrays are sorted, a modified *merge* subroutine (of mergesort) can get the job done in O(n) time and O(1) space.

The arrays' *walk* of merge subroutine can keep track of the previously computed sum and current sum to disregard duplicates and stop when the Nth sum is reached.

The arrays' walk can be done as follows: Given indices i and j, we have previoussum = a[i] + a[j] and currentsum= Min((a[i] + a[j+1]) , (a[i+1] + a[j])). Update the pointers i & j accordingly for the next step in the arrays' walk.

- Murali Mohan October 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice one.

- Ajeet November 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL. Wrong.

- Anonymous November 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Since we only need to check the matrix on top-left, we can have two loop (i, j) , and i+j must less than the Nth.

array A is {1,3,4,8,10}, 
array B is {20, 22, 30, 40}. 

the sum set will be{21(1+20),23(1+22 or 3+20), 25(3+22), 24(4+20), 26(4+22)...} 
the 3rd element in the sum set is 24.

public static int GetNthSum(int[] arrayA, int[] arrayB, int nth)
        {
            // Remove duplicated first in two arrays
            int[] sumList = new int[nth];
            int tempSum;
            int temp;
            int tempCount = 0;

            for (int i = 0; i < arrayA.Length && i < nth; i++)
            {
                for (int j = 0; j < arrayB.Length && j < nth && i + j <= nth; j++)
                {
                    tempSum = arrayA[i] + arrayB[j];

                    for (int k = 0; k < nth; k++)
                    {
                        if (k == tempCount)
                        {
                            sumList[k] = tempSum;
                            tempCount++;
                            break;
                        }
                        else
                        {
                            if (tempSum == sumList[k])
                            {
                                break;
                            }
                            else if (tempSum < sumList[k])
                            {
                                temp = sumList[k];
                                sumList[k] = tempSum;
                                tempSum = temp;
                            }
                        }
                    }
                }
            }

            if (tempCount == nth)
            {
                return sumList[tempCount - 1];
            }
            else
            {
                return -1;
            }
        }

- digjim November 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am not sure if this is the approach, or I could explain my logic properly, any clarifications...welcome
This works in nlog(smaller array.length) time, where n is the position of the number we are trying to find
If someone could find any bug then welcome... :-)

a[] = { 1, 3, 4, 8 , 10}
b[] = {20, 22, 30 ,40}

1. create an array index[b.length] )sizeof the smaller array, value 0 for each element
2. index array will contain current index of array a, for each element of array b
3. Create a min heap of size b.length, to get the current min
4. insert sum of a[0] + b[i] into the min heap (20 + 1, 22 + 1, 30 + 1, 40 + 1)
5. Now until we get the nth element, do the following
6. extract the current min (in this case 20+1)
7. increament the corresponding index pointer in this case index of 20 will be increamented to 1 from 0
8. insert this new element in to the heap (in this case 20 + 3 will be inserted into the heap)

//so next time the comparision will be between 20 + 3, 22 + 1, 30 + 1, 40 + 1

9. one thing we need to take care of, like for the below case
a[] = {1,2,3,4,5}
b[] = {20, 60, 80, 100}

if index of an element exceeds the limit like in the above case, 20+1, 20+2, 20+3, 20+4, 20+5 and then it exceeds so insert INT_MAX into the heap,
so that the pointer of 20 will never get increamented again.

We can take care of the duplicate sum like 20+3, 22+1 case through this logic also, by maintaining a prev min and current extracted min.

- dhiren.bhuyan November 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the solution

class Node implements Comparable<Node> {
    int sum, ai, bi;

    public Node(int s, int a, int b) {
        this.sum = s;
        this.ai = a;
        this.bi = b;
    }

    @Override
    public int compareTo(Node o) {
        return this.sum - o.sum;
    }

    @Override
    public String toString() {
        return "Node{" +
                "sum=" + sum +
                ", ai=" + ai +
                ", bi=" + bi +
                '}';
    }
}



/**
 * Duplicate sum Not allowed
 * Algo:
 * 1. create all the sum nodes for a[i] + b[0]
 * 2. Build priority queue using above nodes
 * 3. For each poll
 * *    3.1: Insert the appropriate pair in PQ either a[i+1]+b[j] or a[i]+b[j+1] if not seen as pair, not seen as sum
 *
 * Time Complexity:  N length of a[], M length of b[]
 * Step 1: O(N)
 * Step 2: O(N) Priority queue could be build in O(n)
 * step 3: In worst case, all the sum are unique and we need to find the last element. This case PQ will contain max(N,M)+1 elements since we remove 1 and add 2 so effectively adding 1 element.
 * That takes O(log(Max(N,M)) time run for n times { n= nth sum element}
 * O(n * log(Max(N,M) )
 *
 * O(N) + O(N) + O(n * log(Max(N,M) )  => O(n * log(Max(N,M) )
 *
 * Space: O(Max(N,M))
 *
 */
class SolutionNthItemInSumOfTwoArraysDuplicateSumNotAllowed {


    public int nthItem(int[] a, int[] b, int n) {

        if (a == null || a.length == 0) {
            if (b.length >= n)
                return b[n - 1];
            else
                return Integer.MIN_VALUE;
        }

        if (b == null || b.length == 0) {
            if (a.length >= n)
                return a[n - 1];
            else
                return Integer.MIN_VALUE;
        }

        return nthItem(a, b, a.length, b.length, n);
    }


    private int nthItem(int[] a, int[] b, int aLength, int bLength, int n) {


        Set<int[]> seenPair = new HashSet<>();
        Set<Integer> sumSeen = new HashSet<>();
        List<Node> nodes = new ArrayList<>();

        //O(aLength)
        for (int i = 0; i < a.length; i++) {
            int sum = a[i] + b[0];
            if (!sumSeen.contains(sum)) {
                nodes.add(new Node(a[i] + b[0], i, 0));
                sumSeen.add(sum);
                seenPair.add(new int[]{i, 0});
            }
        }

        //O(aLength)
        PriorityQueue<Node> priorityQueue = new PriorityQueue<>(nodes);

        int i = 0;
        Node currentPair = null;


        while (i < n && !priorityQueue.isEmpty()) {

            currentPair = priorityQueue.poll();

            int[] pairWithA = {currentPair.ai + 1, currentPair.bi};
            int[] pairWithB = {currentPair.ai, currentPair.bi + 1};

            if (!seenPair.contains(pairWithA) && currentPair.ai + 1 < aLength && !sumSeen.contains(a[currentPair.ai + 1] + b[currentPair.bi])) {
                seenPair.add(pairWithA);
                sumSeen.add(a[currentPair.ai + 1] + b[currentPair.bi]);
                priorityQueue.offer(new Node(a[currentPair.ai + 1] + b[currentPair.bi], currentPair.ai + 1, currentPair.bi));
            }

            if (!seenPair.contains(pairWithB) && currentPair.bi + 1 < bLength && !sumSeen.contains(a[currentPair.ai] + b[currentPair.bi + 1])) {
                seenPair.add(pairWithA);
                sumSeen.add(a[currentPair.ai] + b[currentPair.bi + 1]);
                priorityQueue.offer(new Node(a[currentPair.ai] + b[currentPair.bi + 1], currentPair.ai, currentPair.bi + 1));
            }
            i++;

        }

        if (i < n)
            return Integer.MAX_VALUE;
        assert currentPair != null;
        return currentPair.sum;
    }
}

- nitinguptaiit September 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Let array a anb array b ,start from start of both i,j i=0 j=0, now a[i]+b[j] is lowest sum possible ,counter =1,now compare a[i+1] with b[j+1] which one is smaller increase the respective value of i or j and find next lower sum and do counter++ do this upto counter!=N

- rdx October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Are you sure comparing a[i+1] with b[j+1] enough?

Do you need a counter? Running loop on condition i+j < N should be enough.

- Urik's twin Cookie Monster (dead now) October 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Ahh ic. The question is funky in wording. "Set" and Nth element just do not work together in terms of definition.

Why wouldn't an _idiot_ posting this question give an example at least?
input
0 1 2 20 21 22
10 11 12 14 15 59

output
"What's the order" of this "set of pairs/sums" ?

Guess what, writing the example with automatically give the idiot the algorithm. So let him/her do that? Not my decision.

- Urik's twin Cookie Monster (dead now) October 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is counterexample

L1: 0, 10, 20, 30, 40, ... (Total N elements)
L2: 1, 2, 3, 4, 5, 6, 7, 8, 9 (Total M=9 elements)

- Darida October 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

#include<stdio.h>
int main(){
int n,N,i;
scanf("%d",&n);
scanf("%d",&N);
int a[n],b[n],c[n];
for(i=0;i<n;i++){
scanf("%d",&a[i]);}
for(i=0;i<n;i++){
scanf("%d",&b[i]);}
for(i=0;i<n;i++){
c[i]=a[i]+b[i];}
printf("%d\n",c[N]);

return 0;
}

- Bhargavi October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I am adding both array (start from least significant digits). We need to find sum till (length -n)th element.

Example:  Suppose we need to find 2nd sum ... 
          than we will stop after (5+1 - 2)th element and we will return it.
1  2  3  4  5
1  2  3  4  5
-------------------
-  4  6  9  0
int *AddArrays(int a[], int alen, int b[], int blen, int n)
{
	int maxLen = max(alen, blen);
	int *c = new int[maxLen + 1];

	int acur = alen - 1;
	int bcur = blen - 1;
	int ccur = maxLen;
	int carry = 0;

	//Nth from start will be (length of sum array - N)th from end.
	int nth =  (maxLen + 1 - n);

	while(ccur >= 0)
	{	if(nth-- == 0){
			return c[ccur];
		}

		int cur = carry;
		if(acur >= 0)
			cur += a[acur--];
		if(bcur >= 0)
			cur += b[bcur--];

		c[ccur--] = cur % 10;
		carry = cur/10;
}

return c;
}

- Ajeet October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

After modification of question, this answer does not make sense so pls avoid this.

Answer should be submitted in single go.... :(

- Ajeet October 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

why negative ....it was correct answer for original question ....

- Ajeet October 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The question is not clear. So, I am making following assumptions.

1. Set of sums mean {a[0]+b[0], a[0]+b[1], ...a[1]+b[0], a[1]+b[1].....}
2. Length of array a is lenA and length of array b is arrayB

So, the Nth element would a[N/lenB] + b[N%lenB]

- mindless monk October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

findSumAtNthElement(A1,A2,N)
{
int diff= A1-A2;
if(diff==0){
SumAtN = A1[n-1]+ A2[n-1];
}

if(diff<0)
{
SumAtN = A2[n-1]
}else{
SumAtN = A1[n-1]-
}

}

- yami1 October 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

here is the simple impletation in c# with O(n):

static void FindNthCrossSum(int n)
        {
            int i = 1;
            int p1 = 0;
            int p2 = 0;
            var result = 0;
            if (n == 1) { 
               Console.WriteLine("First:{0}", s1[0] + s2[0]);
               return; 
            }
            while (i++ < n && p1 < s1.Length && p2 < s2.Length)
            {
                result = GetSum(s1, ref p1, s2, ref p2);
            }
            Console.WriteLine("{0}th result:{1}", n, result);
        }

        static int GetSum(int[] s1, ref int p1, int[] s2, ref int p2)
        {
            var sum1 = s1[p1];
            if (p2 < s2.Length - 1) { sum1 += s2[p2 + 1];}
            var sum2 = s2[p2];
            if (p1 < s1.Length -1) { sum2 += s1[p1 + 1] ;}
            if (sum1 < sum2)
            {
                p2++;
                return sum1;
            }
            else if (sum1 == sum2)
            {
                if (s1[p1] < s2[p2])
                {
                    p2++;
                }
                else
                {
                    p1++;
                }
                return sum1;
            }
            p1++;
            return sum2;
        }

- jkyshu October 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The sample in the question is not correct, the 3rd should be 24.

The result is wrong, it returned 25.

if I want to get 10th, it throw exception.

- digjim November 01, 2013 | Flag
Comment hidden because of low score. Click to expand.


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