## Interview Question

Country: United States

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

``````double findKth(int A[], int m, int B[], int n, int k) {

if (m > n) return findKth(B, n, A, m, k);
if (m == 0) return B[k - 1];
if (k == 1) return min(A[0], B[0]);

int aMid = min(k / 2, m);
int bMid = k - aMid;

if (A[aMid - 1] <= B[bMid - 1]) {
return findKth(A + aMid, m - aMid, B, n, k - aMid);
}
return findKth(A, m, B + bMid, n - bMid, k - bMid);
}

double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = m + n;
if(total & 1) return findKth(A, m, B, n, total / 2 + 1);
return (findKth(A, m, B, n, total / 2);
}``````

The overall time complexity is

``O(log(n + n))``

which is

``O(logn)``

.

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

``````public static int findLowerMedian(int[] a, int[]b){
int atry, btry;
atry = findLowerMedianIndex(a, b, 0, a.length);
if(atry != -1){
return a[atry];
}
else{
return b[findLowerMedianIndex(b, a, 0, b.length)];
}
}

public static int findLowerMedianIndex(int[] a, int[] b, int start, int end){
if(start == end){
if(lowerMedianProximity(a, b, start) == 0) return start;
else return -1;
}
else{
int m = (start + end)/2;
int prox = lowerMedianProximity(a, b, m);
if(prox == 0) return m;
else if(prox == -1) return findLowerMedianIndex(a, b, m+1, end);
else return findLowerMedianIndex(a, b, start, m);
}
}

public static int lowerMedianProximity(int[] a, int[] b, int adex){
int firstGreater = a.length - 1 - adex;
else if(b[firstGreater] > a[adex]) return -1;
else return 1;
}``````

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

actually, this is slightly cleaner:

``````public static int findLowerMedian(int[] a, int[]b){
int atry, btry;
atry = findLowerMedianIndex(a, b, 0, a.length-1);
if(atry != -1){
return a[atry];
}
else{
return b[findLowerMedianIndex(b, a, 0, b.length-1)];
}
}

public static int findLowerMedianIndex(int[] a, int[] b, int first, int last){
if(first > last){
return -1;
}
else{
int m = (first + last)/2;
int prox = lowerMedianProximity(a, b, m);
if(prox == 0) return m;
else if(prox == -1) return findLowerMedianIndex(a, b, m+1, last);
else return findLowerMedianIndex(a, b, first, m-1);
}
}``````

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

``````int get( const vector< int >  &a, int lo, int hi, const int e ) {
int ret = lo;
while( lo <= hi ) {
int mid = ( lo + hi ) / 2;
if( a[mid] > e ) hi = mid - 1;
else {
lo = mid + 1;
if( ret < mid ) ret = mid;
}
}
return ret;
}

int lowerMedian ( const vector<int> S, const vector<int> T) {

int N = S.size();
int M = T.size();

int i = 0 , j = 0 ;

int needSmaller = N+M;

if( !needSmaller ) return -1; /// Both vectors are empty

if( needSmaller % 2 ) needSmaller /= 2;
else needSmaller = ( needSmaller / 2 ) - 1;

while( i < N || j < M ) {

if( i == N ) return T[j + needSmaller];
if( j == M ) return S[ i + needSmaller ];

if( S[i] < T[j] ) {
if( !needSmaller ) return S[i];
int idx = get ( S , i , N-1 , T[j] );
if( idx - i >= needSmaller ) return S[ i + needSmaller ] ;
needSmaller -= idx - i + 1;
i = idx + 1;
continue;
}

if( S[i] > T[j] ) {
if( !needSmaller ) return T[j];
int idx = get ( T , j , M-1 , S[i] );
if( idx - j >= needSmaller ) return T[ j + needSmaller ];
needSmaller -= idx - j + 1;
j = idx + 1;
continue;
}
}

/// code will not come here
return -1;
}``````

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

GeeksForGeeks

Perfect O(log(n))

public class GetMedianRec {

/*
* This function returns median of ar1[] and ar2[]. Assumptions in this
* function: Both ar1[] and ar2[] are sorted arrays Both have n elements
*/
static 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
*/
static 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 (i == 0 || ar2[j] > ar1[i - 1])
return Math.min(ar1[i], ar2[j]);
else
return Math.min(ar1[i], ar1[i - 1]);
}

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

public static void main(String[] args) {
int ar1[] = { 1, 2 };
int ar2[] = { 4, -2 };

System.out.println(getMedian(ar1, ar2, ar1.length));
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ merge :: [Int] -> [Int] -> [Int] merge [] (x:xs) = [x] ++ xs merge (x:xs) [] = [x] ++ xs merge (x:xs) (y:ys) | x > y = [y] ++ merge ([x] ++ xs) ys | otherwise = [x] ++ merge xs ([y] ++ ys) }}} {{{ let t = merge [3,6,7,9] [-1,1,2,8] *Main> t !! ((length t) `div` 2 - 1) 3 }
Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{ merge :: [Int] -> [Int] -> [Int] merge [] (x:xs) = [x] ++ xs merge (x:xs) [] = [x] ++ xs merge (x:xs) (y:ys) | x > y = [y] ++ merge ([x] ++ xs) ys | otherwise = [x] ++ merge xs ([y] ++ ys) }}} {{{ let t = merge [3,6,7,9] [-1,1,2,8] *Main> t !! ((length t) `div` 2 - 1) 3 }
Comment hidden because of low score. Click to expand.
0
of 0 vote

Reformatted :

``````merge :: [Int] -> [Int] -> [Int]
merge [] (x:xs) = [x] ++ xs
merge (x:xs) [] = [x] ++ xs
merge (x:xs) (y:ys)
| x > y = [y] ++ merge ([x] ++ xs) ys
| otherwise = [x] ++ merge xs ([y] ++ ys)``````

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

``````let t = merge [3,6,7,9] [-1,1,2,8]
t !! ((length t) `div` 2 - 1)``````

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.