## Google Interview Question for Interns

• 3

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) }.

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) }.

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) }.

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

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 {
}

// 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]);
}
if (curState.pB + 1 < B.length) {
State nextState = new State(curState);
nextState.pB ++;
nextState.pair = new Pair(A[nextState.pA], B[nextState.pB]);
}

}
}``````

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)

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 :)

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)]

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];
//add the first one from both arrays to the result

//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;
}

return result;
}``````

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];
//add the first one from both arrays to the result

//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;
}

return result;
}``````

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];
//add the first one from both arrays to the result

//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;
}

return result;
}``````

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];
//add the first one from both arrays to the result

//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;
}

return result;
}``````

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];
//add the first one from both arrays to the result

//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;
}

return result;
}``````

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];
//add the first one from both arrays to the result

//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;
}

return result;
}

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

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;
}``````

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

This solution is totally wrong. Run it for K = 10. The correct output (sums): {2, 3, 4, 5, 6, 6, 7, 7, 7, 8}. This solution outputs: {2, 3, 4, 5, 6, 7, 8, 2, 2, 11}. Nonsense.

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;
}``````

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 );
}

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} )" );
}``````

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);
}``````

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);
}``````

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<>();

int aIndex = 0;
int bIndex = 0;
while(res.size() < k) {
if(a[aIndex + 1] < b[bIndex + 1]) {
aIndex++;
}
else {
aIndex = 0;
bIndex += 1;
}

}

return res;
}``````

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

C++ solution:

``````template<class It, class Fn>
void smallest_pair_sums(It first1, It last1, It first2, It last2, std::size_t n, Fn fn) {
using Heap_node = std::pair<It, It>;
using Set_node  = std::pair<std::ptrdiff_t, std::ptrdiff_t>;

struct Comparator {
bool operator()(Heap_node p1, Heap_node p2) const {
return *p2.first + *p2.second < *p1.first + *p1.second;
}
};

struct Hash {
std::size_t operator()(Set_node p) const {
return std::hash<Set_node::first_type>{}(p.first) ^ std::hash<Set_node::second_type>{}(p.second);
}
};

std::priority_queue<Heap_node, std::vector<Heap_node>, Comparator> min_heap;
std::unordered_set<Set_node, Hash> set;

const auto insert = [&](auto it1, auto it2) {
const Set_node key{it1 - first1, it2 - first2};
if (it1 != last1 && it2 != last2 && set.count(key) == 0) {
min_heap.emplace(it1, it2);
set.insert(key);
}
};

insert(first1, first2);
while (!min_heap.empty() && n-- > 0) {
const auto [it1, it2] = min_heap.top();
min_heap.pop();

fn(it1, it2);

insert(it1 + 1, it2);
insert(it1, it2 + 1);
}
}``````

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.