CareerCup

//this is sooo easy. just do something similar to a merge sort except u process it only k times.
int gimme (int[] first, int[]sec, int k)
{
int seen = 0, i = 0, j = 0;
for(; seen < k; ++seen)
{
if(i == first.length) { j++; continue; }
if(j == second.length) { i++; continue; }
if(first[i] < second[j])i++; else j++;
}
return Math.min(first[i],second[j];)

}

You should clarify what kth smallest element mean when there are duplicates. If it means there are k-1 elements that are smaller than the result, but that k-1 elements may itself has duplicates, you algorithm still works.

If it means there are k-1 distinct values that are smaller than the result, then there is no O(log n) solution. At least not to my knowledge.

A simple solution in java. Worst case is O(n). Logic is the same of merge in MergeSort: we have two index i,j that move in the two arrays as minimum element is found respectively. We need an additional check for duplicate elements. This is a simple loop to move pointers to an element which is bigger than current minimum.

private static int findKSmallest(int[] arr1, int[] arr2, int k) {
		int i = 0; 
		int j = 0; 
		int min = -1; 
		while (k > 0){
			while (arr1[i] <= min)
				i++; 
			while (arr2[j] <= min)
				j++;
			if (arr1[i] < arr2[j]){				
				min = arr1[i]; 
				i++; 
			}else{				
				min = arr2[j];
				j++;
			}
			k--; 			
		}
		return min;		
	}

int findkthsmallest(int a[], int b[], int k, int len1, int len2) {

    int i = 0, j = 0;
    int elem=0, tmp=0, k1 = k;
    assert(k);
    if (k>len1 && k > len2)
      assert (0);
    while (k) {
        if (i<len1 && j<len2) {
            if (a[i] < b[j]) {
                tmp = a[i];
                i++;
            } else {
                tmp = b[j];
                j++;
            }
        } else if (i<len1) {
            tmp = a[i];
            i++;
        } else if (j<len2) {
            tmp = b[j];
            j++;
        }
        else
            assert(0); // k is too large, gone out of bound sof both arrays
        if (k!=k1) {
            if (tmp != elem) {
                k--;
            }
        }
        elem = tmp;
    }
    return elem;
}

You can use merge sort approach. Use a variable, n, to keep the count of nth smallest number. Keep track of the current nth smallest number, if both values are the same and is equal to the ith smallest number, skip both values, otherwise increment n and update the smallest number. If n equals k, return the nth smallest number

If one of them reaches to the end of the array, do a while loop from there until n reaches k.

This is a solution in O(nlgm + mlgn) time, the idea is basically looking for a pair of indices (i, j) in arrays A and B respectively such that j = k - (i + 1) and B[j] <= A[i] <= B[j+1]. In other words, we're looking in A for an item larger than k - 1 items (making it the kth largest one).

We can do this with a binary search in A and if no such item exists in it we can look in B instead. This is the code for the described algorithm:

int find_kth_item(
    const vector<int>& first_array,
    const vector<int>& second_array,
    const int& k,
    const int& left_index,
    const int& right_index)
{
    assert(first_array.size() != 0 || second_array.size() != 0);
    assert(k <= (int)(first_array.size() + second_array.size()));

    // Element not found in A, look in B.
    if (left_index > right_index)
        return
            find_kth_item(
                second_array,
                first_array,
                max(0, k - (first.size() + 1)),
                min(second_array.size() - 1, k));

    // Binary search.
    int a_kth_index = (left_index + right_index) / 2;
    int b_kth_index = (k - 1) - (a_kth_index + 1);

    if ((b_kth_index == -1 || first_array[a_kth_index] >= second_array[b_kth_index])
        && (b_kth_index == second_array.size() - 1 || first_array[a_kth_index] <= second_array[b_kth_index + 1]))
        return first_array[a_kth_index];

    if ((b_kth_index == -1 || first_array[a_kth_index] > second_array[b_kth_index])
            && b_kth_index < second_array.size() - 1
            && first_array[a_kth_index] > second_array[b_kth_index + 1])
        return
            find_kth_item(
                first_array, second_array, k, left_index, a_kth_index - 1);

    return
        find_kth_item(first_array, second_array, k, a_kth_index + 1, right_index);
}

int find_kth_item(
    const vector<int>& first_array,
    const vector<int>& second_array,
    const int& k)
{
    assert(first_array.size() != 0 || second_array.size() != 0);

    // In the extreme where kth item is less than all j items, then there's no need to look
    // further than min(k, |A|) in A for the upper bound of the binary search. In the extreme
    // where kth item is greater than all j items, then there is no need to look further than
    // max(0, k - |B|) for the lower bound since anything less would fail to meet the success
    // criteria: i + j = k - 1.
    return
        find_kth_item(
            first_array,
            second_array,
            max(0, k - (second_array.size() + 1)),
            min(first_array.size() - 1, k));

}

Just a speed-up on the O(k) merge sort. The initial indexing variables on arrays a and b can both start from k/2 rather than 0, since the kth smallest element will definitely not be in [0-k/2] elements of each of the arrays.
This way you could double the speed by reducing the merging size by half.

/**
 * Objective: To find Kth smallest element from two sorted arrays
 * 
 * @author sunichak
 *
 */
public class KthSmallestElementInTwoSortedArrays {

	public static void main(String[] args) {
		// sample input
		int[] first = {1,5,6,7,9};
		int[] second = {1,3,5,5,8};
		int k = 5;
		getKthElement(k, first, second);
	}
	
	static void getKthElement(int k, int[] first, int[] second) {
		int count = 0, i = 0, j = 0;
		int val = 0;
		if(k<1 || k>(first.length + second.length)) {
			System.out.println("Invalid K!");
			return;
		}
		while(count != k) {
			int a, b;
			if(i < first.length) { 
				a = first[i];
			} else {
				a = Integer.MAX_VALUE;
			}
			if(j < second.length) {
				b = second[j];
			} else {
				b = Integer.MAX_VALUE;
			}
			if(a == b && a != Integer.MAX_VALUE) {
				i++;
			} else if(a < b && a != val) {
				if(val != a) {
					val = a;
					count++;
				}
				i++;
				continue;
			} else if(a > b) {
				if(val != b) {
					val = b;
					count++;
				} 
				j++;
				continue;
			} else {
				count++;
			}
		}
		System.out.println(val);
	}
}

The best I can think of is O(k log(n)) complexity. It is essentially finding first k (or up to k if there are fewer) distinct elements in each array, and using an O(log(k)) algorithm to find the kth distinct element.

1) Find the middle element of First array A, say Amid
2) Find the first element in B which is <= A[Mid], say Bbound
3) Let no of elements from AL to Amid be no_A
3) Let no of elements from BL to Bbound be no_B
4) if no_A+no_B == k , then max of A[Mid],B[Bound] is our solution
5) if no_A+no_B > K , then Kth element is in A(AL,AMid-1) or B(BL,Bound-1)
6) if no_A+no_B < K, then the Kth element is in A(Mid+1,AR) or B(Bound+1,BR), , you need to adjust K to K-(no_A+no_B)
Base case:
if A is exhaused return B[BL+k]
if B is exhaused return A[AL+K]

I think the overall complexity is O(logn)

int kthElementUnion(vector<int>& A, vector<int>& B, int AL, int AR, int BL, int BR, int k){
	if (AL > AR){
		return B[BL + k - 1];
	}
	else if (BL > BR){
		return A[AL + k - 1];
	}
	else{
		int AM = AL + (AR - AL) / 2;
		int no_A = AM - AL + 1;

		int BBound = distance(begin(B),lower_bound((begin(B)+BL),(begin(B)+BR+1), A[AM]));

		if (BBound >= B.size() || B[BBound] > A[AM])
			BBound--;
		int no_B = BBound-BL+1;
		if (no_A + no_B == k)
			return max(A[AM], B[BBound]);
		else if (no_A + no_B < k){
			AL = AM + 1;
			BL = BBound + 1;
			k = k - (no_A + no_B);
			return kthElementUnion(A,B,AL,AR,BL,BR,k);
		}
		else{
			BR = BBound - 1;
			AR = AM - 1;
			return kthElementUnion(A, B, AL, AR, BL, BR, k);
		}
	}
}

int main(){
	int a[] = { 1, 3, 4, 6 };
	vector<int> A(a, a + 4);
	int b[] = { 0, 2, 3, 4, 5 };
	vector<int> B(b, b + 5);

	//Union{0,1,2,3,3,4,4,5,6} 

	for (int i = 1; i <= 9; ++i){
		int elem = kthElementUnion(A, B, 0, A.size() - 1, 0, B.size() - 1, i);
		cout << elem << " ";
	}
		
	return 0;
}

Uses binary search among the first K elements in both the arrays.

public static int KthSmallest1DMergeOfTwoArrays(){
		int ans = -1;
		int k = 9;
		int[] arr1 = {3,3,3,3,3,3};
		int[] arr2 = {3,3,3,3};
		int[] s= {0, 0};
		int[] e= {Math.min(k-1, arr1.length-1), Math.min(k-1, arr2.length-1)};

		while(s[0] <= e[0] && s[1] <= e[1] && e[0] <= arr1.length-1 && e[1] <= arr2.length-1){
			int mid0 = s[0] + (e[0]-s[0])/2;
			int mid1 = s[1] + (e[1]-s[1])/2;
			if(arr1[mid0] > arr2[mid1]){
				k = k - (mid1-s[1] +1);
				if(k == 0)
					return arr2[mid1];
				e[1] = Math.min(mid1+k, e[1]);
				s[1] = mid1+1;
				e[0] = Math.min(s[0]+k-1, e[0]); 
			}else if(arr1[mid0] < arr2[mid1]){
				k = k - (mid0-s[0] +1);
				if(k == 0)
					return arr1[mid0];
				e[0] = Math.min(mid0+k, e[0]);
				s[0] = mid0+1;
				e[1] = Math.min(s[1]+k-1, e[1]); 
			} else{
				k = k - (mid0-s[0] +1);
				e[0] = Math.min(mid0+k, e[0]);
				s[0] = mid0+1;
				k = k - (mid1-s[1] +1);
				e[1] = Math.min(mid1+k, e[1]);
				s[1] = mid1+1;
				if(k <= 0)
					return arr1[mid0];
			}			
			
		}
		
		while(s[0] <= e[0] && e[0] <= arr1.length -1){
			k--;
			if(k == 0){
				return arr1[s[0]];
			}
			s[0]++;
		}
		
		while(s[1] <= e[1] && e[1] <= arr2.length -1){
			k--;
			if(k == 0){
				return arr2[s[1]];
			}
			s[1]++;
		}
		System.out.println("some out issue");
		return ans;
	}

logncomplexity.wordpress.com/2013/01/10/48/

Check my analysis and O(logn) solution here:
allenlipeng47.com/PersonalPage/index/view/94/nkey

O(lgk) solution

int combined_kth(int* a, int n, int* b, int m, int k)
{
    if (m + n < k) return -1;
    if (k <= 0) return -1;
    while (k > 1)
    { 
        int ak = std::min(n - 1, k/2-1);
        int vak = std::numeric_limits<int>::max();
        if (ak >= 0) vak = a[ak];
        int bk = std::min(m - 1, k/2-1);
        int vbk = std::numeric_limits<int>::max();
        if (bk >= 0) vbk = b[bk];
        if (vak < vbk) 
        {
            n -= (ak + 1);
            a += (ak + 1);
            k -= (ak + 1);
        }
        else 
        { 
            m -= (bk + 1);
            b += (bk + 1);
            k -= (bk + 1);
        }
    } 

    int rv = std::numeric_limits<int>::max();
    if (n > 0) rv = std::min(rv, a[0]);
    if (m > 0) rv = std::min(rv, b[0]);

    return rv;
}

void test_combined_kth()
{
    int a[] = { 1, 3, 5, 11, 30, 47, 66, 108 };
    int b[] = { -6, 2, 7, 11, 32, 43, 61 };
    assert(-6 == combined_kth(a, sizeof(a) / sizeof(int), b, sizeof(b) / sizeof(int), 1));
    assert(3 == combined_kth(a, sizeof(a) / sizeof(int), b, sizeof(b) / sizeof(int), 4));
    assert(5 == combined_kth(a, sizeof(a) / sizeof(int), b, sizeof(b) / sizeof(int), 5));
    assert(30 == combined_kth(a, sizeof(a) / sizeof(int), b, sizeof(b) / sizeof(int), 9));
    assert(61 == combined_kth(a, sizeof(a) / sizeof(int), b, sizeof(b) / sizeof(int), 13));
    assert(108 == combined_kth(a, sizeof(a) / sizeof(int), b, sizeof(b) / sizeof(int), 15));
    assert(-1 == combined_kth(a, sizeof(a) / sizeof(int), b, sizeof(b) / sizeof(int), 16));
    assert(-1 == combined_kth(a, sizeof(a) / sizeof(int), b, sizeof(b) / sizeof(int), -2));
}

/*
 * where 'n' in [1, size1+size2]
 *//
int find(const int *arr1, const int size1, const int *arr2, const int size2, const int n)
{
    if (size1 <= 0 || size2 <= 0 || arr1 == 0 || arr2 == 0 || n == 0 || n > size1+size2)
        return -1;

    int i = 0, j = 0;
    int val = 0;
    while (i+j < n)
    {
        if ((i < size1 && !(j < size2)) || (i < size1 && arr1[i] < arr2[j]))
        {
            val = arr1[i];
            i++;
        }
        else
        {
            if (j < size2)
                val = arr2[j];
            j++;
        }
    }

    return val;
}

If Google is asking this, then I do not want to work there.

Way too easy.