Google Interview Question
Software EngineersCountry: Switzerland
Simple Algorithms
Take the mid element of the largest array, and find out the location of that in second array and then compare with N
Here is the formal algorithm
FindNthRankElement(Array1, Array2, N)
Mid1 = Array1.Mid;
Mid2 = FindMid1LocationInArray2; // this should be the element which is just smaller to Array1.Mid1
if(Mid1-Array1.Start + Mid2 - Array2.Start < N)
Array1 = Array1[Mid1 to Array1.End];
Array2 = Array2[Mid2 to Array2.End];
N = N-(Mid1-Array1.Start + Mid2 - Array2.Start);
Call again
else if(Mid1-Array1.Start + Mid2 - Array2.Start > N)
Array1 = Array1[Array1.Start to Mid1];
Array2 = Array2[Array2.Start to Mid2];
Call again
else
return Array1.Mid1
Complexity is O(Log(N)) Time + O(1) Space
Edit : Complexity : O(Log(n)*Log(n)) Time + O(1) Space
1.) Given two sorted arrays of Size N1 and N2 , you have to find the element at Kth position when both are merged.
2.) Take the element at index k*N1/(N1+N2) from array with size N1
i.e int N1Mid = k*N1/(N1+N2)
Now from second array take int N2Mid = K-N1Mid-1
3.) Now if N1[N1Mid] > N2[N2Mid] , search on right side of second array i.e from N2Mid To End and left side of first array N1Start to N1Mid-1 (like Binary Search) ... reduce k by number of elements left in second array
else do the other way around , seach on right side of first and left side of second reduce K
4.) Keep on doing this recursively
Here is the code
public static int findKth(int A[], int B[], int k,
int aStart, int aEnd, int bStart, int bEnd) {
int aLen = aEnd - aStart + 1;
int bLen = bEnd - bStart + 1;
// Handle special cases
if (aLen == 0)
return B[bStart + k];
if (bLen == 0)
return A[aStart + k];
if (k == 0)
return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
int aMid = aLen * k / (aLen + bLen); // a's middle count
int bMid = k - aMid - 1; // b's middle count
// make aMid and bMid to be array index
aMid = aMid + aStart;
bMid = bMid + bStart;
if (A[aMid] > B[bMid]) {
k = k - (bMid - bStart + 1);
aEnd = aMid;
bStart = bMid + 1;
} else {
k = k - (aMid - aStart + 1);
bEnd = bMid;
aStart = aMid + 1;
}
return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}
public class MergedArrayService
{
public static int findNthValue(int[] a, int [] b, int n) throws NullPointerException
{
if(a==null||b==null)
{
throw new NullPointerException("one or more input arrays is null");
}
if(n<0)
{
throw new IllegalArgumentException("n must be atleast 0");
}
int pa=0;
int pb=0;
int pmerge=0;
int[] merge=new int[n+1];
while((pa<a.length) && (pb<b.length) &&(pmerge<merge.length))
{
if(a[pa]<=b[pb])
{
merge[pmerge++]=a[pa++];
}else
{
merge[pmerge++]=b[pb++];
}
}
while(pa<a.length && pmerge<merge.length)
{
merge[pmerge++]=a[pa++];
}
while(pb<b.length && pmerge<merge.length)
{
merge[pmerge++]=b[pb++];
}
return merge[pmerge-1];
}
public static int[] getInputArray(int n)
{
if(n==0)
{
return null;
}
int[] a=new int[n];
Random rnd=new Random();
for(int i=0;i<n;i++)
{
a[i]=rnd.nextInt(n);
}
return a;
}
public static void main(String[] args)
{
Random rnd=new Rnadom();
int n=rnd.nextInt(101);
int[] a=MergedArrayService.getInputArray(n);
n=rnd.nextInt(101);
int[] b=MergedArrayService.getInputArray(n);
System.out.println("a: " + Arrays.toString(a));
System.out.println("b: " + Arrays.toString(b));
int k=MergedArrayService.findNthValue(a,b,rnd.nextInt(a.length+b.length));
System.out.println("nth value: " + k);
}
}
//O(n) time and O(n) space--where n is the rank of the element we are interested in finding.
public int? FindNthElement(int[] a1, int[] a2, int n)
{
if (a1 == null || a2 == null || n < 0 || (a1.Length + a2.Length) <= n)
return null;
int i = 0;
int j = 0;
while (true)
{
if (i + j == n)
break;
if (j >= a2.Length || i < a1.Length && a1[i] < a2[j])
i++;
else
j++;
}
return (j >= a2.Length || i < a1.Length && a1[i] < a2[j]) ? a1[i] : a2[j];
}
void mergeSort(int oneArr[SIZE1],int twoArr[SIZE2],int n)
{
int resArr[SIZE3] = {0};
int j=0,k=0,i=0;
while(i<SIZE1 || k<SIZE2)
{
if(i>=SIZE1)
resArr[j] = twoArr[k];
if(k>=SIZE2)
resArr[j] = oneArr[i];
if(j==n)
{
cout << n << "th element is "<< resArr[j];
return;
}
if(oneArr[i] < twoArr[k])
{
resArr[j] = oneArr[i];
i++;
}
else
{
resArr[j] = twoArr[k];
k++;
}
j++;
}
}
Operates with runtime complexity of O(k) and memory O(1) where k is the position in the merged array:
public static int getMergedValue(int[] arr1, int[] arr2, int k){
//check for illegal inputs
if(arr1 == null || arr2 == null){
throw new NullPointerException();
}
if(k >= arr1.length + arr2.length){
throw new IllegalArgumentException();
}
//'merge' the arrays
int pos = 0;
int arr1Pos = 0;
int arr2Pos = 0;
while(pos < k && arr1Pos < arr1.length && arr2Pos < arr2.length){
if(arr1[arr1Pos] < arr2[arr2Pos]){
arr1Pos++;
}
else {
arr2Pos++;
}
pos ++;
}
//if one or the other array is exhausted
if(pos < k){
if(arr1Pos < arr1.length){
arr1Pos += (k - pos);
return arr1[arr1Pos];
}
else{
arr2Pos += (k - pos);
return arr2[arr2Pos];
}
}
//return the smallest of the current positions in the array
if(arr1[arr1Pos] < arr2[arr2Pos]){
return arr1[arr1Pos];
}
return arr2[arr2Pos];
}
Sample solution in C++. O(K) where K is the desired order.
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int getNth(const vector<int>& a, const vector<int>& b, int n) {
if (a.size() + b.size() < n) return -1;
auto itrA = a.begin();
auto itrB = b.begin();
if (itrA == a.end()) return *(itrB + n-1);
if (itrB == b.end()) return *(itrA + n-1);
for (int i = 0; i < n - 1; ++i) {
if (*itrA < *itrB) {
++itrA;
} else {
++itrB;
}
}
return min(*itrA, *itrB);
}
int main() {
vector<int> a {1,3,4,5,8};
vector<int> b {};
int nth = getNth(a, b, 4);
cout << nth << endl;
return 0;
}
- tested.candidate July 14, 2015