Interview Questions

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