## VMWare Inc Amazon Interview Question for Software Engineer / Developers

Comment hidden because of low score. Click to expand.
3
of 3 vote

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?

Comment hidden because of low score. Click to expand.
0

/* 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);
}

Comment hidden because of low score. Click to expand.
0

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)));
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

HOW about merger sort and terminating as soon as we had encountered m+n/2 th element

Comment hidden because of low score. Click to expand.
0
of 0 vote

http://ocw.mit.edu/NR/rdonlyres/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/30C68118-E436-4FE3-8C79-6BAFBB07D935/0/ps9sol.pdf

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0
of 0 vote

http://blogs.msdn.com/bali_msft/archive/2008/09/22/select-median-of-two-sorted-array.aspx

Comment hidden because of low score. Click to expand.
0

sucks

Comment hidden because of low score. Click to expand.
0
of 0 vote

@AK
same approach but explained in a more clear/crispy way:
http://batiste.dosimple.ch/blog/2008-04-25-1/

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!

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

also the complexity should be order O(n) not O(logn)

Comment hidden because of low score. Click to expand.
0
of 0 vote

@AK
same approach but explained in a more clear/crispy way:
http://batiste.dosimple.ch/blog/2008-04-25-1/

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!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Arrays are already sorted we need to find the median.
if arrays are 1,4,5,7 and 2,3,6 then median is 4 which can be easily done by merge sort

Comment hidden because of low score. Click to expand.
0
of 0 vote

the complexity of wot you are saying is o(nlogn)

Comment hidden because of low score. Click to expand.
0

sorry.. not nlogn...
it is n...

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0

Here is another link that explains all the approaches.

http://geeksforgeeks.org/?p=2105

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is another link that explains all the approaches.

http://geeksforgeeks.org/?p=2105

Comment hidden because of low score. Click to expand.
0
of 0 vote

Gaurav: the page you mentioned is not availabe any more. can you please recheck and post a valid link. thank you.

Comment hidden because of low score. Click to expand.
0

Go to geeksforgeeks.org and type "median" in search text box

Comment hidden because of low score. Click to expand.
0
of 0 vote

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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";

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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";

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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?

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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?

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.