## Microsoft Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Written Test

Comment hidden because of low score. Click to expand.
2
of 4 vote

I probably would have merged them all into a new array. Just have 3 indexes pointing to the start of each array. Take the smallest value referenced by the indexes, append to the new array, and then increment that index. Do this until each index equals the len of it's corresponding array. Return the newly created array.

If you follow the assumptions you made where there is enough room in array1, then you can use a similar algorithm except go from the end of the arrays.

``````i1 = end of array1 (last number in array, not the size of array)
i2 = end of array2
i3 = end of array3
insertIndex = len(array1) - 1

while (i1, i2, i3 >= 0)
if i1 largest
a1[insertIndex--] = array1[i1--]
else if i2 largest
a1[insertIndex--] = array2[i2--]
else if i3 largest
a1[insertIndex--] = array3[i3--]``````

That's the basics of it, there are boundary cases you have to check like when the indexes reach -1.

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

if there is a better or faster way to do this with all three arrays at the same time (instead of merging two at a time and then use that result with the third array), please advise. I'm very much interested to learn.

Comment hidden because of low score. Click to expand.
0

public static void main(String[] args) {
int a[] = {0,3,6,9,12,15};
int b[] = {2,4,6,8,10};
int c[] = {1,2,3,4,5,6};
//Create a new array that is supposed to hold the final output of sorted values across the 3 arrays.
int d[] = new int[a.length+b.length+c.length];
//Copy the first array as it is (this can be any array)
for (int i=0;i<a.length;i++) {
d[i] = a[i];
}
//For the remaining two arrays, add element from each of the two arrays into the final array via insertion sort.
merge(b,d,a.length);
merge(c,d,a.length+b.length);
for (int i=0;i<d.length;i++) {
System.out.print(d[i]+" ");
}
}
//Adds the elements from fromArray into the final toArray via insertion sort.
public static void merge(int fromArray[], int toArray[], int currentIndex) {
int val = 0;
for (int i=0;i<fromArray.length;i++) {
val = fromArray[i];
int j = currentIndex;
while (j > 0 && toArray[j-1] > val) {
toArray[j] = toArray[j-1];
j--;
}
toArray[j] = val;
currentIndex++;
}
}

Comment hidden because of low score. Click to expand.
0

yes there is i believe,
the trick is to maintain three pointers running from the last of each array, compare the three values and put the largest at the last index of the resultant array (assuming first array has the extra space). decrement it and keep repeating this until any of the arrays exhaust.
One thing to note here is that after above step need to check if the indexes have exhausted or not and need to iterate them separately if required.
Complexity: O(m+n+p) (where m,n,p are the length's of each array respectively)

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

This was my code. There were some syntax errors which I corrected in this code:

``````public static int[] ThreeMergeSortedArrays(int[] a, int[] b, int[] c)
{
int[] res = TwoMergeSortedArrays(a, b);
res = TwoMergeSortedArrays(res, c);
return res;
}

public static int[] TwoMergeSortedArrays(int[] a1, int[] a2)
{
//this is under the assumption that array a1 has space to fit in entire array a2. No error conditions have been checked.
int i;
int m = a2.Length - 1;
int n = a1.Length - 1 - a2.Length;
if (a2[0] > a1[n])
{
for (i = 0; i < a2.Length; i++)
a1[i + 1 + n] = a2[i];
return a1;
}
for (int k = 0; m >= 0 && n >= 0; k++)
{
if (a1[n] > a2[m])
{
a1[a1.Length - 1 - k] = a1[n];
n--;
}
else
{
a1[a1.Length - 1 - k] = a2[m];
m--;
}
}
if (n < 0 && m >= 0)
{
while (m >= 0)
{
a1[m] = a2[m];
m--;
}
}
return a1;``````

}

Comment hidden because of low score. Click to expand.
0
of 6 vote

Create an array equal to the length of the three arrays.
Fill the array from the last. Since the array is already sorted, starting to fill from the last will help.

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

what are the other question in the test??

Comment hidden because of low score. Click to expand.
0

2nd question was a pointer question... was asked to remove bugs in a pointer code..dont remember exactly...
3rd question was asked to reverse order of vowels in a string.. for e.g.
wOndErfUl -> wUndErfOl.. another e.g. Cater -> Cetar. another e.g.
This is not that -> Thas os nit thit

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

Was the merged array supposed to maintain all values in sorted order?

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

public static void main(String[] args) {
int a[] = {0,3,6,9,12,15};
int b[] = {2,4,6,8,10};
int c[] = {1,2,3,4,5,6};
//Create a new array that is supposed to hold the final output of sorted values across the 3 arrays.
int d[] = new int[a.length+b.length+c.length];

//Copy the first array as it is (this can be any array)
for (int i=0;i<a.length;i++) {
d[i] = a[i];
}
//For the remaining two arrays, add element from each of the two arrays into the final array via insertion sort.
merge(b,d,a.length);
merge(c,d,a.length+b.length);

for (int i=0;i<d.length;i++) {
System.out.print(d[i]+" ");
}

}

//Adds the elements from fromArray into the final toArray via insertion sort.
public static void merge(int fromArray[], int toArray[], int currentIndex) {
int val = 0;
for (int i=0;i<fromArray.length;i++) {
val = fromArray[i];
int j = currentIndex;
while (j > 0 && toArray[j-1] > val) {
toArray[j] = toArray[j-1];
j--;
}
toArray[j] = val;
currentIndex++;
}
}

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

public static void main(String[] args) {
int a[] = {0,3,6,9,12,15};
int b[] = {2,4,6,8,10};
int c[] = {1,2,3,4,5,6};
//Create a new array that is supposed to hold the final output of sorted values across the 3 arrays.
int d[] = new int[a.length+b.length+c.length];
//Copy the first array as it is (this can be any array)
for (int i=0;i<a.length;i++) {
d[i] = a[i];
}
//For the remaining two arrays, add element from each of the two arrays into the final array via insertion sort.
merge(b,d,a.length);
merge(c,d,a.length+b.length);
for (int i=0;i<d.length;i++) {
System.out.print(d[i]+" ");
}
}
//Adds the elements from fromArray into the final toArray via insertion sort.
public static void merge(int fromArray[], int toArray[], int currentIndex) {
int val = 0;
for (int i=0;i<fromArray.length;i++) {
val = fromArray[i];
int j = currentIndex;
while (j > 0 && toArray[j-1] > val) {
toArray[j] = toArray[j-1];
j--;
}
toArray[j] = val;
currentIndex++;
}
}

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

public static void main(String[] args) {
int a[] = {0,3,6,9,12,15};
int b[] = {2,4,6,8,10};
int c[] = {1,2,3,4,5,6};
//Create a new array that is supposed to hold the final output of sorted values across the 3 arrays.
int d[] = new int[a.length+b.length+c.length];
//Copy the first array as it is (this can be any array)
for (int i=0;i<a.length;i++) {
d[i] = a[i];
}
//For the remaining two arrays, add element from each of the two arrays into the final array via insertion sort.
merge(b,d,a.length);
merge(c,d,a.length+b.length);
for (int i=0;i<d.length;i++) {
System.out.print(d[i]+" ");
}
}
//Adds the elements from fromArray into the final toArray via insertion sort.
public static void merge(int fromArray[], int toArray[], int currentIndex) {
int val = 0;
for (int i=0;i<fromArray.length;i++) {
val = fromArray[i];
int j = currentIndex;
while (j > 0 && toArray[j-1] > val) {
toArray[j] = toArray[j-1];
j--;
}
toArray[j] = val;
currentIndex++;
}
}

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

public static void main(String[] args) {
int a[] = {0,3,6,9,12,15};
int b[] = {2,4,6,8,10};
int c[] = {1,2,3,4,5,6};
//Create a new array that is supposed to hold the final output of sorted values across the 3 arrays.
int d[] = new int[a.length+b.length+c.length];
//Copy the first array as it is (this can be any array)
for (int i=0;i<a.length;i++) {
d[i] = a[i];
}
//For the remaining two arrays, add element from each of the two arrays into the final array via insertion sort.
merge(b,d,a.length);
merge(c,d,a.length+b.length);
for (int i=0;i<d.length;i++) {
System.out.print(d[i]+" ");
}
}
//Adds the elements from fromArray into the final toArray via insertion sort.
public static void merge(int fromArray[], int toArray[], int currentIndex) {
int val = 0;
for (int i=0;i<fromArray.length;i++) {
val = fromArray[i];
int j = currentIndex;
while (j > 0 && toArray[j-1] > val) {
toArray[j] = toArray[j-1];
j--;
}
toArray[j] = val;
currentIndex++;
}
}

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

``````public static int[] merge2(int[] a1, int[] a2){
int[] mergedArr = new int[(a1.length + a2.length)];
int i1 = 0, i2 = 0, t = 0;
int tota = a1.length + a2.length;
while(t < tota){
if (i1 == a1.length){
while(i2 < a2.length){
mergedArr[t++] = a2[i2++];
}
break;
}
else if (i2 == a2.length){
while(i1 < a1.length){
mergedArr[t++] = a1[i1++];
}
break;
}
else if (a1[i1] < a2[i2]){
mergedArr[t++] = a1[i1++];
}
else {
mergedArr[t++] = a2[i2++];
}
}
return mergedArr;
}

public static int[] merge3 (int[] a1, int[] a2, int[] a3){
int[] mergedArr = new int[(a1.length + a2.length + a3.length)];

int temp1[] = merge2(a1,a2);
mergedArr = merge2(temp1,a3);

return mergedArr;
}``````

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

``````std::vector<int> Merge3(std::vector<int>& v1, std::vector<int>& v2, std::vector<int>& v3)
{
std::vector<int> rval;
std::vector<int>::iterator i1 = v1.begin(), i2 = v2.begin(), i3 = v3.begin();

while ((i1 != v1.end()) || (i2 != v2.end()) || (i3 != v3.end()))
{
std::vector<int>::iterator* lowest = NULL;
if (i1 != v1.end())
lowest = &i1;
if (i2 != v2.end())
lowest = lowest ? (*i2 < **lowest ? &i2 : lowest) : &i2;
if (i3 != v3.end())
lowest = lowest ? (*i3 < **lowest ? &i3 : lowest) : &i3;
rval.push_back(*(*lowest)++);
}

return rval;
}``````

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

Based on suggestions from alregith and adam - here is the code to process three sorted arrays from the end:

``````public int[] ThreeMergeSortedArrays(int[] a1, int[] a2, int[] a3)
{
int a1L = a1.Length-1,
a2L = a2.Length-1,
a3L = a3.Length-1;

int[] result = new int[a1.Length + a2.Length + a3.Length];
int resL = result.Length-1;

while (a1L >= 0 && a2L >= 0 && a3L >= 0)
{
if (a1[a1L] >= a2[a2L] && a1[a1L] >= a3[a3L])
result[resL--] = a1[a1L--];

else if (a2[a2L] >= a1[a1L] && a2[a2L] >= a3[a3L])
result[resL--] = a2[a2L--];

else
result[resL--] = a3[a3L--];
}

if (a1L < 0)
{
while (a2L >= 0 && a3L >= 0)
{
if (a2[a2L] >= a3[a3L])
result[resL--] = a2[a2L--];
else
result[resL--] = a3[a3L--];
}
if (a2L < 0)
result[resL] = a3[a3L];
else
result[resL] = a2[a2L];
}
else if (a2L < 0)
{
while (a1L >= 0 && a3L >= 0)
{
if (a1[a1L] >= a3[a3L])
result[resL--] = a1[a1L--];
else
result[resL--] = a3[a3L--];
}
if (a1L < 0)
result[resL] = a3[a3L];
else
result[resL] = a1[a1L];
}
else
{
while (a1L >= 0 && a2L >= 0)
{
if (a1[a1L] >= a2[a2L])
result[resL--] = a1[a1L--];
else
result[resL--] = a2[a2L--];
}
if (a1L < 0)
result[resL] = a2[a2L];
else
result[resL] = a1[a1L];
}
return result;``````

}

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

Hello,

Is think that approach to this problem should not be as complex as it sounds.

Generally, I see this problem is a matter of inserting all values from all arrays in Binary Search Tree and performing in-order traversal to add all items in newly allocated array.

Time complexity for this is N log N (to fill binary search tree) and N operations to traverse tree, thus making it O(N log N) operation.

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

``````#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

void Merge(vector<int> &v1, vector<int> &v2, vector<int> &v3, vector<int> &output) {

int tsize = v1.size() + v2.size() + v3.size();
output.resize(tsize);

vector<int> indices;
indices.push_back(v1.size() - 1);
indices.push_back(v2.size() - 1);
indices.push_back(v3.size() - 1);

int oi = tsize - 1;
while(indices[0] >= 0 || indices[1] >= 0 || indices[2] >= 0) {
int mx = -1;
int i = -1;
if(indices[0] >= 0) {
i = 0;
mx = v1[indices[i]];
}
if((indices[1] >= 0) && (mx < v2[indices[1]])) {
i = 1;
mx = v2[indices[i]];
}
if((indices[2] >= 0) && (mx < v3[indices[2]])) {
i = 2;
mx = v3[indices[i]];
}
output[oi--] = mx;
//cout << "mx = " << mx << endl;
indices[i]--;
}

}

int main() {
vector<int> v1 = {3, 6, 9, 10, 14, 16, 18, 29};
vector<int> v2 = {1, 5, 7, 11, 14, 19, 23};
vector<int> v3 = {2, 3, 4, 5};
vector<int> output;
Merge(v1, v2, v3, output);
for(auto i : output)
cout << i <<  " ";
return 0;
}``````

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

Were they just expecting a 2 dimensional array?

``````int[][] newArray = {arr1, arr2, arr3};
return newArray;``````

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

``````static int[] MergeArrays(int[] array1, int[] array2)
{
int NewLength = array1.Length + array2.Length;
int[] result = new int[NewLength];

int last2 = 0;
for (int i = 0; i < array1.Length; i++)
{
for (int j = last2; j < array2.Length; j++)
{
if (array1[i] > array2[j])
{
result[last2 + i] = array2[j];
last2++;
}
else
{
result[last2 + i] = array1[i];
break;
}
}
if (last2 == array2.Length) result[i + last2] = array1[i];
}

for (int j = last2; j < array2.Length; j++)
{
result[j+array1.Length] = array2[j];
}

return result;
}
static void OutPutArray(int[] array)
{
System.Console.WriteLine("");
for (int i=0; i < array.Length;i++)
{
System.Console.Write(array[i]+",");
}
}
static void Main(string[] args)
{
int[] array1 = {1,5,7,9};
int[] array2 = {3,6,10,17,25};
int[] array3 = { 8, 13, 15, 20 };
int[] result;

OutPutArray(array1);
OutPutArray(array2);
OutPutArray(array3);
result = MergeArrays(array1,array2);
OutPutArray(result);
result = MergeArrays(result, array3);
OutPutArray(result);
}``````

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

``````public int[] MergedArray(int[] a1, int[] a2, int[] a3)
{

for (int i = 0; i < a1.Length; i++)
{

newNode.data = a1[i];

if (root == null)
{
root = newNode;
current = root;
}
else
{
current.next = newNode;
current = current.next;
}
}

List<int> result = new List<int>();

while (root != null)
{
root = root.next;
}

root = null;

return result.ToArray();
}

{
int count = 0;

while (root != null && count < array.Length)
{
newNode.data = array[count];

if (root.next == null)
{
root.next = newNode;
count += 1;

}
else if (root.data < newNode.data && root.next.data > newNode.data)
{
newNode.next = root.next;
root.next = newNode;
count += 1;
}

root = root.next;
}

root = current;

return root;``````

}

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

C++ implementation: create a third array iterate over each array and add the smallest element to the new array till the arrays are empty.

``````#include<iostream>
using namespace std;

class Merge{
public:
void mergeArrays(int *a, int *b, int *c, int as, int bs, int cs, int *final){
int k=0;
int j=0;
int l=0;
for (int i=0; i<(as+bs+cs); i++){
if(j<as && k<bs && l<cs){
if(a[j]<=b[k] && a[j]<=c[l]){
final[i] = a[j];
j++;
}
else if(b[k]<=a[j] && b[k]<=c[l]){
final[i] = b[k];
k++;
}
else if(c[l]<=a[j] && c[l]<=b[k]){
final[i] = c[l];
l++;
}
}
else if(j<as && k<bs){
if(a[j]<=b[k]){
final[i] = a[j];
j++;
}
else {
final[i] = b[k];
k++;
}
}
else if(j<as && l<cs){
if(a[j]<=c[l]){
final[i] = a[j];
j++;
}
else {
final[i] = c[l];
l++;
}
}
else if(k<bs && l<cs){
if(b[k]<=c[l]){
final[i] = b[k];
k++;
}
else {
final[i] = c[l];
l++;
}
}
else if(j<as){
final[i] = a[j];
j++;
}
else if(k<bs){
final[i] = b[k];
k++;
}
else if(l<cs){
final[i] = c[l];
l++;
}
}
}
};
int main(){
int a[] = {1,5,8};
int b[] = {2,6,7};
int c[] = {0,8,9,10};
int final[10];
int *ptra = a;
int *ptrb = b;
int *ptrc = c;
int *ptr = final;

Merge *merge = new Merge();
merge->mergeArrays(ptra,ptrb,ptrc,3,3,4,ptr);
for(int i=0;i<10;i++)
cout<<ptr[i];
cout<<endl;
system("pause");
}``````

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

O(n) solution in C:

``````#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
int* d;
void merge_arr(int a[],int b[],int c[],int a_size,int b_size,int c_size) {
int small=INT_MAX;
int i,j,k,l;
i=j=k=l=0;
int* p=d;
while(l<a_size+b_size+c_size) {
small=INT_MAX;
if(i!=a_size && a[i]<small)
small=a[i];
if(j!=b_size && b[j]<small)
small=b[j];
if(k!=c_size && c[k]<small)
small=c[k];
if(small==a[i]) i++;
if(small==b[j]) j++;
if(small==c[k]) k++;
d[l++]=small;
}
}
int main() {
int a[]={50,51,52};
int b[]={23,43,76,81};
int c[]={31,55};
int i;
int a_size=sizeof(a)/sizeof(a[0]);
int b_size=sizeof(b)/sizeof(b[0]);
int c_size=sizeof(c)/sizeof(c[0]);
d=(int*)malloc(a_size+b_size+c_size);
merge_arr(a,b,c,a_size,b_size,c_size);
for(i=0;i<(a_size+b_size+c_size);i++)
printf("%d\n",d[i]);
}``````

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

O(n) solution in C:

``````#include<limits.h>
#include<stdio.h>
#include<stdlib.h>
int* d;
void merge_arr(int a[],int b[],int c[],int a_size,int b_size,int c_size) {
int small=INT_MAX;
int i,j,k,l;
i=j=k=l=0;
int* p=d;
while(l<a_size+b_size+c_size) {
small=INT_MAX;
if(i!=a_size && a[i]<small)
small=a[i];
if(j!=b_size && b[j]<small)
small=b[j];
if(k!=c_size && c[k]<small)
small=c[k];
if(small==a[i]) i++;
if(small==b[j]) j++;
if(small==c[k]) k++;
d[l++]=small;
}
}
int main() {
int a[]={50,51,52};
int b[]={23,43,76,81};
int c[]={31,55};
int i;
int a_size=sizeof(a)/sizeof(a[0]);
int b_size=sizeof(b)/sizeof(b[0]);
int c_size=sizeof(c)/sizeof(c[0]);
d=(int*)malloc(a_size+b_size+c_size);
merge_arr(a,b,c,a_size,b_size,c_size);
for(i=0;i<(a_size+b_size+c_size);i++)
printf("%d\n",d[i]);
}``````

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.

### 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.