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?

- anand June 11, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Nit May 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- mgatuiet September 21, 2014 | Flag
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

- CUNOMAD August 11, 2009 | Flag Reply
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

- XYZ October 29, 2008 | Flag Reply
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?

- anand June 11, 2009 | Flag Reply
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?

- anand June 11, 2009 | Flag Reply
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

- AK August 09, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sucks

- xyz August 27, 2010 | Flag
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/

@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 August 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@googler- read the question properly then go on commenting. cunomad's approach is correct as the given two array are already sorted.

- @@@@@@@ October 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- @@@@@@@ October 09, 2013 | Flag
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/

@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 August 12, 2009 | Flag Reply
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

- CUNOMAD August 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous August 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous August 14, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

AK: your approach is correct
googler: your link is more helpful to understand AK's approach. thanks to both of you.

- maddy August 30, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is another link that explains all the approaches.

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

- Gaurav September 30, 2009 | Flag
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

- Gaurav September 30, 2009 | Flag Reply
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.

- Anonymous October 08, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Abhishek Shah January 21, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

The link is working. can u please try again?

- Guarav October 31, 2009 | Flag Reply
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;
}

Comments are welcome

- Anonymous June 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ananthakrishnan.s.r June 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- ananthakrishnan.s.r June 16, 2011 | Flag Reply
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";

}

- piyush April 28, 2012 | Flag Reply
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";

}

- piyush April 28, 2012 | Flag Reply
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?

- anand June 11, 2009 | Flag Reply
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?

- anand June 11, 2009 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More