Flipkart interview questions : How to merge two sorted array and final array should be in descending order with O(n) performance.

Lets see the above questions in detail.

There two integer array int a[] = {12,45,67,89,100} and int b[]={1,13,46,65,88,90,101} and resulted array would be int result[]={101,100,90,89,88,67,65,46,45,13,12,1}

And also interviewer wants the solution should be the best among all.


The above question was asked by one of the interviewer from flipkart.  Initially my friend gave lot of solution with less than the performance of O(N^2). But interviewer not convinced with his approach and ask him to do with O(N) performance. He was very strong in logical analytic, so tried and came up with the solution O(N) performance. 

Let's see the solution.

If you look at the above two sorted array, we know either one of the first array element will be placed at the last index of result array, this can be achieved by comparing the element of both the array.
The remaining element array also follow the same logic but it will be placed before the last element of result array.


Algorithm:

Step 1: Initialize two counter variable i and j to traverse a and b array.
Step 2: Initialize k=length of the result array(a.length+b.length)
Step 3: Compare each element of both the array and minimum value will be place at the end of the array and increase (i and j) or decrease(k) the respective counter variables.
Step 4: Repeat the step until the comparison of all the elements of array of a and b.
Step 5: Print the result array.

Code:

public class MergeArraySample {

public static void main(String[] args) {
int a[] = {12,45,67,89,100};    // array 1st
int b[] = {1,13,46,65,88,90,101}; // array 2nd
int len = a.length+b.length;  //  result array
int result [] = new int[len];
int i=0,j=0;  //  intialize counter to traverse 1st and 2nd array
int k= len-1;
while(i<a.length || j<b.length) {
if(i<a.length && j<b.length) {  // compare logic
if(a[i]<b[j]) {
result[k] = a[i];
i++;
} else {
result[k] = b[j];
j++;
}
} else if(i<a.length){
result[k] = a[i];
i++;
} else {
result[k] = b[j];
j++;
}
k--;
}
for(int v: result) {
System.out.print(v+",");
}
}
}

Output:-

101,100,90,89,88,67,65,46,45,13,12,1,

Click to Read more Core Java interview questions and answers

If you like the above solution . Please share this blog