## Goldman Sachs Interview Question for Software Architects

• 0

Country: India
Interview Type: Phone Interview

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

``````def find_median_lazy( a, b ){
s = sset() // sorted set
s += a
s += b
l = list(s) // done, to get indexer up
len = size(l)
if ( len == 0 ) return null
// and now the rest
mid = len/2
if ( len % 2 == 0 ){
// even case, then
return (l[mid-1] + l[mid])/2.0
}
return l[mid]
}
println( find_median_lazy( [1,2] , [3,4] ) )
println( find_median_lazy( [1,2,5] , [3,4] ) )

def _merge_(a,b){
l = list()
i_a = 0
l_a = size(a)
i_b = 0
l_b = size(b)
while ( i_a < l_a && i_b < l_b ){
if ( a[i_a] < b[i_b] ){
l += a[i_a]
i_a += 1
} else {
l += b[i_b]
i_b += 1
}
}
while ( i_a < l_a ){
l += a[i_a]
i_a += 1
}
while ( i_b < l_b ){
l += b[i_b]
i_b += 1
}
l // return
}
def find_median_with_unnecessary_work(a,b){
l = _merge_(a,b)
len = size(l)
if ( len == 0 ) return null
// and now the rest
mid = len/2
if ( len % 2 == 0 ){
// even case, then
return (l[mid-1] + l[mid])/2.0
}
return l[mid]
}

println( find_median_with_unnecessary_work( [1,2] , [3,4] ) )
println( find_median_with_unnecessary_work( [1,2,5] , [3,4] ) )``````

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

Can you give couple of the example data what is required ?

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

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

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

a = [0,1,2,3,4] , b = [ -10, -2 ]
That is, no duplicate.

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

But in the question you are asking to find median element ?

"Given two sorted integer arrays, find the median element. Note that for an even sized collection, median element is to be defined as the average of the central two elements."

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

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

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

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

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

@RajK you are partially correct, the complexity is the same (O((N+M)/2) you only save space. In your code you still need to run over the array so its *not* O(1), since you need to run half way its O((M+N)/2) where M and N are the array length

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

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

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

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.

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

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

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

``````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];``````

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

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]

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

do we really need to merge 2 arrays, why not loop (M+N)/2 +1 times and just get 2 middle numbers and add a small check for even or odd

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

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

}

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

``````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))``````

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

``````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))``````

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

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

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.