Microsoft Interview Question for Senior Software Development Engineers


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)));
	}

}

- coolguy September 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- IC October 08, 2015 | Flag
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)

- xyz September 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ritwik_pandey September 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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!!!

- codealtecdown September 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- codealtecdown September 19, 2015 | Flag
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.

- sheiscute September 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();

}

- Pooja Singh September 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
        }

- Pooja SIngh September 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
        }

- pooja Singh September 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
        }

- brikesh987 September 29, 2015 | Flag Reply
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;
}

- howdie October 02, 2015 | Flag Reply
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);
    }

- NL October 06, 2015 | Flag Reply
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

Example please refer to: cpluspluslearning-petert.blogspot.co.uk/2015/10/data-structure-and-algorithm-find.html

- peter tang October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorting requires

nlog(n)

. Can we get to linear runtime?

- unordered_map October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can get it to linear if you use python.

- Varun November 02, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If you use python you can get it to linear

- Varun November 02, 2015 | Flag
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}

- M October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Kaushik B November 09, 2015 | Flag
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.

- prodigy January 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

* until a1<a2.

- prodigy January 14, 2016 | Flag
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.

- kk January 21, 2016 | Flag Reply
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;
}

- Vikram Kumar November 05, 2017 | Flag Reply
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;
}

- Anonymous November 05, 2017 | Flag Reply
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.

- Anonymous September 01, 2018 | 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