Google Interview Question for Interns


Country: United States
Interview Type: Phone Interview




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

@Fernando
Your second solution is not correct.

For example, with

A = { 1, 3 }
B = { 4, 5 }
K = 2

Your solution outputs { (1,4), (3,4) } instead of { (1,4), (1,5) }.

- BruGo August 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Fernando,
Your second solution is not correct.

For example, with

A = { 1, 3 }
B = { 4, 5 }
K = 2

Your solution outputs { (1,4), (3,4) } instead of { (1,4), (1,5) }.

- BruGo August 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Fernando
Your second solution is not correct.

For example, with

A = { 1, 3 }
B = { 4, 5 }
K = 2

Your solution outputs { (1,4), (3,4) } instead of { (1,4), (1,5) }.

- BruGo August 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a O(Klog(K)) recursive solution.

import java.util.*;

class State implements Comparable<State> {

	// pointers
	public int pA;
	public int pB;

	public Pair pair;

	public State(int pA, int pB, Pair pair) {
		this.pA = pA;
		this.pB = pB;
		this.pair = pair;
	}
	public State(State s) {
		this.pA = s.pA;
		this.pB = s.pB;
		this.pair = s.pair;
	}

	@Override
    public int compareTo(State s) {
        return pair.sum - s.pair.sum;
    }
}

class Pair {
	public int val1;
	public int val2;
	public int sum;

	public Pair(int val1, int val2) {
		this.val1 = val1;
		this.val2 = val2;
		sum = val1 + val2;
	}

	public String toString() {
		return "(" + val1 + ", " + val2 + ")";
	}
}

public class MinPairsGenerator {

	public static void main(String[] args) {
		int[] A = {1,2,3,6,10};
		int[] B = {1,4,5,7};
		int K = 5;
		ArrayList<Pair> minPairs = getMinPairs(A, B, K);
		for (Pair p: minPairs) {
			System.out.println(p);
		}
	}

	static ArrayList<Pair> getMinPairs(int[] A, int[] B, int K) {
		ArrayList<Pair> minPairs = new ArrayList<Pair>();

		// handle corner case
		if (A.length == 0 || B.length == 0)
			return minPairs;

		PriorityQueue<State> queue = new PriorityQueue<State>(A.length * B.length);

		// add first min sum pair
		queue.add(new State(0, 0, new Pair(A[0], B[0])));
		
		// recursively find min pairs
		addPairs(A, B, minPairs, queue, K);

		return minPairs;
	}

	static void addPairs(int[] A, int[] B, ArrayList<Pair> minPairs, PriorityQueue<State> queue, int K) {

		// base case
		if (K == 0)
			return;

		State curState = queue.poll();
		
		if (curState == null) // no more pairs
			return;
		else {
			minPairs.add(curState.pair);
		}

		// create new pairs from the current one
		// by moving a pointer forward
		if (curState.pA + 1 < A.length) {
			State nextState = new State(curState);
			nextState.pA ++;
			nextState.pair = new Pair(A[nextState.pA], B[nextState.pB]);
			queue.add(nextState);
		}
		if (curState.pB + 1 < B.length) {
			State nextState = new State(curState);
			nextState.pB ++;
			nextState.pair = new Pair(A[nextState.pA], B[nextState.pB]);
			queue.add(nextState);
		}
		
		addPairs(A, B, minPairs, queue, K-1);
	}
}

- BruGo August 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution is n*log(maxSum)*log(m).
Binary search on range (A[0]+B[0],A[n-1]+B[m-1]).
We get the mid_sum = (low + high)/2
total = 0
For each element a in A, use second binary search to find number of elements in B which <= mid_sum - a, add that number to total.
If low == high, then return the pairs from above loop.
if(total >= K) binary search on (low, mid_sum), otherwise binary search on (mid_sum+1, high)

- anonymous August 05, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Brugo I know I realized I got the indexes not working correctly and removed the comment as I didn't have time to fix the code but the web page didn't update until several hours later. Great answer using a queue to keep sorted the pairs. Anyway, as both arrays are sorted you can provide a solution in O(k)

Naive solution O(a*b)

from iterttools import product

def smallKPairs(K, a, b):
        return sorted(product(a, b), key=sum)[:K]

Solution in O(K)

def smallKPairs(K, a, b):
        f_a, f_b = 0, 0
        l_a, l_b, c_a, c_b = 0, 0, 0, 0
        pairs = []
        while (len(pairs) < K):
                pairs.append((a[c_a], b[c_b]))
                f_a += 1
                if f_a == len(a):
                        l_a += 1
                        f_a = l_a
                f_b += 1
                if f_b == len(b):
                        l_b += 1
                        f_b = l_b
                if a[l_a] + b[f_b] <= a[f_a] + b[l_b]:
                        c_a = l_a
                        c_b = f_b
                        f_a -= 1
                else:
                        c_a = f_a
                        c_b = l_b
                        f_b -= 1
        return pairs

Cheers :)

- Fernando August 06, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution is wrong.
>>> a
[1, 2, 3, 6, 10]
>>> b
[1, 4, 5, 7, 10]
>>> print smallKPairs(6,a,b)
[(1, 1), (2, 1), (3, 1), (1, 4), (1, 5), (6, 1)]

and result should be [(1, 1), (2, 1), (3, 1), (1, 4), (1, 5), (2, 4)]

- Archit Goel August 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my O(k) solution. The key is to create a cache for processed A items and keep increasing A until it is less than B.

public static List<Tuple<Integer>> getSmallestSums(int[] a, int[] b, int k) {
        //cache tp keep track of last processed item from array a
        int[] cache = new int[a.length];
        List<Tuple<Integer>> result = new LinkedList<>();
        //add the first one from both arrays to the result
        result.add(new Tuple<>(a[0], b[0]));

        //add the first b to the cache since it was already processed
        cache[0] +=1;
        
        //array shit indexes
        int aIndex = 0;
        int bIndex = 0;
        
        //fill the result
        while(result.size() < k) {
            if(a[aIndex + 1] <= b[bIndex + 1]) {
                aIndex++; //if item in array a is less than b, increment it
            } else {
                aIndex = 0; //otherwise reset back to 0
            }
            //get the next stem in the cache
            bIndex = cache[aIndex];
            //increment step in the cache
            cache[aIndex] +=1;
            result.add(new Tuple<>(a[aIndex], b[bIndex]));
        }

        return result;
    }

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

O(k) solution

public static List<Tuple<Integer>> getSmallestSums(int[] a, int[] b, int k) {
        //cache tp keep track of last processed item from array a
        int[] cache = new int[a.length];
        List<Tuple<Integer>> result = new LinkedList<>();
        //add the first one from both arrays to the result
        result.add(new Tuple<>(a[0], b[0]));

        //add the first b to the cache since it was already processed
        cache[0] +=1;
        
        //array shit indexes
        int aIndex = 0;
        int bIndex = 0;
        
        //fill the result
        while(result.size() < k) {
            if(a[aIndex + 1] <= b[bIndex + 1]) {
                aIndex++; //if item in array a is less than b, increment it
            } else {
                aIndex = 0; //otherwise reset back to 0
            }
            //get the next stem in the cache
            bIndex = cache[aIndex];
            //increment step in the cache
            cache[aIndex] +=1;
            result.add(new Tuple<>(a[aIndex], b[bIndex]));
        }

        return result;
    }

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

public static List<Tuple<Integer>> getSmallestSums(int[] a, int[] b, int k) {
        //cache tp keep track of last processed item from array a
        int[] cache = new int[a.length];
        List<Tuple<Integer>> result = new LinkedList<>();
        //add the first one from both arrays to the result
        result.add(new Tuple<>(a[0], b[0]));

        //add the first b to the cache since it was already processed
        cache[0] +=1;
        
        //array shit indexes
        int aIndex = 0;
        int bIndex = 0;
        
        //fill the result
        while(result.size() < k) {
            if(a[aIndex + 1] <= b[bIndex + 1]) {
                aIndex++; //if item in array a is less than b, increment it
            } else {
                aIndex = 0; //otherwise reset back to 0
            }
            //get the next stem in the cache
            bIndex = cache[aIndex];
            //increment step in the cache
            cache[aIndex] +=1;
            result.add(new Tuple<>(a[aIndex], b[bIndex]));
        }

        return result;
    }

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

O(k) solution

public static List<Tuple<Integer>> getSmallestSums(int[] a, int[] b, int k) {
        //cache tp keep track of last processed item from array a
        int[] cache = new int[a.length];
        List<Tuple<Integer>> result = new LinkedList<>();
        //add the first one from both arrays to the result
        result.add(new Tuple<>(a[0], b[0]));

        //add the first b to the cache since it was already processed
        cache[0] +=1;
        
        //array shit indexes
        int aIndex = 0;
        int bIndex = 0;
        
        //fill the result
        while(result.size() < k) {
            if(a[aIndex + 1] <= b[bIndex + 1]) {
                aIndex++; //if item in array a is less than b, increment it
            } else {
                aIndex = 0; //otherwise reset back to 0
            }
            //get the next stem in the cache
            bIndex = cache[aIndex];
            //increment step in the cache
            cache[aIndex] +=1;
            result.add(new Tuple<>(a[aIndex], b[bIndex]));
        }

        return result;
    }

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

O(k) solution

public static List<Tuple<Integer>> getSmallestSums(int[] a, int[] b, int k) {
        //cache tp keep track of last processed item from array a
        int[] cache = new int[a.length];
        List<Tuple<Integer>> result = new LinkedList<>();
        //add the first one from both arrays to the result
        result.add(new Tuple<>(a[0], b[0]));

        //add the first b to the cache since it was already processed
        cache[0] +=1;
        
        //array shit indexes
        int aIndex = 0;
        int bIndex = 0;
        
        //fill the result
        while(result.size() < k) {
            if(a[aIndex + 1] <= b[bIndex + 1]) {
                aIndex++; //if item in array a is less than b, increment it
            } else {
                aIndex = 0; //otherwise reset back to 0
            }
            //get the next stem in the cache
            bIndex = cache[aIndex];
            //increment step in the cache
            cache[aIndex] +=1;
            result.add(new Tuple<>(a[aIndex], b[bIndex]));
        }

        return result;
    }

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

public static List<Tuple<Integer>> getSmallestSums(int[] a, int[] b, int k) {
//cache tp keep track of last processed item from array a
int[] cache = new int[a.length];
List<Tuple<Integer>> result = new LinkedList<>();
//add the first one from both arrays to the result
result.add(new Tuple<>(a[0], b[0]));

//add the first b to the cache since it was already processed
cache[0] +=1;

//array shit indexes
int aIndex = 0;
int bIndex = 0;

//fill the result
while(result.size() < k) {
if(a[aIndex + 1] <= b[bIndex + 1]) {
aIndex++; //if item in array a is less than b, increment it
} else {
aIndex = 0; //otherwise reset back to 0
}
//get the next stem in the cache
bIndex = cache[aIndex];
//increment step in the cache
cache[aIndex] +=1;
result.add(new Tuple<>(a[aIndex], b[bIndex]));
}

return result;
}

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

Why comments don't show up?

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

O(K) solution in C++.

MinList firstK(vector<int> a, vector<int> b, int k) {
  assert(k <= a.size() * b.size());
  if (k == 0) {
    return MinList();
  }

  int aBase = 0;
  int bBase = 0;

  int aCounter = 0;
  int bCounter = 0;

  MinList minVec;
  minVec.emplace_back(make_pair(a[0], b[0]));

  while (minVec.size() != k) {
    if (aCounter + 1 == a.size()) {                                                                                            
      ++bBase;
    }
    if (bCounter + 1 == b.size()) {
      ++aBase;
    }
    const int amoved = a[aCounter + 1] + b[0];
    const int bmoved = a[0] + b[bCounter + 1];
    if (amoved <= bmoved) {
      ++aCounter;
      minVec.emplace_back(make_pair(a[aCounter], b[bBase]));
    } else {
      ++bCounter;
      minVec.emplace_back(make_pair(a[aBase], b[bCounter]));
    }
  }

  return minVec;
}

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

#include <vector>
#include <iostream>

using namespace std;

vector <pair<int, int>> MinPairs(vector<int> const &a1, vector<int> const &a2, int k)
{
	vector<pair<int, int>> out;

	if (k > 0 &&
		a1.size() * a2.size() >= k)
	{
		int start1 = 0;
		int start2 = 0;
		int i = 0;
		int j = 0;
		while (out.size() < k) {
			int idx1 = -1;
			int idx2 = -1;

			if (start1 + 1 < a1.size() &&
				a1[start1 + 1] + a2[0] < a2[start2] + a1[i] &&
				a1[start1 + 1] + a2[0] < a1[start1] + a2[j])
			{
				++start1;
				idx1 = start1;
				idx2 = 0;
				j = 0;
			} else if (start2 + 1 < a2.size() &&
				a2[start2 + 1] + a1[0] < a1[start1] + a2[j] &&
				a2[start2 + 1] + a1[0] < a2[start2] + a1[i])
			{
				++start2;
				idx1 = 0;
				idx2 = start2;
				i = 0;
			} else if (a1[start1] + a2[j] < a2[start2] + a1[i]) {
				idx1 = start1;
				idx2 = j++;
				if (j >= a2.size()) {
					j = 0;
					++start1;
				}
			} else {
				idx1 = i++;
				idx2 = start2;
				if (i >= a1.size()) {
					i = 0;
					++start2;
				}
			}

			if (out.empty() ||
				out.back().first != idx1 ||
				out.back().second != idx2)
			{
				out.push_back(pair<int, int>(idx1, idx2));
			}
		}
	}
	return out;
}

int main(int argvc, char const **argv)
{
	vector<int> a1 = {1, 2, 3, 6, 10};
	vector<int> a2 = {1, 4, 5, 7};

    vector<pair<int, int>> out = MinPairs(a1, a2, 5);
	for (auto el : out) {
		cout << a1[el.first] << ", " << a2[el.second] << " => " << (a1[el.first] + a2[el.second]) << "\n";
	}
    return 0;
}

- Alex August 31, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

static void Main( string[] args )
        {
            int[] A = { 1, 2, 3, 6, 10 };
            int[] B = { 1, 4, 5, 7 };

            int k = 12;

            findMinSumPair( A, B, k );
            Console.ReadLine();
        }

        public class pairComparer : IComparer<Tuple<int, int>>
        {
            public int Compare( Tuple<int, int> x, Tuple<int, int> y )
            {
                if ( x.Item1 + x.Item2 < y.Item1 + y.Item2 )
                    return -1;
                else if ( x.Item1 + x.Item2 > y.Item1 + y.Item2 )
                    return 1;

                return 0;
            }
        }

        static void findMinSumPair( int[] A, int[] B, int k )
        {
            List<Tuple<int, int>> all = new List<Tuple<int, int>>();

             int i = 0, j = 0;
            while ( all.Count() < k )
            {
                for ( int l = j; l < B.Count(); ++l )
                    all.Add( Tuple.Create( A[i], B[l] ) );
                for ( int l = i + 1; l < A.Count(); ++l )
                {
                        all.Add( Tuple.Create( A[l], B[j] ) );
                }

                all.Sort( new pairComparer() );

                i++;
                j++;
            }

            for( int l = 0; l < k; ++l )
                Console.WriteLine( $"( {all.ElementAt(l).Item1}, {all.ElementAt( l ).Item2} )" );
        }

- TGoofnik September 09, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Complexity - O(k) and no extra space -

public static void main(String args[]) {
        int[] A = {1, 2, 3, 6, 10};
        int[] B = {1, 4, 5, 7};
        int k = 5; 
        print(A, B, k, 0, 0, 1, 1);   
    }
    
    public static void print(int[] A, int[] B, int k, int i, int j, int p, int q){
        int n = A.length;
        int m = B.length;
        
        System.out.print("("+A[i] + ", " + B[j]+") ");
        
        while(k > 1 && i < n && p < n && j < m && q < m){
            while(k > 1 && i < n && p < n && j < m && q < m && A[i] + B[q] < A[p] + B[j]){
                System.out.print("("+A[i] + ", " + B[q]+") ");
                q++;
                k--;
            }
            while(k > 1 && i < n && p < n && j < m && q < m && A[p] + B[j] < A[i] + B[q]){
                System.out.print("("+A[p] + ", " + B[j]+") ");
                p++;
                k--;
            }
        }
        if(k > 1 && i < n && p < n && j < m && q < m)
            print(A, B, k, i, j, p, q);
    }

- Anonymous October 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

complexity - O(k) & no extra space -

public static void main(String args[]) {
        int[] A = {1, 2, 3, 6, 10};
        int[] B = {1, 4, 5, 7};
        int k = 5; 
        print(A, B, k, 0, 0, 1, 1);   
    }
    
    public static void print(int[] A, int[] B, int k, int i, int j, int p, int q){
        int n = A.length;
        int m = B.length;
        
        System.out.print("("+A[i] + ", " + B[j]+") ");
        
        while(k > 1 && i < n && p < n && j < m && q < m){
            while(k > 1 && i < n && p < n && j < m && q < m && A[i] + B[q] < A[p] + B[j]){
                System.out.print("("+A[i] + ", " + B[q]+") ");
                q++;
                k--;
            }
            while(k > 1 && i < n && p < n && j < m && q < m && A[p] + B[j] < A[i] + B[q]){
                System.out.print("("+A[p] + ", " + B[j]+") ");
                p++;
                k--;
            }
        }
        if(k > 1 && i < n && p < n && j < m && q < m)
            print(A, B, k, i, j, p, q);
    }

- sudip.innovates October 08, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't think you'd need a new array to keep track of the bIndex. Here's a simpler solution:

private List<int[]> getSmallestSums(int[] a, int[] b, int k) {
        List<int[]> res = new ArrayList<>();
        res.add(new int[]{a[0], b[0]});
        
        int aIndex = 0;
        int bIndex = 0;
        while(res.size() < k) {
            if(a[aIndex + 1] < b[bIndex + 1]) {
                aIndex++;
            }
            else {
                aIndex = 0;
                bIndex += 1;
            }

            res.add(new int[]{a[aIndex], b[bIndex]});
        }

        return res;
    }

- Hugh May 26, 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