## Google Interview Question for Software Engineer / Developers

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

Let the two arrays be A1 and A2 and their medians be m1 and m2. Find all elements between m1 and m2 and then find their median.

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

Hey Ravi: I don't think your approach will work. What is the two arrays are as follows:

Arr1: 1, 30, 35, 40
Arr2: 5, 6, 8, 9

The median should be 8. But if I take your approach, we will not get 8. Try it out.

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

It works.. Median of first array is 30. Median of second array is 6. The new array now is 6,8, 9, 30. Median of this array is 8. Actually its same as the second approach given in the link below.

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

I think the median of the first array is 32.5 and the second one is 7.

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

there are many approaches to do this, see link geeksforgeeks.org/?p=2105

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

sol2 at geekforgeeks doesn't seem to work with following case:

a1 = 5, 6, 8, 9
a2 = 1, 30, 35, 40

correct me if wrong

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

In merge sort there is one function in which we use to merge two sorted array.
Use the same logic here but here we don't have to merge the array only we have to increment two index. Continue the loop uo to (n1+n2)/2 times. Now get the lowest of index1 and index2.

float find_median(int *a, int n1 , int *b , int n2)
{
int n , even_flg = FALSE;
int acount , bcount , ccount;
float median;
acount=0;
bcount=0;
n=(n1+n2)/2;
if((n1+n2)%2==0)
{
even_flg=TRUE;
}

for(ccount=0;ccount<n && acount<n1 && bcount<n2 ; ccount++)
{
if(a[acount]<b[bcount])
{
acount++;
}
else
{
bcount++;
}
}

if(a[acount]<b[bcount])
{
median=(float)a[acount];
}
else
{
median=(float)b[bcount];
}

return median;

}

Also we have to take care
1) array over flow.
2) even number of elements (means n1+n2 is even)
for complete program see
"goursaha.freeoda.com/Miscellaneous/FindMedianFrom2SortedArray.html"

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

I think this might work as well ::

{ int count =0,number =0, i=0,j=0;
while ( i< A.length && j<B.length ){
count++;
if ( A[i] < B[j] ){
number = A[i];
i++;
}
else{
number = B[j];
j++;
}
if ( count == Math.round((A.length+B.length)/2 ){
return number;
}
}
}

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

Let the arrays be A1 and A2 with start and end as s1,e1 and s2,e2 resp.
1. find the median m1 of A1 and m2 of A2
2. Compare m1 and m2, say m1 < m2 then the median of the two arrays combined should lie in the second half of A1 or the first half of A2.
3. Update s1=m1 and e2=m2. repeat from 1 till you arrive at s1=e1 or s2=e2.

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

#define abc
int main()
{}

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

Write code to find kth largest number in the sorted arrays.

if N is odd, find n/2th number using the above algo.
if N is even, find n/2 th number and n/2+1 th number using the above algo. find mean of these two numbers.

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

Given length of arrays are know, merging two arrays till median is reached will plum it in O(n).

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

I know a solution which can run in O(logn * log(maxValue-minValue)). Its based on binary search on the range of numbers.

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

Feedbacks are welcome

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

Found an approach that is O(log(a)+log(b)). The algoritmh is based on binary search as described:
1. find the the median position (a.length+b.length)/2
2. select the median from a, and do a binary search for elements lower than a[median] in b.
3. if the sum of the position of median + lower elements in b = median pos, you have it.
4. if that sum is lower than wanted, do the same for the second half of a. since all elements of this hal are greater than previous you can also restric the lower bound in b search.
5. if that sum i higher than want, search in the previous half of a.
6. if the median was not found, is because is in b. so, invert a with b and start from step 1.

Code:

``````public class FindMedian {

public static int searchMedian(int[] a, int[] b) {
return searchMedian(a, 0, a.length-1, b, 0,
b.length-1);
}

private static int searchMedian(int[] a, int al,
int ar, int[] b, int bl, int br) {

int medianPos = (a.length + b.length)/2;
while (al <= ar) {
int am = (al+ar)/2;
int blow = bl +
countLowerThan(b, a[am], bl, br);
int curPos = am+blow;
if (curPos == medianPos)
return a[am];
if (curPos < medianPos) {
al = am+1;
bl = blow;
} else {
ar = am-1;
br = blow;
}

}
return searchMedian(b, 0, b.length-1,
a, 0, a.length-1);
}

private static int countLowerThan(int[] a, int val,
int l, int r) {
int start = l;
while (l <= r) {
int m = (l+r)/2;
if (a[m] < val &&
(m == (a.length-1) || a[m+1] >= val))
return (m+1) - start;
if (val <= a[m])
r = m-1;
else
l = m+1;
}
return 0;
}

}``````

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

thnx!!! it s working

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

int FindKthSmallest(int *a, int an, int *b, int bn, int k)
{
if (an == 0) return b[k];
if (bn == 0) return a[k];

int mida = an/2;
int midb = bn/2;

if (a[mida] == b[midb])
{
if (k == mida + midb)
{
return a[mida];
}
else if (k < mida + midb)
{
return FindKthSmallest(a, mida, b, midb, k);
}
else
{
FindKthSmallest(a+mida, an - mida, b+midb, bn - midb, k - mida - midb);
}
}
}

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

2 pointer， 1 quick pointer（everytime jump 2 steps）， 1 slower pointer（1 step per jump），

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

My solution in C++. The running time should be O(log(max - min) * log(totalSize)) using double dichotomy (see comments). It seems to be working :)

``````#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

/*  Count the number of items in L with value <= L
L is sorted, so we do it in logarithmic time.
*/
int countInf(vector<int> L, int m) {
int cnt = 0, i;
while (cnt < L.size() && L[cnt] <= m) {
for (i = 1; cnt + (i << 1) < L.size() && L[cnt + (i << 1)] <= m; i <<=1) {}
cnt += i;
}
return cnt;
}

/*
We now find the median value by dichotomy starting between the min and max value.
We do O(log(max - min)) round of the loop, each of them calling countInf on both list.
The running time is O(log(max - min) * log(total size))
*/
#define countTotalInf(m)    (countInf(L1, m) + countInf(L2, m))
int findMedian(vector<int> L1, vector<int> L2) {
if (L1.size() == 0)
return (L2.size() == 0) ? 0 : L2[L2.size() / 2];
if (L2.size() == 0)
return L1[L2.size() / 2];

int middle, start = min(L1[0], L2[0]), end = max(L1[L1.size() - 1], L2[L2.size() - 1]);

while (start != end) {
middle = (start + end) / 2;
if (countTotalInf(middle) < (L1.size() + L2.size()) / 2)
start = middle + 1;
else
end = middle;
}
return start;
}

int main(int argc, char* argv[]) {
int ar1[] = {1, 3, 5, 9, 23, 42};
int ar2[] = {2, 7, 10, 13, 26, 52, 73};
vector<int> L1(ar1, ar1 + sizeof(ar1) / sizeof(int));
vector<int> L2(ar2, ar2 + sizeof(ar2) / sizeof(int));
cout << findMedian(L1, L2) << endl;     // Prints 9
return 0;
}``````

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

Here's my compact implementation of O(log(m+n)) time algorithm. It is based on the findKth with the complexity of O(log(min(k,m,n))). O(1) space.

Please note that O(log(m+n)) is better than previously proposed O(log(m)+log(n)) since latter equals to O(log(nm))

``````int findKth(int A[], int m, int B[], int n, int k)
{
assert(k < m + n && k >= 0);
if (m == 0) return B[k];
if (n == 0) return A[k];
if (k == 0) return min(A[0], B[0]);
int halfK = (k + 1) / 2;
int asub, bsub;
asub = min(halfK, m);
bsub = min(halfK, n);
if (A[asub - 1] < B[bsub - 1])
return findKth(A + asub, m - asub, B, n, k - asub);
else return findKth(A, m, B + bsub, n - bsub, k - bsub);
}

double findMedianSortedArrays(int A[], int m, int B[], int n) {
if (m + n == 0) return INT_MIN;
int k = (m + n) / 2;
double result = findKth(A, m, B, n, k);
if ((m + n) % 2 == 0)
result = (result + findKth(A, m, B, n, k - 1)) / 2;
return result;
}``````

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

For finding the median of two sorted arrays we will have to so the binary search on the smaller array and then, we need to handle some of the corner test cases such as when the index of the first array is 0 that is it's left part is empty then the next element of the second array becomes the median and also when the index of the first array comes to be equal to its size than, we will return the sum of median along with the next element of the first array and similarly with the second array.

Implementation:

``````int findmedian(int a[], int n, int b[], int m){
int median, min_index = 0, max_index = n;
while(min_index <= max_index){
int i = (min_index + max_index) / 2;
int j = ((m + n + 1) / 2) - i;
if(i < n && j > 0 && b[j - 1] > a[i])
min_index = i + 1;
else if(i > 0 && j < m && b[j] < a[i - 1])
max_index = i - 1;
else{
if(i == 0)
median = b[j - 1];
else if(j == 0)
median = a[i - 1];
else
median = max(a[i - 1], b[j - 1]);
}
}
if((n + m) % 2 == 1)
return (double)median;
if(i == n)
return (median + b[j]) / 2.0;
if(j == m)
return (median + a[i]) / 2.0;
else{
return (median + min(b[j], a[i])) / 2.0;
}``````

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.