## Riverbed Interview Question for Software Engineer / Developers

Country: United States

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is basic array merge logic, except you don't actually write the merged array.

``````public 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
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
* 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);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++;
}
}
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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");
}
}

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.