Amazon Interview Question
Country: -
if the number of elemnts are given like n1 and n2 then we can find the meadian of two soted array just in lg((n1+n2)/2) time that is its easy :)
just use kth element in two soted array as procedure:)
int median(int a[],int n,int b[],int m)
{
int med;
med=(n+m);
if((n+m)%2==0)
{
med=(m+n)/2;
return(kthelement(a,n,b,m,med);
}
else
{med=(m+n)/2;
return((kthelement(a,n,b,m,med)+kthelement(a,n,b,m,med+1))/2);
}
}
// some estra checking add :) i am in hurry :P
int kthelement(int a[],int n,int b[],int m,int k)
{
if(n+m==k)
{
if(a[n]<=b[m])
return a[n];
else
return b[m];
}
else if(a[n]<b[m])
{
int bloc;
bloc=Binarysearch(b,m,a[n]);
if(bloc+n==k)
return a[n];
if(bloc+n>k)
return kthelement(a,n,b,bloc,k);
if(bloc+n<k)
return b[k-bloc-n];}
else
{
int aloc;
aloc=binarysearch(a,n,b[m]);
if(aloc+m==k)
return b[m];
else if(aloc+m>k)
return kthelemnt(a,aloc,b,m);
else
return a[k-aloc-m];
}
}
binary sewarch is something modified versiuon means like we searching the key in array a we find the loctaion whehere the key can fit means next elemnt should be greater than key and the previous element should be smaller or equal to key so just retun that location :)
Its really easy dude, get the last element of the first array and the first element of the second array. Add them up and divide by 2. This will give you the median (Assuming that the sorted arrays are in ascending order).
Example:
array1 = [1,2,3,4,5];
array2 = [10,20,30,40,50];
//Get the index of the last element of the first array and first element of the second array.
int index1 = [array1 count] - 1;
int index2 = [array1 count] - 1;
median = ( array1 [index1] + array2 [index2] ) / 2;
Simplest would be this:
- novice September 12, 2011Given two sorted arrays A and B, having n1 and n2 elements.
1. Find the median in A and B, say m_a and m_b
2. if(m_a > m_b)
select sub-array A[1..n1/2] and B[(n2)/2+1 .. n2]
3. And repeat from step 1. on this sub-array until
3.1) m_a == m_b;
3.2) Elements in array A or B == 1 (or 2), then merge the single(or two) elements with the rest of array, and find the median in the last single array.