db
BAN USER
Comments (2)
Reputation 0
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
Doing binary search.
Complexity: O(log N), where N is the size of array data
int getNth(int a[], int size_a,
int b[], int size_b,
int k) {
if(size_a + size_b < k  k <= 0) {
throw "Not found";
}
int left_a = 0;
int right_a = (k < size_a) ? k : size_a;
do {
// pivots go from 0, 1...N
// 0  dont include any element from that array
// 1  first element of the array
// Hence, you will notice that all array references are left shifted by 1
int pivot_a = left_a + (right_a  left_a) / 2;
int pivot_b = k  pivot_a;
// Second array is smaller than "k"
if(pivot_b > size_b) {
left_a = (left_a == size_b) ? size_b + 1 : size_b;
continue;
}
if(pivot_a == 0 && left_a == right_a) {
return b[k1];
}
if(pivot_b == 0) {
return a[k1];
}
// We have found the expected element when:
// element pointed by a pivot is less than or equal to all elements of the other array
// Example with k = 5
// 1,3,5,7,9
// 2,4,6,8,10
// when pivot_a = 3 and pivot_b = 2
// (a[pivot_a1]=5) is less than (b[pivot_b]=6)
// and
// (b[pivot_b1]=2) is less than (a[pivot_a]=5)
if(pivot_b == size_b  a[pivot_a1] <= b[pivot_b]) {
if(pivot_a == size_a  b[pivot_b1] <= a[pivot_a]) {
return (a[pivot_a1] > b[pivot_b1]) ? a[pivot_a1] : b[pivot_b1];
}
else {
left_a = pivot_a + 1;
}
}
else {
right_a = pivot_a;
}
}
while(1);
}

db
December 05, 2014 Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Doubt that a O(log n) solution can be given for this problem, unless the BST is balanced probably?
Worst case, take a BST that is build completely with just the right tree
Example:
In order to find the 6th element, we have to traverse through down the right chain and we will have a complexity of O(n).
 db December 07, 2014