Google Interview Question
SDE-3sCountry: United States
Interview Type: Phone Interview
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[0].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;
}
}
The Task:
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;
MergeSortTask<T> left = new MergeSortTask<>(a, helper, lo, mid);
MergeSortTask<T> right = new MergeSortTask<>(a, helper, mid+1, hi);
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[0].getClass() , a.length);
ForkJoinPool forkJoinPool = new ForkJoinPool(10);
forkJoinPool.invoke(new MergeSortTask<T>(a, helper, 0, a.length-1));
}
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.
- Chris August 26, 2017Did 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.