## Google Interview Question for SDE-3s

• 0

Country: United States
Interview Type: Phone Interview

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

Why would one union two sorted arrays in memory utilizing multiple core's (or even worse one core with multiple threads) to achieve that? The bottle neck is clearly memory and not CPU.
Did he tell the two sets were on different machines? Did he potentially want to start a discussion about when multi threading makes sense (in parctice I've seen lots and lots of multithreading approaches due to a lack of understanding on overlapped I/O and other concepts)?
Especially in Java, I can't imagine doing anything good in multi-threading that task. A different thing is multiple arrays on multiple machines. That's more interesting.

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

find the median of the two sorted arrays. Divide the two arrays based on values greater and larger than the median. Merge the two distinct sets on two threads. Merge is straightforward = result(thread1).Append(result(thread2))

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

Use mergesort with Java ForkJoin. This way each thread will receive a slice of each array and sort it, after the subsequent sorts and merges the final array will be sorted.

Here's a sample code I found on the internet:

Mergesort

``````import java.lang.reflect.Array;

public class MergeSort {
public static <T extends Comparable<? super T>> void sort(T[] a) {
@SuppressWarnings("unchecked")
T[] helper = (T[])Array.newInstance(a.getClass() , a.length);
mergesort(a, helper, 0, a.length-1);
}

private static <T extends Comparable<? super T>> void mergesort(T[] a, T[] helper, int lo, int hi){
if (lo>=hi) return;
int mid = lo + (hi-lo)/2;
mergesort(a, helper, lo, mid);
mergesort(a, helper, mid+1, hi);
merge(a, helper, lo, mid, hi);
}

private static <T extends Comparable<? super T>> void merge(T[] a, T[] helper, int lo, int mid, int hi){
for (int i=lo;i<=hi;i++){
helper[i]=a[i];
}
int i=lo,j=mid+1;
for(int k=lo;k<=hi;k++){
if (i>mid){
a[k]=helper[j++];
}else if (j>hi){
a[k]=helper[i++];
}else if(isLess(helper[i], helper[j])){
a[k]=helper[i++];
}else{
a[k]=helper[j++];
}
}
}

private static <T extends Comparable<? super T>> boolean isLess(T a, T b) {
return a.compareTo(b) < 0;
}
}``````

``````private static class MergeSortTask<T extends Comparable<? super T>> extends RecursiveAction{
private static final long serialVersionUID = -749935388568367268L;
private final T[] a;
private final T[] helper;
private final int lo;
private final int hi;

public MergeSortTask(T[] a, T[] helper, int lo, int hi){
this.a = a;
this.helper = helper;
this.lo = lo;
this.hi = hi;
}
@Override
protected void compute() {
if (lo>=hi) return;
int mid = lo + (hi-lo)/2;
invokeAll(left, right);
merge(this.a, this.helper, this.lo, mid, this.hi);

}
private void merge(T[] a, T[] helper, int lo, int mid, int hi){
for (int i=lo;i<=hi;i++){
helper[i]=a[i];
}
int i=lo,j=mid+1;
for(int k=lo;k<=hi;k++){
if (i>mid){
a[k]=helper[j++];
}else if (j>hi){
a[k]=helper[i++];
}else if(isLess(helper[i], helper[j])){
a[k]=helper[i++];
}else{
a[k]=helper[j++];
}
}
}
private boolean isLess(T a, T b) {
return a.compareTo(b) < 0;
}
}``````

And finally a wrapper method that will do all the job behind the scenes:

``````public static <T extends Comparable<? super T>> void sort(T[] a) {
@SuppressWarnings("unchecked")
T[] helper = (T[])Array.newInstance(a.getClass() , a.length);
ForkJoinPool forkJoinPool = new ForkJoinPool(10);
}``````

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

You can delete all the code inside `MergeSort` class, leave only the private class, and it will still work the same ;)

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

What about using something similar to bitonic sort and doing the comparisons in parallel processors.

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

For Union of 2 sorted arrays
Stop adding elements till both points meet in the final array.

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.