Microsoft Microsoft Interview Question
Software Engineer in TestsTeam: Office
Country: United States
Interview Type: In-Person
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: 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.
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.
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: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
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++]);
}
}
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);
}
}
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);
}
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;
}
}
Say the two arrays are: a[] of size n and b[] of size m.
- Anonymous January 24, 2013Declare 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!