Given two sorted arrays of integers........
Microsoft Interview Questions and Answers
(Continued from previous question...)
124. Given two sorted arrays of integers........
Question:
Given two sorted arrays of integers, write a function to determine the median(s) of merged array. Note: no extra space to be used. Discuss the complexity also.
maybe an answer:
public class Median {
public static void main(String args[]) {
int a[] = { 0, 1, 2, 3 };
int b[] = { 0, 1, 2 };
System.out.print("Median: ");
findMedian(a, b);
}
/*
* Two sorted arrays as input
*/
public static void findMedian(int a[], int b[]) {
int totalLength = a.length + b.length;
int median1 = 0;
int median2 = 0;
if (totalLength % 2 == 0) {
median1 = totalLength / 2;
median2 = median1 - 1;
System.out.println("Two medians");
} else {
median1 = totalLength / 2;
median2 = -1;
System.out.println("One median");
}
int aPtr = 0;
int bPtr = 0;
int previousMove = -1;
int recentMove = -1;
while ( aPtr + bPtr < median1 ) {
if (a[aPtr] < b[bPtr]) {
aPtr++; previousMove = recentMove; recentMove = 0;
} else if (a[aPtr] >= b[bPtr]) {
bPtr++; previousMove = recentMove; recentMove = 1;
}
}
if (recentMove == 0) {
System.out.print(b[bPtr]);
} else {
System.out.print(a[aPtr]);
}
// Recent move == 0 -> then the median is found in current bPtr in b array
// Recent move == 1 -> then the median is found in current aPtr in a array
if (median2 != -1) {
// Find second median in bPtr-1 of b array
if (previousMove == 0 && recentMove == 1) {
System.out.println(" and " + b[bPtr-1]);
// Find second median in aPtr-1 of a array
} else if (previousMove == 0 && recentMove == 0) {
System.out.println(" and " + a[aPtr-1]);
} else if (previousMove == 1 && recentMove == 0) {
System.out.println(" and " + b[bPtr-1]);
} else if (previousMove == 1 && recentMove == 1) {
System.out.println(" and " + a[bPtr-1]);
}
}
}
}
maybe an answer2:
int findMedian(int *a, int n, int *b, int m) {
int idx_median = (n + m - 1) / 2;
int i = 0;
int j = 0;
int l = 0;
int AorB = 0; // 0 mean in A, 1 mean in B
while (i < n && j < m && l <= idx_median) {
if (a[i] <= b[j]) {
AorB = 0;
i++;
l++;
} else {
AorB = 1;
j++;
l++;
}
}
while (i < n && l <= idx_median) {
AorB = 0;
i++;
l++;
}
while (j < n && l <= idx_median) {
AorB = 1;
j++;
l++;
}
return (!AorB) ? a[i - 1] : b[j - 1];
}
(Continued on next question...)
Other Interview Questions
|