techInterview Discussion 

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor 
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((nk1) / 2.0f)) dk = ceil((nk1) / 2.0f); while(dk != 0 && k1 < n && k2 < n) { if (A[k11] > B[k2]) { k2 += dk; k1 = dk; } else if (A[k1] < B[k11]) { 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[k11] < B[k21] ? B[k21] : A[k11]; }
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: "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 implementationdefined whether a right shift of a negative number propagates the sign bit. Sincerely, Gene Wirchenko
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 nontwo's compliment representation of negative numbers, so there *no* crossplatform solution to floor and ceiling.
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 kth 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
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...km1] and look for m+1th smallest element in remaining arrays 
Powered by FogBugz