techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Find the k-th smallest element in the union of two sorted array.

Given 2 sorted arrays of n elements A,B. Find the k-th smallest element in the union of A and B in O(log k) time. You can assume that there are no duplicate elements
yuren1978 Send private email
Monday, October 27, 2008
 
 
O(logK)

int ksmall(int* A, int* B, int k, int n)
{
    if (k > 2*n || k <= 0) return -1;

    int nk = k % 2 == 0 ? k : k - 1;

    int k1 = nk / 2;
    int k2 = nk / 2;
    int dk = ceil(nk / 4.0f);

    if (dk > ceil((n-k1) / 2.0f))
        dk = ceil((n-k1) / 2.0f);

    while(dk != 0 && k1 < n && k2 < n)
    {
        if (A[k1-1] > B[k2])
        {
            k2 += dk;
            k1 -= dk;
        } else if (A[k1] < B[k1-1])
        {
            k1 += dk;
            k2 -= dk;
        } else
        {
            break;
        }

        dk = ceil(dk/2.0f);
    }

    if (nk != k)
    {
        if (k1 >= n)
            k2++;
        else if (k2 >= n)
            k1++;
        else if (A[k1] < B[k2])
            k1++;
        else
            k2++;
    }

    return A[k1-1] < B[k2-1] ? B[k2-1] : A[k1-1];
}
Tao Su Send private email
Tuesday, October 28, 2008
 
 
Tao Su, it's usually better to write (int)ceil(x / 2f) as (x + 1) / 2; it's faster, and if C actually respects your float annotation (as opposed to promoting both to double), the mantissa of the float isn't long enough on most modern architectures to represent the int exactly. (On the other hand, if it does promote to double, your incantation works for MAXINT.)
d Send private email
Tuesday, October 28, 2008
 
 
Thanks for your note, d..

I've been using C# for quite some time and forgot some details of C...
Tao Su Send private email
Wednesday, October 29, 2008
 
 
Also, (x + 1) / 2 doesn't display the same behavior for negative numbers; a pedant would write (x >> 1) + (x & 1), which works for any value of any integral type assuming that the signed right shift is arithmetic.
d Send private email
Wednesday, October 29, 2008
 
 
d: "Also, (x + 1) / 2 doesn't display the same behavior for negative numbers; a pedant would write (x >> 1) + (x & 1), which works for any value of any integral type assuming that the signed right shift is arithmetic."

And the assumption can be incorrect.  In C, it is implementation-defined whether a right shift of a negative number propagates the sign bit.

Sincerely,

Gene Wirchenko
Gene Wirchenko Send private email
Wednesday, October 29, 2008
 
 
This is why signed array indices are a bad idea.  Fortunately, C++ requires size_type (the index type for each of the standard library containers) to be unsigned, and of course size_t is unsigned.

And if you want to get picky, C and C++ support non-two's compliment representation of negative numbers, so there *no* cross-platform solution to floor and ceiling.
Skorj Send private email
Friday, October 31, 2008
 
 
This problem can be derived from finding the median of two sorted arrays of length n. We know how to find the median in O(logn) time. The k-th smallest element of the union of the two sorted arrays is the median of union of the two sorted arrays considering only first K elements from each sorted array.
Praveen
Friday, October 31, 2008
 
 
tao su, can you explain your code a little?  what's the idea?
G Send private email
Sunday, November 02, 2008
 
 
I quite don't understand the details of the code posted above. But, in plain English this is how I suppose it should work and I assume the above code takes a similar approach.I thought I will give another perspective here.

We are asked to find the kth rank. That means the kth rank element is within the first k elements of the either of the sorted arrays. So, that will be the base set we will work with. A[0..k] and B[0..k].

Since, the running time needed in O(log k), it makes sense to take the approach of divide and conquer.

Therefore, we start with the middle elements of A[0..K] and B[0..k], and compare the values. Say A[i] > B[i], then we know that the value we needed is either after A[j] where i> j or B[k], where k <= i. Therefore, we just shift our pointers to the center of A[i..k] and center of B[0..k] and continue comparisons.  When we end up with just one element in either of the arrays, then we do our final comparison and decide on the element.

Therefore, the total number of operations would be log(k) + 1 . Hence, O(log(k))
gddev
Wednesday, November 26, 2008
 
 
The solution goes like this

A[1...m] B[1...n]

1. Compare A(k/2) and B(k/2)
if A(k/2) < B(k/2)

So the kth smallest can't be in A[1..k/2] and B[k/2+1 .. n]. A[1...k/2] < Kth smallest < B[k/2+1 ... n]

So we discard these elements. And now search for the k/2th smallest number in the 2 remaining arrays

if the reverse is true we do the same operation but with B and A swapped

2. if m<k

we discard B[1...k-m-1]

and look for m+1th smallest element in remaining arrays
Amit Wadhwa Send private email
Tuesday, December 09, 2008
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz