Google Interview Question Interns
Country: United States
Interview Type: Phone Interview
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);
}
}
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)
@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 :)
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
#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;
}
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} )" );
}
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);
}
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);
}
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;
}
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);
}
}
@Fernando
Your second solution is not correct.
For example, with
A = { 1, 3 } B = { 4, 5 } K = 2Your solution outputs { (1,4), (3,4) } instead of { (1,4), (1,5) }.
- BruGo August 05, 2017