Interview Question
Country: India
If you are sure it is hard enough to solve in O(n+m) then prove me that we can't solve it. Don't just throw the words.
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;
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
We don't need to make the array -- in fact, because the array will be O(n1*n2) in size, we *cannot* make the sum array if we are to have any hope of even coming close to the level of efficiency the question asks for.
But how would you find the median of the array without making it? That's the question. If you have an algorithm, please state it.
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..:):)
Why not? ALL elements from one array are summed up with ALL elements from another array. That got to keep the overall distribution unchanged. If so, the medians should also remain unchanged. Totally works with a simple example (using sorted arrays for simplicity):
arr1: {2,3,4}
arr2: {5,6,7,8}
Median: 3 + (6+7)/2 = 9.5
After transformation:
7,8,8,9,9,9,10,10,10,11,11,12
Median: (9+10)/2 = 9.5
Is there a counter example where this approach would not work?
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)
No. Yours is about the 4th answer to use this approach. I don't know why everyone thinks this approach will be correct, without attempting to prove or even give an argument for correctness.
Consider {4, 4, 7, 7, 7} and {5, 5, 8, 8, 8}. You get 15 with your approach, but 15 is not the answer.
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.
No. The size of the sum array would be O(n1*n2), and so this solution could not come close to the desired complexity of O(n1 + n2).
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
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
Eugene,
array1.length * array2.length - this is just a multiplication of two numbers and memory created to its size. It does not amount to O(n1*n2) ie O(n^2).
In Java, it takes O(x) time to allocate an array of size x. This is because the array must be initialized to (for object arrays) all null. You are allocating an array of size n1*n2, hence the allocation is O(n1*n2) time.
Don't think that this is just a technicality and that in a language that does not force the initialization of memory (such as C), the algorithm would work better. Yes, in C, it might not take O(n1*n2) just to initialize the array, but VJ then follows up with a loop with a condition like "while(i < result.length){ ... i++ ", which means that the amount of work being done is at least O(result.length), and result.length is n1*n2.
Which company? This is a really hard problem (to get an O(n+m) time algo), and research papers have been written on it.
- Anonymous May 30, 2013Either the interviewer is an idiot, or the question poster is completely clueless.