Google Interview Question for SDE-3s


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 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.

- Chris August 26, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 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))

- pranaypratap September 24, 2017 | Flag Reply
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[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));
}

- guilhebl August 27, 2017 | Flag Reply
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 ;)

- Nir Alfasi September 20, 2017 | Flag Reply
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.

- fallenstar November 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For Union of 2 sorted arrays
Create 2 threads
One thread keep adds elements from the beginning
Other thread adds elements from the ending.
Stop adding elements till both points meet in the final array.

- Anonymous January 28, 2018 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More