Goldman Sachs Interview Question
Software ArchitectsCountry: India
Interview Type: Phone Interview
Here is a better solution that still uses O((M+N)/2) complexity but with minimal space:
#include "CommonHeader.h"
double findMedian(const std::vector<int>& arr1, const std::vector<int>& arr2)
{
// Sanity
size_t arr1Index = 0;
size_t arr2Index = 0;
size_t maxMergedSize = arr1.size() + arr2.size();
bool isOdd = ((maxMergedSize % 2) != 0);
// We need to merge both arrays and return the median
// Incase the merged array size is odd we need to merge halfway and return the last element in the merged array
// otherwise, we return the avg of the two last elements of the merged array
size_t minMergedSize = isOdd ? (maxMergedSize / 2) : ((maxMergedSize / 2) + 1);
size_t elementsToKeep = isOdd ? 1 : 2;
size_t counter = 0;
// We use queue to keep the values of the last 2 elements (or 1, depends on the total number of numbers of both arrays)
std::queue<int> q;
while(true) {
int a = arr1[arr1Index];
int b = arr2[arr2Index];
if(a < b) {
q.push(a);
if(q.size() > elementsToKeep) q.pop();
arr1Index++;
} else {
q.push(b);
if(q.size() > elementsToKeep) q.pop();
arr2Index++;
}
++counter;
if(counter == minMergedSize) break;
}
if(isOdd) {
// return the last number in the array
return (double) q.front();
} else {
// we cast to double to allow decimal points
double a = q.front(); q.pop();
double b = q.front(); q.pop();
return (a + b) / 2.0;
}
}
Merge both arrays and return the median.
However, we don't need to fully merge the arrays only O((M+N)/2) where M and N are the array sizes.
#include "Common.h"
double findMedian(const std::vector<int>& arr1, const std::vector<int>& arr2)
{
size_t arr1Index = 0;
size_t arr2Index = 0;
size_t maxMergedSize = arr1.size() + arr2.size();
bool isOdd = ((maxMergedSize % 2) != 0);
// We need to merge both arrays and return the median
// Incase the merged array size is odd we need to merge halfway and return the last element in the merged array
// otherwise, we return the avg of the two last elements of the merged array
size_t minMergedSize = isOdd ? (maxMergedSize / 2) : ((maxMergedSize / 2) + 1);
std::vector<int> mergedArray;
while(true) {
int a = arr1[arr1Index];
int b = arr2[arr2Index];
if(a < b) {
mergedArray.push_back(a);
arr1Index++;
} else {
mergedArray.push_back(b);
arr2Index++;
}
if(mergedArray.size() == minMergedSize) break;
}
if(isOdd) {
// return the last number in the array
return (double)mergedArray[mergedArray.size() - 1];
} else {
// we cast to double to allow decimal points
return (double)(mergedArray[mergedArray.size() - 1] + mergedArray[mergedArray.size() - 2]) / 2.0;
}
}
PenChief and NoOne, why do you actually need to perform the merge?
You can just run through the merge process without actually storing the results. Thus, it becomes an O(1) algo.
The following is just to give an idea. I definitely did not cover the corner cases.
int A = arr1.length;
int B = arr2.length;
int m = (int)(A+B)/2; // The index of the first median element in the merged array
int n = (A+B) % 2 == 0 ? 2 : 1; // No. of median elements
int i, j;
while(i < A && j < B && (i+j) < m) {
int a = arr1[i];
int b = arr2[j];
if (a < b)
i++;
else
j++;
}
while(i < B && (i+j) < m)
i++;
while(j < B && (i+j) < m)
j++;
if (i == A) {
return n == 1 ? arr2[j] : (arr2[j]+arr2[j+1])/2;
} else if (j == B)
return n == 1 ? arr1[i] : (arr1[i]+arr1[i+1])/2;
} else {
int x = arr1[i] < arr2[j] ? arr1[i++] : arr2[j++];
int y = arr1[j] < arr2[j] ? arr1[i] : arr2[j];
}
public static void main(String[] args) {
int[] arr1 = { 1, 2, 5 };
int[] arr2 = { 3,4 };
int n = getMedian(arr1, arr2);
System.out.println(n);
}
public static int getMedian(int[] arr1, int[] arr2) {
int n = arr1.length;
int m = arr2.length;
int q = n + m;
if (q % 2 == 0)
return (getKthPositionValue(arr1, arr2, q / 2) + getKthPositionValue(arr1, arr2, q / 2+1)) / 2;
else
return getKthPositionValue(arr1, arr2, q / 2+1);
}
public static int getKthPositionValue(int[] arr1, int[] arr2, int k) {
int n = arr1.length;
int m = arr2.length;
int i = 0;
int j = 0;
while (i < n && j < m) {
if (i < arr1.length && j < arr2.length && arr1[i] < arr2[j]) {
i++;
k--;
if (k == 0)
return arr1[i - 1];
}
if (i < arr1.length && j < arr2.length && arr2[j] < arr1[i]) {
j++;
k--;
if (k == 0)
return arr2[j - 1];
}
}
if (i < arr1.length - 1 && (k + i -1) < n) {
return arr1[k + i -1];
}
if (j < arr2.length - 1 && (k + j -1) < m) {
return arr2[k + j -1];
}
return -1;
}
There is a solution without merge, thus O(1) space complexity and and time complexity of something like O(lg(m)*lg(n)) or O(lg(m+n)) [depending on how smart you implement it] which is basically a simultaneous binary search over the two arrays. It goes like this:
- since the array are sorted, you can jump into the middle of the first array, pick that element and binary search it in the second array, then you know the order of that element (e.g. k-th order). since you are looking for n/2 or n/2-1 and n/2 you can correct, so you repeat it but only consider the first arrays upper or lower part etc.
- The corner cases are ugly, if you want to optimize constant factors etc.
if you are interested there is the exact same question on leetcode including some explanations in quite some details. How ever, you'll need to write it on a piece of paper to fully understand corner cases and cleanly code it.
final static int ARR1 = 0;
final static int ARR2 = 1;
static int median(int[] arr1, int[] arr2) {
int[][] arrs = new int[][]{arr1,arr2};
int[] ptrs = new int[] {-1,-1};
int length = arr1.length + arr2.length;
int middle = 1 + (length/2);
int prev = 0;
int median = 0;
for (int i = 0; i < middle; i++) {
int which;
if (ptrs[ARR1] >= arrs[ARR1].length - 1) {
// reached end of ARR1 so must move ARR2
which = ARR2;
} else if (ptrs[ARR2] >= arrs[ARR2].length - 1) {
// reached end of ARR2 so must move ARR1
which = ARR1;
} else if (arrs[ARR1][ptrs[ARR1]+1] >= arrs[ARR2][ptrs[ARR2]+1]) {
// next ARR1 is bigger than next ARR2, so move ARR2
which = ARR2;
} else {
which = ARR1;
}
prev = median;
ptrs[which]++;
median = arrs[which][ptrs[which]];
}
if (length % 2 == 0) {
// its even, so return the average (cast to int, but could be returned as a double)
return (median + prev) / 2;
}
return median;
}
std::vector<int> v1{ 1, 5, 7, 8, 9 };
std::vector<int> v2{ 2, 3, 6, 7, 8, 10 };
std::vector<int> v3(v1.size() + v2.size());
std::copy(v1.begin(), v1.end(), v3.begin());
std::copy(v2.begin(), v2.end(), v3.begin() + v1.size());
std::inplace_merge(v3.begin(), v3.begin() + v1.size(), v3.end());
int middle = v3.size() / 2;
if (v3.size() % 2 == 0 && v3.size() > 1)
{
return (float)(v3[middle] + v3[middle+1]) * .5f;
}
return (float)v3[middle];
median xs
| trueCenter = xs!!center
| otherwise = (xs!!center + xs!!center+1)/2
where
center = floor $ realToFrac (length xs) / 2
trueCenter = (realToFrac (length xs) / 2) == realToFrac center
merge [] ys = ys
merge (x:xs) ys = x : (merge xs ys)
main = do
print "Median of the list"
print $ merge [1,2,3,4,5,7] [6,8,9, 10, 11, 12]
print $ median $ merge [1,2,3,4,5,7] [6,8,9, 10, 11, 12]
public class MedianArrays {
public static void main(String[] args) {
int[] arr1 = {4,5,6,7,15,20,34,66,71};
int[] arr2 = {0,37,99,133,155,178,200};
int k1, k2 = -1, value1 = 0, value2 = 0;
if ( (arr1.length + arr2.length)%2 == 0 ) {
k1 = (arr1.length + arr2.length)/2 ;
k2 = k1+1;
} else {
k1 = (arr1.length + arr2.length)/2 + 1;
}
int i = 0, j = 0;
for ( int k = 0; k < (k1<k2?k2:k1); k++ ) {
value1 = value2;
if ( arr1[i] <= arr2[j] ) {
value2 = arr1[i++];
} else {
value2 = arr2[j++];
}
System.out.print(value2 + ",");
}
System.out.println();
if ( k2 == -1 ) {
System.out.println(value2);
} else {
System.out.println((value1 + value2)/2.0);
}
}
}
array1 = [1,6,7,8,9,12,15,16]
array2 = [2,5,12,13]
def find_median(array1, array2):
size = len(array1) + len(array2)
index = int(size/2)
even = (size%2 == 0)
i =0
j=0
count = 0
median = []
current = 0
prev= 0
while count < index + 1:
prev = current
if(i < len(array1) and (len(array2) == j) or array1[i] < array2[j]):
current = array1[i]
i= i+1
elif j < len(array2):
current = array2[j]
j = j+1
count = count + 1
if even:
return (prev + current)/2
else:
return current
print(find_median(array1, array2))
array1 = [1,6,7,8,9,12,15,16]
array2 = [2,5,12,13]
def find_median(array1, array2):
size = len(array1) + len(array2)
index = int(size/2)
even = (size%2 == 0)
i =0
j=0
count = 0
median = []
current = 0
prev= 0
while count < index + 1:
prev = current
if(i < len(array1) and (len(array2) == j) or array1[i] < array2[j]):
current = array1[i]
i= i+1
elif j < len(array2):
current = array2[j]
j = j+1
count = count + 1
if even:
return (prev + current)/2
else:
return current
print(find_median(array1, array2))
and
array1 = [1,6,7,8,9,12,15,16]
array2 = [2,5,12,13]
def find_median(array1, array2):
size = len(array1) + len(array2)
index = int(size/2)
even = (size%2 == 0)
i =0
j=0
count = 0
median = []
current = 0
prev= 0
while count < index + 1:
prev = current
if(i < len(array1) and (len(array2) == j) or array1[i] < array2[j]):
current = array1[i]
i= i+1
elif j < len(array2):
current = array2[j]
j = j+1
count = count + 1
if even:
return (prev + current)/2
else:
return current
print(find_median(array1, array2))
and
- NoOne September 25, 2017