Google Interview Question for Software Engineers


Country: Switzerland




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

public class NthOfSortedArrays {
    private static int nth(int[] a, int a1, int a2, int[] b, int b1, int b2, int n) {
        if (a2 < a1) {
            return b[b1 + n];
        }
        if (b2 < b1) {
            return a[a1 + n];
        }

        int midA = (a1 + a2) / 2;
        int midB = (b1 + b2) / 2;
        if (midA - a1 + midB - b1 < n) {
            // Middle is too little to reach n
            // Get rid of the quarter which is surely smaller - it can't contain nth
            if (a[midA] > b[midB]) {
                // Lower b values are certainly below nth
                return nth(a, a1, a2, b, midB + 1, b2, n - (midB - b1 + 1));
            } else {
                // Lower a values are certainly below nth
                return nth(a, midA + 1, a2, b, b1, b2, n - (midA - a1 + 1));
            }
        } else {
            // Middle is enough to reach n
            // Get rid of the quarter which is surely bigger - it can't contain nth
            if (a[midA] > b[midB]) {
                // Upper a values are certainly above nth
                return nth(a, a1, midA - 1, b, b1, b2, n);
            } else {
                // Upper b values are certainly above nth
                return nth(a, a1, a2, b, b1, midB - 1, n);
            }
        }
    }

    private static int nth(int[] a, int[] b, int n) {
        return nth(a, 0, a.length - 1, b, 0, b.length - 1, n);
    }

    public static int[] random() {
        Random random = new Random();
        int[] array = new int[1 + Math.abs(random.nextInt()) % 9];
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextInt();
        }
        Arrays.sort(array);
        return array;
    }

    private static int[] join(int[] a, int[] b) {
        int[] joined = new int[a.length + b.length];
        System.arraycopy(a, 0, joined, 0, a.length);
        System.arraycopy(b, 0, joined, a.length, b.length);
        Arrays.sort(joined);
        return joined;
    }

    public static void main(String[] arguments) {
        int[] a = random();
        int[] b = random();
        Random random = new Random();
        int n = 1 + Math.abs(random.nextInt()) % (a.length + b.length - 2);
        System.out.println(Arrays.toString(a));
        System.out.println(Arrays.toString(b));
        System.out.println(Arrays.toString(join(a, b)));
        System.out.println(n);
        System.out.println(nth(a, b, n));
    }
}

- tested.candidate July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Simple Algorithms
Take the mid element of the largest array, and find out the location of that in second array and then compare with N
Here is the formal algorithm

FindNthRankElement(Array1, Array2, N)
    Mid1 = Array1.Mid;
    Mid2 = FindMid1LocationInArray2; // this should be the element which is just smaller to Array1.Mid1
    if(Mid1-Array1.Start + Mid2 - Array2.Start < N)
        Array1 = Array1[Mid1 to Array1.End];
        Array2 = Array2[Mid2 to Array2.End];
        N = N-(Mid1-Array1.Start + Mid2 - Array2.Start);
        Call again
   else if(Mid1-Array1.Start + Mid2 - Array2.Start > N)
        Array1 = Array1[Array1.Start to Mid1];
        Array2 = Array2[Array2.Start to Mid2];
        Call again
   else
       return Array1.Mid1

Complexity is O(Log(N)) Time + O(1) Space

Edit : Complexity : O(Log(n)*Log(n)) Time + O(1) Space

- sonesh July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Due to your 'call again's, your evaluation of Complexity and Memory is incorrect.

- zortlord July 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.) Given two sorted arrays of Size N1 and N2 , you have to find the element at Kth position when both are merged.
2.) Take the element at index k*N1/(N1+N2) from array with size N1
i.e int N1Mid = k*N1/(N1+N2)
Now from second array take int N2Mid = K-N1Mid-1
3.) Now if N1[N1Mid] > N2[N2Mid] , search on right side of second array i.e from N2Mid To End and left side of first array N1Start to N1Mid-1 (like Binary Search) ... reduce k by number of elements left in second array
else do the other way around , seach on right side of first and left side of second reduce K

4.) Keep on doing this recursively

Here is the code

public static int findKth(int A[], int B[], int k, 
	int aStart, int aEnd, int bStart, int bEnd) {
 
	int aLen = aEnd - aStart + 1;
	int bLen = bEnd - bStart + 1;
 
	// Handle special cases
	if (aLen == 0)
		return B[bStart + k];
	if (bLen == 0)
		return A[aStart + k];
	if (k == 0)
		return A[aStart] < B[bStart] ? A[aStart] : B[bStart];
 
	int aMid = aLen * k / (aLen + bLen); // a's middle count
	int bMid = k - aMid - 1; // b's middle count
 
	// make aMid and bMid to be array index
	aMid = aMid + aStart;
	bMid = bMid + bStart;
 
	if (A[aMid] > B[bMid]) {
		k = k - (bMid - bStart + 1);
		aEnd = aMid;
		bStart = bMid + 1;
	} else {
		k = k - (aMid - aStart + 1);
		bEnd = bMid;
		aStart = aMid + 1;
	}
 
	return findKth(A, B, k, aStart, aEnd, bStart, bEnd);
}

- smarthbehl July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MergedArrayService
{
	public static int findNthValue(int[] a, int [] b, int n) throws NullPointerException
	{
		if(a==null||b==null)
		{
			throw new NullPointerException("one or more input arrays is null");
		}
		if(n<0)
		{
			throw new IllegalArgumentException("n must be atleast 0");
		}
		int pa=0;
		int pb=0;
		int pmerge=0;
		int[] merge=new int[n+1];
		while((pa<a.length) && (pb<b.length) &&(pmerge<merge.length))
		{
			
			if(a[pa]<=b[pb])
			{
				merge[pmerge++]=a[pa++];
			}else
			{
				merge[pmerge++]=b[pb++];
			}
			
		}
		while(pa<a.length && pmerge<merge.length)
		{
			merge[pmerge++]=a[pa++];
		}
		while(pb<b.length && pmerge<merge.length)
		{
			merge[pmerge++]=b[pb++];
		}
		return merge[pmerge-1];
	}
	
	public static int[] getInputArray(int n)
	{
		if(n==0)
		{
			return null;
		}
		int[] a=new int[n];
		Random rnd=new Random();
		for(int i=0;i<n;i++)
		{
			a[i]=rnd.nextInt(n);
		}
		return a;
	}
	
	public static void main(String[] args)
	{
		Random rnd=new Rnadom();
		int n=rnd.nextInt(101);
		int[] a=MergedArrayService.getInputArray(n);
		n=rnd.nextInt(101);
		int[] b=MergedArrayService.getInputArray(n);
		System.out.println("a: " + Arrays.toString(a));
		System.out.println("b: " + Arrays.toString(b));
		int k=MergedArrayService.findNthValue(a,b,rnd.nextInt(a.length+b.length));
		System.out.println("nth value: " + k);
	}
		
		
}

//O(n) time and O(n) space--where n is the rank of the element we are interested in finding.

- divm01986 July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int? FindNthElement(int[] a1, int[] a2, int n)
{
	if (a1 == null || a2 == null ||  n < 0 || (a1.Length + a2.Length) <= n)
		return null;

	int i = 0;
	int j = 0;

	while (true)
	{
		if (i + j == n)
			break;

		if (j >= a2.Length || i < a1.Length && a1[i] < a2[j])
			i++;
		else
			j++;
	}

	return (j >= a2.Length || i < a1.Length && a1[i] < a2[j]) ? a1[i] : a2[j];
}

- hnatsu July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void mergeSort(int oneArr[SIZE1],int twoArr[SIZE2],int n)
{
	int resArr[SIZE3] = {0};
	int j=0,k=0,i=0;

	while(i<SIZE1 || k<SIZE2)
	{
		if(i>=SIZE1)
			resArr[j] = twoArr[k];

		if(k>=SIZE2)
			resArr[j] = oneArr[i];
		
		if(j==n)
		{
			cout << n << "th element is "<< resArr[j];
			return;
		}
		if(oneArr[i] < twoArr[k])
		{
			resArr[j] = oneArr[i];
			i++;
		}
		else
		{
			resArr[j] = twoArr[k];
			k++;
		}
		j++;
	}
}

- sv July 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Operates with runtime complexity of O(k) and memory O(1) where k is the position in the merged array:

public static int getMergedValue(int[] arr1, int[] arr2, int k){
    //check for illegal inputs
    if(arr1 == null || arr2 == null){
        throw new NullPointerException();
    }
    if(k >= arr1.length + arr2.length){
        throw new IllegalArgumentException();
    }
    
    //'merge' the arrays
    int pos = 0;
    int arr1Pos = 0;
    int arr2Pos = 0;
    while(pos < k && arr1Pos < arr1.length && arr2Pos < arr2.length){
        if(arr1[arr1Pos] < arr2[arr2Pos]){
            arr1Pos++;
        }
        else {
            arr2Pos++;
        }
        pos ++;
    }
    //if one or the other array is exhausted
    if(pos < k){
        if(arr1Pos < arr1.length){
            arr1Pos += (k - pos);
            return arr1[arr1Pos];
        }
        else{
            arr2Pos += (k - pos);
            return arr2[arr2Pos];
        }
    }
    //return the smallest of the current positions in the array
    if(arr1[arr1Pos] < arr2[arr2Pos]){
        return arr1[arr1Pos];
    }
    return arr2[arr2Pos];
}

- zortlord July 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) time:
2 pointers, one for arr A, one for arr B
while (i<n) increment whichever pointer is smaller
At n, return smaller of two pointers.

- Eugen Hotaj November 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Sample solution in C++. O(K) where K is the desired order.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int getNth(const vector<int>& a, const vector<int>& b, int n) {
  if (a.size() + b.size() < n) return -1;

  auto itrA = a.begin();
  auto itrB = b.begin();

  if (itrA == a.end()) return *(itrB + n-1);
  if (itrB == b.end()) return *(itrA + n-1);

  for (int i = 0; i < n - 1; ++i) {
    if (*itrA < *itrB) {
      ++itrA;
    } else {
      ++itrB;
    }
  }
  
  return min(*itrA, *itrB);
}

int main() {
  vector<int> a {1,3,4,5,8};
  vector<int> b {};

  int nth = getNth(a, b, 4);
  cout << nth << endl;

  return 0;
}

- Anonymous August 06, 2015 | 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