CareerCup

Which company? This is a really hard problem (to get an O(n+m) time algo), and research papers have been written on it.

Either the interviewer is an idiot, or the question poster is completely clueless.

we can find median in o(n+m) by first calculating arr1.length()*(a1+a2+a3+a4) this wiil take o(n) and then caluculate arr2.length()*(b1+b2+b3+b4) this will take o(m) time.Then
total time for calculating median will be O(n+m).

n = n1*n2;
mid = (n%2) ? (n+1)/2 : n/2;
k = mid / n1;
s = mid % n1;
median = b(k+1) + a(s+1);
return median;

// O(n*m)
for(i=0;i<n;i++)
 for(j=0;j<n;j++)
   c[i*n+j] =a[i]+b[j];

median = c[c.length/2]

Why we are calculating the arrays, we just need to find which element will seat in middle if we will make such an array which can be done in constant time. Give reasons If you don't agree.

Thanks

Find median of both the arrays using

anandtechblog.blogspot.in/2010/07/median-of-unsorted-array

Then, just sum them up to get the resultant answer..:):)

if sorted, there is heap-like layers in the n*m matrix
a b c d
b c d e
c d e f
d e f g

If the array are sorted then it
Median (R) = Median (A) + Median(B)

If arrays are not sorted then,
Input new element in sorted order and you will found the median... O(n*m)

Can't we just use SELECT(median of medians) algorithm to find median in linear time?
It seems this algorithm followns these steps:

1. Divide the n elements of the input array into groups of 5 elements each
and at most one group made up of the remaining elements.
2. Find the median of each of the groups by first insertion-sorting the ele-
ments of each group (of which there are at most 5) and then picking the median from the sorted list of group elements.
3. Use SELECT recursively to find the median x of the medians found in
step 2. (If there are an even number of medians, then by our convention, x is
the lower median.)
4. Partition the input array around the median-of-medians 'x' using the modified version of PARTITION of the QuickSort algorithm. Let k be one more than the number of elements on the low side of the partition, so that x is the kth smallest element and there are n k elements on the high side of the partition.
5. If k is half of our initial array, then return x. Otherwise, use SELECT recursively to find the ith smallest element on the low side if i < k, or the .i k/th smallest element on the high side if i > k.

The resultant array after merge is of size n1 + n2. Call n1+n2 = m. If m is odd then we have one median which is the floor(m/2)th element. If m is even we have floor(m)th and ceil(m)th elements as medians.

Apply the standard 'SELECT' algorithm that invokes the partition subroutine of quicksort. SELECT computes the median in O(m) time complexity. The merge operation takes O(m) steps. Overall the median can be found in O(m)[= O(n1+n2)] time complexity

for(k=1;k<nm;k++)
{
for(j=1;j<m;j++)
for(i=1;i<n;i++)
{c[k]=a[j]+b[k];
}
}

If we can through modifying the quick sort to find
the (n1 / 2)th number of array1 or array2 (if n1 or n2 is odd number)
the (n1 / 2)th and ((n1 / 2) + 1)th number of array1 or array2 (if n1 or n2 is even number)

Then we can add them to find the median number.

add two array in store in one array.

to find median of this new array in o(n+m), you can use median of medians algorithms

en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

Is this a valid question?
I do not see the significance of adding 2 arrays here.
use the algo medians of medians to find the median of an unsorted array.
en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

public class FindMedianAfterArraySum {

   // this is done in O(n1 + n2)
   public static Integer[] mergeArrays(int[] array1, int[] array2) {

       Integer result[] = new Integer[array1.length * array2.length];


       int a1Index = 0;
       int i=0;
       while(i < result.length) {

           result[i] = array2[i%array2.length] + array1[a1Index];
           ++i;

           if(i%array2.length == 0) {
               a1Index++;
           }
       }

       return result;
   }

   public static void main(String[] args) {
       int[] array1 = new int[]{1,2,3};
       int[] array2 = new int[]{10,20,30};

       Integer[] mergedArray = mergeArrays(array1, array2);
       System.out.println(Arrays.asList(mergedArray));

       // complexity of this is O(nlogn), but there is a solution to find median in linear time using two priority queues
       Arrays.sort(mergedArray);
       System.out.println("Sorted array : " + Arrays.asList(mergedArray));
       System.out.println("Median through sorting : " + mergedArray[mergedArray.length/2]);
   }
}
//***** o(n1+n2) solution