Microsoft Interview Question
Senior Software Development EngineersCountry: United States
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.
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)
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
Comments plz!!!
public static void ReplaceArrTogetMaxNum()
{
int[] Arr1 = new int[5];
int[] Arr2 = new int[5];
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(",");
}
Console.Read();
}
public static void ReplaceArrTogetMaxNum()
{
int[] Arr1 = new int[5];
int[] Arr2 = new int[5];
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(",");
}
Console.Read();
}
public static void ReplaceArrTogetMaxNum()
{
int[] Arr1 = new int[5];
int[] Arr2 = new int[5];
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(",");
}
Console.Read();
}
public static void ReplaceArrTogetMaxNum()
{
int[] Arr1 = new int[5];
int[] Arr2 = new int[5];
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(",");
}
Console.Read();
}
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);
}
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
Example please refer to: cpluspluslearning-petert.blogspot.co.uk/2015/10/data-structure-and-algorithm-find.html
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}
Create min heap for array1 and max heap for array2. Poll a1 and a2, keep polling until a1>a2.
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;
}
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;
}
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.
- coolguy September 18, 2015