Riverbed Interview Question Software Engineer / Developers
Country: United States
The above solution works but is O(k). For large values of k, this solution may not be optimal.
There is a better solution that works in O(log m + log n) where m and n are the lengths of the two arrays. This solution uses a divide-and-conquer approach.
Select Ai and Bj from the two arrays A and B such that i+j = k -1.
If Ai > Bj,
the kth smallest element should lie in the subarrays [A0 - Ai] and [Bj - Bn]
the way to understand this is that none of the elements in [B0 - Bj] can be the kth smallest element when u consider the union of the two arrays (think about this for a while)
by similar reasoning, all the elements in [Ai+1 - Am] should be greater than the kth smallest element and can be eliminated.
Apply the same logic recursively to the two subarrays [A0 - Ai] and [Bj - Bn]. But now since we have eliminated j elements which are less than the kth smallest element, we have to look for k-j th element in the two subarrays.
/*
* Given 2 sorted arrays find kth element in merged sorted array
*/
int KthMergedSorted (int a[], int b[], int k) {
int len1 = 5;
int len2 = 5;
int i, l = 0, m = 0;
if (len1 + len2 < k) {
return (FALSE);
}
for (i = 0; i < k; i++) {
if (l < len1 && a[l] < b[m]) {
if (i == k-1) {
return (a[l]);
}
l++;
} else {
if (i == k-1) {
return (b[m]);
}
m++;
}
}
}
int main () {
printf("I AM HERE\n");
int arr1[] = {1,5,8,7,19};
int arr2[] = {2,4,13,14,20};
printf (" ..%d..",KthMergedSorted (arr1, arr2, 10));
printf("\n");
return(0);
}
Better to just count as if you were merging, but just don't merge.
public class KthElementTwoSortedArrays {
public static void main(String[] args) {
int[] b = {2,3,4,5,6,7,8,9};
int[] a = {10,11,12,13,14,15,16,17,18,19};
int k = 14;
int count = 1;
int i = 0;
int j = 0;
while (i < a.length || j < b.length) {
int n;
if (i < a.length && (j > b.length - 1 || a[i] < b[j])) {
n = a[i];
i++;
}
else {
n = b[j];
j++;
}
if (count == k) {
System.out.println("Kth entry (K = " + k + ") in merged array would be: " + n + ".");
break;
}
count++;
}
}
}
public class sorted_array {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int c =0;
int numbers_1[] = {1,2,3,4,5,6,7,8,9};
int numbers_2[]= {9,8,7,6,5,4,3,2,1};
int index = 50;
c= numbers_1.length+numbers_2.length;
int numbers_3 [] = new int[c];
for(int i = 0;i<numbers_1.length;i++)
{
numbers_3[i]=numbers_1[i];
}
for(int k = 0;k<numbers_2.length;k++)
{
numbers_3[numbers_1.length+k]=numbers_2[k];
}
if(index<c)
{
System.out.println(numbers_3[index]);
}
else
{
System.out.println("wrong index given");
}
}
}
This is basic array merge logic, except you don't actually write the merged array.
- vijay January 14, 2012public static int mergedPosition(int[] a, int[] b, int k) { int aI = 0; int bI = 0; int counter = 0; int curr = 0; while(ai < a.length && bi < b.length) { if(a[ai] < b[bi]) { curr = a[ai++]; } else { curr = b[bi++]; } counter++; if(k == counter) return curr; } while(ai < a.length) { int curr = a[ai++]; counter++; if(k == counter) return curr; } while(bi < b.length) { int curr = b[bi++]; counter++; if(k == counter) return curr; } return -1; // if k > a.length + b.length }