## Amazon Interview Question

Country: -

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

Simplest would be this:
Given 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.

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

This is assuming both are of same length.

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

@JP: How can we assume that elements n first list are greater than second one?
i guess we have to merge them & find median on resulting array

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

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 :)

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

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

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

In our example

median = ( 5 + 10 ) / 2
median = 7.5;

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

In our example

median = ( 5 + 10 ) / 2
median = 7.5;

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

LOL.

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

Stupidity at its finest.

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

JP, your solution is stupid and of couse doesn't work... read the problem again...

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.