VMWare Inc Amazon Interview Question
Software Engineer / Developers/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
return getMedianRec(ar1, ar2, 0, n-1, n);
}
/* A recursive function to get the median of ar1[] and ar2[]
using binary search */
int getMedianRec(int ar1[], int ar2[], int left, int right, int n)
{
int i, j;
/* We have reached at the end (left or right) of ar1[] */
if(left > right)
return getMedianRec(ar2, ar1, 0, n-1, n);
i = (left + right)/2;
j = n - i - 1; /* Index of ar2[] */
/* Recursion terminates here.*/
if (ar1[i] > ar2[j] && (j == n-1 || ar1[i] <= ar2[j+1]))
{
/*ar1[i] is decided as median 2, now select the median 1
(element just before ar1[i] in merged array) to get the
average of both*/
if (ar2[j] > ar1[i-1] || i == 0)
return (ar1[i] + ar2[j])/2;
else
return (ar1[i] + ar1[i-1])/2;
}
/*Search in left half of ar1[]*/
else if (ar1[i] > ar2[j] && j != n-1 && ar1[i] > ar2[j+1])
return getMedianRec(ar1, ar2, left, i-1, n);
/*Search in right half of ar1[]*/
else /* ar1[i] is smaller than both ar2[j] and ar2[j+1]*/
return getMedianRec(ar1, ar2, i+1, right, n);
}
if m+n is even, median will be (min(A[ptA],B[ptB])+min(A[ptA-1],B[ptB-1]) )/2 see code:
#include<stdio.h>
#define min(a,b) (a>b? b : a)
float median(int a[],int m,int b[],int n){
int count=0,s=(m+n),i=0,j=0;
float mid=0;
while(count<s/2){
if(a[i]<=b[j]){
i++;
count++;
}
else{
j++;
count++;
}
}
if(s%2!=0)
mid= min(a[i],b[j]);
else
mid= ((float)(min(a[i],b[j])+min(a[i-1],b[j-1]))/2);
return mid;
}
void main(){
int a[]={1,2,3};
int b[]={4,5,6,7};
printf("\nmedian is: %f\n",median(a,sizeof(a)/sizeof(int),b,sizeof(b)/sizeof(int)));
}
let A and B be the two sorted arrays.
m = length(A) n=length(B)
have two pointers ptrA and ptrB pointing to the first element of A and B respectively. if A[ptrA]<= B[ptrB], increment ptrA. else increment ptrB. stop when the number of increments is equal to (m+n)/2.
if m+n is odd, the median is the minimum( A[ptrA] and B[ptrB] ). if even take mean of the min number and next greater number.
is this correct?
let A and B be the two sorted arrays.
m = length(A) n=length(B)
have two pointers ptrA and ptrB pointing to the first element of A and B respectively. if A[ptrA]<= B[ptrB], increment ptrA. else increment ptrB. stop when the number of increments is equal to (m+n)/2.
if m+n is odd, the median is the minimum( A[ptrA] and B[ptrB] ). if even take mean of the min number and next greater number.
is this correct?
http://blogs.msdn.com/bali_msft/archive/2008/09/22/select-median-of-two-sorted-array.aspx
@AK
same approach but explained in a more clear/crispy way:
http://batiste.dosimple.ch/blog/2008-04-25-1/
@Cunomad:
your approach is not going to work at all, think of it again! we're not supposed to sort the list and then find the median...then there's not point asking such questions. Also the required time complexity is O(logn). I guess you got the point. Look at the above link, you will better understand the reasoning!
@googler- read the question properly then go on commenting. cunomad's approach is correct as the given two array are already sorted.
@AK
same approach but explained in a more clear/crispy way:
http://batiste.dosimple.ch/blog/2008-04-25-1/
@Cunomad:
your approach is not going to work at all, think of it again! we're not supposed to sort the list and then find the median...then there's not point asking such questions. Also the required time complexity is O(logn). I guess you got the point. Look at the above link, you will better understand the reasoning!
AK: your approach is correct
googler: your link is more helpful to understand AK's approach. thanks to both of you.
Gaurav: the page you mentioned is not availabe any more. can you please recheck and post a valid link. thank you.
Please check my code for kth smallest element
#include<stdio.h>
int findKthsmallest(int a[],int m,int b[],int n,int k)
{
int i=0,j=0,ti=0,tj=0,I=0,J=0,M=m,N=n;
while(1)
{
ti = (int)((double)m/(m+n) * (k-1));
tj = (k-1)-ti;
i = I+ti;
j= J+tj;
//printf(" i=%d j=%d\n",i,j);
if(j>0 && j<N && i<M && a[i]>b[j-1] && a[i]<b[j])
return a[i];
if(i>0 && i<M && j<N && b[j]>a[i-1] && b[j]<a[i])
return b[j];
if(j==0 && i<M && a[i]<b[j])
return a[i];
if(i==0 && j<N && b[j]<a[i])
return b[j];
if(j==N && a[i]>b[j-1])
return a[i];
if(i==M && b[j]>a[i-1])
return b[j];
if(i<M && j<N)
{
if(a[i]<b[j])
{
k=k-ti-1;
m=m-ti-1;
I=i+1;
}
else
{
k=k-tj-1;
n=n-tj-1;
J=j+1;
}
}
else if(i>=M)
{
k=k-tj-1;
n=n-tj-1;
J=j+1;
}
else
{
k=k-ti-1;
m=m-ti-1;
I=i+1;
}
}
}
int main()
{
int a[]={1,2,3};
int b[]={4};
int m=3,n=1,k=3;
printf("%d",findKthsmallest(a,m,b,n,k));
return 0;
}
Comments are welcome
Please check my code
#include<stdio.h>
int findKthsmallest(int a[],int m,int b[],int n,int k)
{
int i=0,j=0,ti=0,tj=0,I=0,J=0,M=m,N=n;
while(1)
{
ti = (int)((double)m/(m+n) * (k-1));
tj = (k-1)-ti;
i = I+ti;
j= J+tj;
//printf(" i=%d j=%d\n",i,j);
if(j>0 && j<N && i<M && a[i]>b[j-1] && a[i]<b[j])
return a[i];
if(i>0 && i<M && j<N && b[j]>a[i-1] && b[j]<a[i])
return b[j];
if(j==0 && i<M && a[i]<b[j])
return a[i];
if(i==0 && j<N && b[j]<a[i])
return b[j];
if(j==N && a[i]>b[j-1])
return a[i];
if(i==M && b[j]>a[i-1])
return b[j];
if(i<M && j<N)
{
if(a[i]<b[j])
{
k=k-ti-1;
m=m-ti-1;
I=i+1;
}
else
{
k=k-tj-1;
n=n-tj-1;
J=j+1;
}
}
else if(i>=M)
{
k=k-tj-1;
n=n-tj-1;
J=j+1;
}
else
{
k=k-ti-1;
m=m-ti-1;
I=i+1;
}
}
}
int main()
{
int a[]={1,2,3};
int b[]={4};
int m=3,n=1,k=3;
printf("%d",findKthsmallest(a,m,b,n,k));
return 0;
}
Comments are welcome
Please check my code
#include<stdio.h>
int findKthsmallest(int a[],int m,int b[],int n,int k)
{
int i=0,j=0,ti=0,tj=0,I=0,J=0,M=m,N=n;
while(1)
{
ti = (int)((double)m/(m+n) * (k-1));
tj = (k-1)-ti;
i = I+ti;
j= J+tj;
//printf(" i=%d j=%d\n",i,j);
if(j>0 && j<N && i<M && a[i]>b[j-1] && a[i]<b[j])
return a[i];
if(i>0 && i<M && j<N && b[j]>a[i-1] && b[j]<a[i])
return b[j];
if(j==0 && i<M && a[i]<b[j])
return a[i];
if(i==0 && j<N && b[j]<a[i])
return b[j];
if(j==N && a[i]>b[j-1])
return a[i];
if(i==M && b[j]>a[i-1])
return b[j];
if(i<M && j<N)
{
if(a[i]<b[j])
{
k=k-ti-1;
m=m-ti-1;
I=i+1;
}
else
{
k=k-tj-1;
n=n-tj-1;
J=j+1;
}
}
else if(i>=M)
{
k=k-tj-1;
n=n-tj-1;
J=j+1;
}
else
{
k=k-ti-1;
m=m-ti-1;
I=i+1;
}
}
}
int main()
{
int a[]={1,2,3};
int b[]={4};
int m=3,n=1,k=3;
printf("%d",findKthsmallest(a,m,b,n,k));
return 0;
}
Comments are welcome
#include <iostream>
using namespace std;
int median(int *arr1,int *arr2,int l1,int u1,int l2,int u2)
{
if(l1==u1 && l2==u2)
if(arr1[l1] < arr2[l2])
return arr1[l1];
else
return arr2[l2];
int mid1,mid2;
mid1=(l1+u1)/2;
mid2=(l2+u2)/2;
if(arr1[mid1] < arr2[mid2] )
{
if(mid1 == u1-1)
mid1=u1;
if(l2==mid2-1)
l2=mid2;
return (median(arr1,arr2,mid1,u1,l2,mid2));
}
else
{
if(mid2 == u2-1)
mid2=u2;
if(l1==mid1-1)
l1=mid1;
return (median(arr1,arr2,l1,mid1,mid2,u2));
}
}
int main()
{
int *arr1,*arr2,size1,size2;
cin>>size1>>size2;
arr1=new int[size1];
arr2=new int[size2];
for(int i=0;i<size1;i++)
cin>>arr1[i];
for(int i=0;i<size2;i++)
cin>>arr2[i];
int med = median(arr1,arr2,0,size1-1,0,size2-1);
cout<<"The mdeian is "<<med<<"\n";
}
#include <iostream>
using namespace std;
int median(int *arr1,int *arr2,int l1,int u1,int l2,int u2)
{
if(l1==u1 && l2==u2)
if(arr1[l1] < arr2[l2])
return arr1[l1];
else
return arr2[l2];
int mid1,mid2;
mid1=(l1+u1)/2;
mid2=(l2+u2)/2;
if(arr1[mid1] < arr2[mid2] )
{
if(mid1 == u1-1)
mid1=u1;
if(l2==mid2-1)
l2=mid2;
return (median(arr1,arr2,mid1,u1,l2,mid2));
}
else
{
if(mid2 == u2-1)
mid2=u2;
if(l1==mid1-1)
l1=mid1;
return (median(arr1,arr2,l1,mid1,mid2,u2));
}
}
int main()
{
int *arr1,*arr2,size1,size2;
cin>>size1>>size2;
arr1=new int[size1];
arr2=new int[size2];
for(int i=0;i<size1;i++)
cin>>arr1[i];
for(int i=0;i<size2;i++)
cin>>arr2[i];
int med = median(arr1,arr2,0,size1-1,0,size2-1);
cout<<"The mdeian is "<<med<<"\n";
}
let A and B be the two sorted arrays.
m = length(A) n=length(B)
have two pointers ptrA and ptrB pointing to the first element of A and B respectively. if A[ptrA]<= B[ptrB], increment ptrA. else increment ptrB. stop when the number of increments is equal to (m+n)/2.
if m+n is odd, the median is the minimum( A[ptrA] and B[ptrB] ). if even take mean of the min number and next greater number.
is this correct?
let A and B be the two sorted arrays.
m = length(A) n=length(B)
have two pointers ptrA and ptrB pointing to the first element of A and B respectively. if A[ptrA]<= B[ptrB], increment ptrA. else increment ptrB. stop when the number of increments is equal to (m+n)/2.
if m+n is odd, the median is the minimum( A[ptrA] and B[ptrB] ). if even take mean of the min number and next greater number.
is this correct?
let A and B be the two sorted arrays.
- anand June 11, 2009m = length(A) n=length(B)
have two pointers ptrA and ptrB pointing to the first element of A and B respectively. if A[ptrA]<= B[ptrB], increment ptrA. else increment ptrB. stop when the number of increments is equal to (m+n)/2.
if m+n is odd, the median is the minimum( A[ptrA] and B[ptrB] ). if even take mean of the min number and next greater number.
is this correct?