## Microsoft Interview Question for Senior Software Development Engineers

• 2

Country: United States

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

``````import java.util.Arrays;

public class MaxArray{

// T(n) = O(N+1 * logN)
public int [] maximizeArray(int [] arr1, int [] arr2){
if(arr1 == null || arr2 == null || arr1.length == 0){
return null;
}
Arrays.sort(arr2);

int index2 = arr2.length - 1;
for(int i = 0; i < arr1.length; i++){
if(index2 >= 0 && arr1[i] < arr2[index2]){
arr1[i] = arr2[index2];
index2--;
}
}
return arr1;
}

public static void main(String[] args) {
MaxArray m = new MaxArray();
int [] arr1 = { 3, 1, 4, 5, 6};
int [] arr2 = { 2, 9 };
System.out.println(Arrays.toString(m.maximizeArray(arr1, arr2)));
}

}``````

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

Curious about some performance considerations here
1. If arr2 is significantly larger than arr1, then is it worth sorting arr2?
for example if arr1 size is 5 and arr2 size is 1000. We will need only the largest 5 from arr2. To get the 5 largest is it worth sorting 1000 entries in the array?

2. What would be a good formula to determine 'significantly larger'?
Is it arr2.length > 10* arr1.length
or something like
log arr2.length > arr1.length

If this performance question is valid then maybe we can have a 2 part hybrid solution where we sort arr2 if arr2 is not significantly larger than arr1 and some other solution for significantly larger scenario. Well... depends on the use cases.

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

Author it should not be {9,5,4,5,6} ?
If it's answer is as above then you can solve as.
1. Sort 2nd Array in descending order
2.

``````j = 0;
for( i = 0;i < A.size();i++){
if ( A[i] < B[j] ){
A[i] = B[j];
j++;
}
}``````

3. O(N log N)

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

Yes. You are right. That was a typo. Sorry for that.

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

Considering following arr & rep
arr={3,1,4,5,6}
rep={1,9,5,2,3}
and assumption that output should be
res={9,1,4,5,6}

Approach:
1. Find the maximum number from rep, max2
2. Traverse arr from right to left, and find a digit which is less than max2
3. If found, replace and return arr
4. If not found, replace the last digit(right most) of arr with max2. Assumption here is that we have to replace one element even if it is bringing down the number

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

sorry for the typo in the second step above.
2. Traverse arr from left to right, and find a digit which is less than max2

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

guys: if we are not using 3 rd array for storing final elements, then we might require a full length push in case you need to pick elements from rep array. SOmething like this:

n^2 could be the complexity then.

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

``````public static void ReplaceArrTogetMaxNum()
{
int[] Arr1 = new int;
int[] Arr2 = new int;
Random rdm = new Random();
//create random array
for (int i = 0; i < 5; i++)
{
Arr1[i]= rdm.Next(0,10);
Arr2[i] = rdm.Next(0, 10);
}

//print array
Console.WriteLine("Input");

Console.Write("Arr1: [");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr1[i].ToString());
if(i==4)
Console.WriteLine("]");
else
Console.Write(",");

}
Console.Write("Arr2: ");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr2[i].ToString());
if (i == 4)
Console.WriteLine("]");
else
Console.Write(",");

}
//srt desc array 2
for (int i = 0; i < Arr2.Length;i++ )
{
for (int j = i + 1; j < Arr2.Length; j++)
{
int left = int.Parse(Arr2[i].ToString());
int right = int.Parse(Arr2[j].ToString());
//int temp = 0;

if (left < right)
{
//temp = right;
Arr2[j] = Arr2[i];
Arr2[i] = right;

}
}
}
//print sorted array
Console.Write("Arr2:sorted desc ");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr2[i].ToString());
if (i == 4)
Console.WriteLine("]");
else
Console.Write(",");

}
//replace arrray 1 if corresponding array 2 element is greater
for (int i = 0; i < Arr1.Length; i++)
{
if (int.Parse(Arr1[i].ToString()) < int.Parse(Arr2[i].ToString()))
{
Arr1[i] = Arr2[i];
}
}
//print max number
Console.Write("Arr1:max number ");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr1[i].ToString());
if (i == 4)
Console.WriteLine("]");
else
Console.Write(",");

}

}

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

``````public static void ReplaceArrTogetMaxNum()
{
int[] Arr1 = new int;
int[] Arr2 = new int;
Random rdm = new Random();
//create random array
for (int i = 0; i < 5; i++)
{
Arr1[i]= rdm.Next(0,10);
Arr2[i] = rdm.Next(0, 10);
}

//print array
Console.WriteLine("Input");

Console.Write("Arr1: [");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr1[i].ToString());
if(i==4)
Console.WriteLine("]");
else
Console.Write(",");

}
Console.Write("Arr2: ");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr2[i].ToString());
if (i == 4)
Console.WriteLine("]");
else
Console.Write(",");

}
//srt desc array 2
for (int i = 0; i < Arr2.Length;i++ )
{
for (int j = i + 1; j < Arr2.Length; j++)
{
int left = int.Parse(Arr2[i].ToString());
int right = int.Parse(Arr2[j].ToString());
//int temp = 0;

if (left < right)
{
//temp = right;
Arr2[j] = Arr2[i];
Arr2[i] = right;

}
}
}
//print sorted array
Console.Write("Arr2:sorted desc ");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr2[i].ToString());
if (i == 4)
Console.WriteLine("]");
else
Console.Write(",");

}
//replace arrray 1 if corresponding array 2 element is greater
for (int i = 0; i < Arr1.Length; i++)
{
if (int.Parse(Arr1[i].ToString()) < int.Parse(Arr2[i].ToString()))
{
Arr1[i] = Arr2[i];
}
}
//print max number
Console.Write("Arr1:max number ");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr1[i].ToString());
if (i == 4)
Console.WriteLine("]");
else
Console.Write(",");

}

}``````

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

``````public static void ReplaceArrTogetMaxNum()
{
int[] Arr1 = new int;
int[] Arr2 = new int;
Random rdm = new Random();
//create random array
for (int i = 0; i < 5; i++)
{
Arr1[i]= rdm.Next(0,10);
Arr2[i] = rdm.Next(0, 10);
}

//print array
Console.WriteLine("Input");

Console.Write("Arr1: [");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr1[i].ToString());
if(i==4)
Console.WriteLine("]");
else
Console.Write(",");

}
Console.Write("Arr2: ");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr2[i].ToString());
if (i == 4)
Console.WriteLine("]");
else
Console.Write(",");

}
//srt desc array 2
for (int i = 0; i < Arr2.Length;i++ )
{
for (int j = i + 1; j < Arr2.Length; j++)
{
int left = int.Parse(Arr2[i].ToString());
int right = int.Parse(Arr2[j].ToString());
//int temp = 0;

if (left < right)
{
//temp = right;
Arr2[j] = Arr2[i];
Arr2[i] = right;

}
}
}
//print sorted array
Console.Write("Arr2:sorted desc ");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr2[i].ToString());
if (i == 4)
Console.WriteLine("]");
else
Console.Write(",");

}
//replace arrray 1 if corresponding array 2 element is greater
for (int i = 0; i < Arr1.Length; i++)
{
if (int.Parse(Arr1[i].ToString()) < int.Parse(Arr2[i].ToString()))
{
Arr1[i] = Arr2[i];
}
}
//print max number
Console.Write("Arr1:max number ");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr1[i].ToString());
if (i == 4)
Console.WriteLine("]");
else
Console.Write(",");

}

}``````

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

``````public static void ReplaceArrTogetMaxNum()
{
int[] Arr1 = new int;
int[] Arr2 = new int;
Random rdm = new Random();
//create random array
for (int i = 0; i < 5; i++)
{
Arr1[i]= rdm.Next(0,10);
Arr2[i] = rdm.Next(0, 10);
}

//print array
Console.WriteLine("Input");

Console.Write("Arr1: [");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr1[i].ToString());
if(i==4)
Console.WriteLine("]");
else
Console.Write(",");

}
Console.Write("Arr2: ");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr2[i].ToString());
if (i == 4)
Console.WriteLine("]");
else
Console.Write(",");

}
//srt desc array 2
for (int i = 0; i < Arr2.Length;i++ )
{
for (int j = i + 1; j < Arr2.Length; j++)
{
int left = int.Parse(Arr2[i].ToString());
int right = int.Parse(Arr2[j].ToString());
//int temp = 0;

if (left < right)
{
//temp = right;
Arr2[j] = Arr2[i];
Arr2[i] = right;

}
}
}
//print sorted array
Console.Write("Arr2:sorted desc ");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr2[i].ToString());
if (i == 4)
Console.WriteLine("]");
else
Console.Write(",");

}
//replace arrray 1 if corresponding array 2 element is greater
for (int i = 0; i < Arr1.Length; i++)
{
if (int.Parse(Arr1[i].ToString()) < int.Parse(Arr2[i].ToString()))
{
Arr1[i] = Arr2[i];
}
}
//print max number
Console.Write("Arr1:max number ");
for (int i = 0; i < 5; i++)
{
Console.Write(Arr1[i].ToString());
if (i == 4)
Console.WriteLine("]");
else
Console.Write(",");

}

}``````

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

``````public int[] maximizeNum(int[] arr, int[] rep) {

if(arr == null || rep == null)
return null;

Arrays.sort(rep);
int arrLen = arr.length;
int currRepIdx = 0;

for(int i = 0; i < arrLen; i++) {
if(arr[i] < rep[currRepIdx]) {
arr[i] = rep[currRepIdx++];
}
}
return arr;
}``````

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

Java approach

``````public static void main(String[] args) {
Integer[] arr = {3, 1, 4, 5, 6};
Integer[] rep = {1, 9, 5, 2, 3};
maximize(arr, rep);

}

private static void maximize(Integer[] arr, Integer[] rep) {
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1 > o2 ? -1 : 1;
}
};
Arrays.sort(rep, comparator);
int repIndex = 0;
for(int i = 0; i < arr.length; i++){
if(arr[i] < rep[repIndex]){
arr[i] = rep[repIndex];
repIndex++;
}
}
for(int i : arr)
System.out.println(i);
}``````

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

``````Pseudo code:
1. Sort rep in the descending order as sortedRep
2. Two pointers points to arr and sortedRep as arrPtr and repPtr
3. Compare the value arrPtr points to with the value repPtr points to
* If less, replace the value arrPtr points to with the value repPtr points to
And move arrPtr and repPtr forward by 1
* If not less, move attPtr forward by 1
4. Repeat Step 3 until either pointer reaches the end``````

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

Sorting requires

``nlog(n)``

. Can we get to linear runtime?

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

You can get it to linear if you use python.

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

If you use python you can get it to linear

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

Above solutions will fail in case input is like this:
ARR = {4,5,6,3,1,}
REP = {1,9,5,2,3}

If we traverse arr from left to right and replace the max from Rep.
Result would be {9,5,6,5,3}
But it should be {4,5,6,5,9}

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

Why do you think the answer expected is 4,5,6,5,9 ? As per question the maximum number formed by replacing the digits (one digit only once) is 95653 only. Please explain.

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

Create min heap for array1 and max heap for array2. Poll a1 and a2, keep polling until a1>a2.

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

* until a1<a2.

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

you can do without sorting which result N x K performance.
compare and replace with biggest diff.

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

``````int * MaximizingNumber(int *arr,int n,int *rep,int m)
{
if(arr==NULL)
return NULL;
if(rep==NULL)
return arr;
sort(rep, rep+m, greater<int>());
for(int i=0;i<m;i++)
{
cout<<rep[i]<<' ';

}
cout<<'\n';
int k=0;
for(int i=0;i<n;i++)
{
if(k<m)
for(int j=k;j<m;j++)
{
if(arr[i]<rep[j]){
arr[i]=rep[j];
k++;
break;
}
}
else
break;
}
return arr;
}``````

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

int * MaximizingNumber(int *arr,int n,int *rep,int m)
{
if(arr==NULL)
return NULL;
if(rep==NULL)
return arr;
sort(rep, rep+m, greater<int>());
for(int i=0;i<m;i++)
{
cout<<rep[i]<<' ';

}
cout<<'\n';
int k=0;
for(int i=0;i<n;i++)
{
if(k<m)
for(int j=k;j<m;j++)
{
if(arr[i]<rep[j]){
arr[i]=rep[j];
k++;
break;
}
}
else
break;
}
return arr;
}

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

This can be done in O(n).
The arrays will have only numbers which will be from 0-9. Create a hash (arr) of size 10 containing count of each digit.

Start iterating second array and search for a digit lesser than this (constant operation as hash is of size 10 always)
If the count is >0 there is a small digit we can replace with this large digit.
Reduce count and replace the digit with this new digit.

Optimising replacement-
Create another hash which will be a copy of first hash initially abd will finally contain the answer.
Whenever you find a smaller digit in first hash idecrease count of first digit in answer hash and increase count of this digit in second hash.
Finally the second hash (answer hash) will contain all the digits which will go in final answer.
Iterate over this hash and put all the digits per their count in first array.

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.