Microsoft Microsoft Interview Question for Software Engineer in Tests


Team: Office
Country: United States
Interview Type: In-Person




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

Say the two arrays are: a[] of size n and b[] of size m.
Declare another array c[] of size m+n
Compare a[i] with b[j], put the smaller value into c[k]
keep incrementing the index of the array whose element is smaller and put it into c[k++]
keep continuing this unless one of the arrays is used.
Now since the other array is sorted already, simply copy all the remaining elements into c[].
Our merged array is ready!

- Anonymous January 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

I think you also have to consider the case their a[i]=b[j], where then you would simply make the next entry of c=a[i] and then at the end, you would need to count the number of null entries in the array, make a new array of the appropriate size, and copy the entries over.

- SL January 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@SL: the note about a[i] == b[j] is correct, because otherwise you'll end up with duplicates on the merge resultn, and then the result size could be less and n + m.

- hnrqbaggio January 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Yes.. I happened to miss that condition out..
Here is the code after incorporating the condition for equality:

package com.career.cup;

 class MergeWithoutDuplicates {

	static int[] getMergedArrayWithoutDuplicates(int[] firstArray, int[] secondArray)
	{
		int firstArraySize=firstArray.length;
		int secondArraySize=secondArray.length;
		int i=0,j=0,k=0;
		int[] resArray=new int[firstArraySize+secondArraySize];
		while(i<firstArraySize && j<secondArraySize)
		{
			if(firstArray[i]==secondArray[j])
			{
				resArray[k++]=firstArray[i++];
				j++;
			}
			
			else if(firstArray[i]<secondArray[j])
				resArray[k++]=firstArray[i++];
			
			else
				resArray[k++]=secondArray[j++];
				
		}
		
		while(i<firstArraySize)
			resArray[k++]=firstArray[i++];
		
		while(j<secondArraySize)
			resArray[k++]=secondArray[j++];
		
		return resArray;
	}
	
	public static void main(String[] args)
	{
		int[] firstArray={1,2,6,9,10,27};
		int[] secondArray={2,8,10,89};
		for(int resIndividualElement: getMergedArrayWithoutDuplicates(firstArray,secondArray))
		{
			System.out.println(resIndividualElement);
		}
	}
}

This solution works fine but since we created an array of size (m+n) and when there are duplicates, we dont use some of these slots in the result array we are returning which are initialized to 0. Can someone please suggest how we could avoid this without having to create a whole new array only to accommodate the size.

- teli.vaibhav January 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

One thing you might have missed it here, Suppose we have arrays like
int[] a ={1,5,6,7,9,12,17};
int[] b = {2,3,4,7,10,11,12,18,22};
the way u have mentioned, we will get something like
{1,2,3,5,4,6,7,9,10,11,12}

But , this contradicts the assumption, i.e result should be sorted.

Correct me if i am wrong .

- sushant001 May 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sushant001:kindly check ur ans the result by using above algo will be {1,2,3,4,5,6,7,9,10,11,12,17,18,22} bcoz while cmpring 3 and 5 index of b will be incrmnted and nw it will pt to 4 since 4 is also less than 5 than 4 will be oinserted into new array and now agn index of b will be incremented and it will point to 7 i hope u got it

- codex June 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

think about this case
[1,2,3]
[3,3,3,4,4,4]

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

Question says that both input arrays are sets.
[3,3,3,4,4,4] is not a valid set.

- Sudhakar August 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

void Merge(int * a, int m, int * b, int n, vector<int>& c)
{
	int p = 0; int q = 0;
	while (p < m && q < n)
	{
		if (a[p] < b[q])
		{
			c.push_back(a[p++]);
		}
		else if (a[p] > b[q])
		{
			c.push_back(b[q++]);
		}else
		{
			c.push_back(a[p++]);
			q++;
		}
	}
	while (p < m)
	{
		c.push_back(a[p++]);
	}
	while (q < n)
	{
		c.push_back(b[q++]);
	}
}

- speedmancs January 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good solution.

With the STL vector there isn't the problem of the find the size of the merged set, and the effect the vector reallocation on the time complexity is negligible.

But in this case it's worth to note that the resulting container's type is not the same of the inputs'.

- hnrqbaggio February 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Use binary search tree is the most efficient way to solve this problem.
In Java, we have TreeSet.
You could also implement your own binary tree and add data into this tree.

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;
import java.util.TreeSet;


public class MergeSet {
	
	public static Set<Integer> mergeSets(LinkedList<Integer> set1, LinkedList<Integer> set2){
		Set<Integer> resultSet = new TreeSet<Integer>();
		for(int i=0;i<set1.size();i++){
			int value = set1.get(i);
			if(value > 0){
				resultSet.add(value);
			}
		}
		
		for(int i=0;i<set2.size();i++){
			int value = set2.get(i);
			if(value > 0){
				resultSet.add(value);
			}
		}
		return resultSet;
	}
	
	public static void main(String[] args){
		LinkedList<Integer> set1 = new LinkedList<Integer>();
		set1.add(3);
		set1.add(4);
		set1.add(-1);
		set1.add(0);
		LinkedList<Integer> set2 = new LinkedList<Integer>();
		set2.add(3);
		set2.add(2);
		set2.add(-3);
		set2.add(4);
		Set<Integer> result = mergeSets(set1,set2);
		System.out.println(result);
	}
}

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

This question is a complement of this one: 15273751

- hnrqbaggio January 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Somewhat similar to 15290749

- Messiah January 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how about maintaining a simple BST. or a TreeSet in java

- the_one January 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is the runtime for this O(n) ? n being size of the larger of the two sorted lists?

- mdzy February 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can just merge both the arrays and sort it and put it in a hashset.

public static void main(String[] args)
{
int[] a ={1,5,6,7,9,12,17};
int[] b = {2,3,4,7,10,11,12,18,22};
int[]c=new int[a.length+b.length];
for(int i=0;i<=a.length-1;i++)
{
c[i]=a[i];
}
for(int i=a.length,j=0;i<=c.length-1;i++,j++)
{
c[i]=b[j];
}
Arrays.sort(c);
HashSet<Integer> hset=new HashSet<>();
for(int num:c)
{
hset.add(num);
}
System.out.println(hset);
}

- Alok February 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedHashSet;
import java.util.Set;

public class MergeSortedArrays {

	public static void main(String[] args) {
		int[] a= {1,2,6,9,10,27};
		int[] b= {2,8,10,89};
		int[] result=merge(a,b);
		Set<Integer> set = new LinkedHashSet<Integer>();
		for(int i : result)
		{
			set.add(i);
		}
		System.out.println(set);
		

	}
	public static int[] merge(int[] a,int[] b)
	{
		int m=0;int n=0;
		int k=a.length+b.length;
		int[] c=new int[k];
		int j=0;
		while(m<a.length && n<b.length)
		{
			c[j++] = a[m]<=b[n] ? a[m++] :b[n++];
		}
		while(m<a.length)
		{
			c[j++]=a[m++];
		}
		while(n<b.length)
		{
			c[j++]=b[n++];
		}
		return c;
	}

}

- Shabana Khan May 31, 2020 | 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