Google Interview Question
Software Engineer / DevelopersTeam: Hangouts
Country: United States
Interview Type: In-Person
Here's the implementation in c++
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
class triple {
public:
int a;
int b;
int c;
triple(int x,int i, int j) : a(x), b(i), c(j) {}
};
void printTripleList(list<triple> &l)
{
for (list<triple>::const_iterator it = l.begin(), end = l.end(); it != end; ++it)
{
printf("{%d, %d, %d}\n", it->a, it->b, it->c);
}
printf("\n\nlist size: %lu\n\n", l.size());
}
void printVector(const vector<int> &n)
{
int size = n.size();
for(int i = 0; i < size; i++)
{
printf("%d\n",n[i]);
}
printf("\n\nvector size: %d\n\n", size);
}
list<triple> find3Sum(vector<int> n, const int NUMS, const int d)
{
list<triple> solutions;
sort (n.begin(), n.end());
printf("After Sorting\n");
printVector(n);
int a_index = 0;
int b_index = 1;
int c_index = NUMS - 1;
while(a_index < c_index)
{
if (b_index >= c_index)
{
a_index++;
b_index = a_index + 1;
}
else if(n[a_index] + n[b_index] + n[c_index] > d)
{
c_index--;
}
else {
for(int i = b_index+1; i <= c_index; i++)
{
triple sol(n[a_index], n[b_index], n[i]);
solutions.push_back(sol);
}
b_index++;
}
}
return solutions;
}
int main()
{
int n = 7;
int d = 7;
vector<int> input(n) ;
for(int i = 0; i < n; i++)
{
input[i] = n - i;
}
printf("n: %d, d: %d\n", n,d);
printf("Input\n");
printVector(input);
list<triple> solutions = find3Sum(input, n, d);
printf("SOLUTIONS\n");
printTripleList(solutions);
return 0
}
int d = 7;
vector<int> in = { 2, 3, 1, 4, 7, 5, 6 };
sort(in.begin(), in.end());
for (int i = 0; i < in.size() - 2; ++i)
{
if (in[i] + in[i+1] + in[i + 2] > d) {
break;
}
for (int j = i + 1; j < in.size() - 1; ++j)
{
if (in[i] + in[j] + in[j + 1] > d) {
break;
}
for (int k = j + 1; k < in.size(); ++k) {
if (in[i] + in[j] + in[k] <= d) {
cout << in[i] << " " << in[j] << " " << in[k] << endl;
}
else {
break;
}
}
}
}
Brute Force? There doesn't seem to be any restriction on complexity or space?
int[] input = { 1, 2, 3, 4, 5, 6, 7 };
int d = 7;
for ( int a_index = 0; a_index < input.length; a_index++ ) {
int a = input[a_index];
for ( int b_index = a_index + 1; b_index < input.length; b_index++ ) {
int b = input[b_index];
for ( int c_index = b_index + 1; c_index < input.length; c_index++ ) {
int c = input[c_index];
if (( a + b + c ) <= d) {
System.out.println("(" + a + ", " + b + ", " + c + ")" );
}
}
}
}
I think the million integers indicates complexity should be atmost nlogn.
Yours is way too slow O(n^3).
package com.test.four;
import java.util.ArrayList;
import java.util.Iterator;
public class Test4 {
public static void main(String[] args) {
// store the result
ArrayList<Integer[]> ret = new ArrayList<Integer[]>();
// the value of total sum which you can change
final int SET = 10;
// input
Integer[] aa = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
for (int i = 0; i < aa.length; i++) {
for (int j = i + 1; j < aa.length; j++) {
for (int k = j + 1; k < aa.length; k++) {
if (aa[i] + aa[j] + aa[k] <= SET) {
try {
ret.add(new Integer[] { aa[i], aa[j], aa[k] });
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
}
// confirm the results
for (int i = 0; i < ret.size(); i++) {
Iterator<Integer[]> it = (Iterator<Integer[]>) ret.iterator();
while (it.hasNext()) {
Integer temp[] = (Integer[]) it.next();
System.out.print("[");
for (int j = 0; j < temp.length; j++) {
if (j == 0 || j == 1)
System.out.print(temp[j] + ", ");
else
System.out.print(temp[j]);
}
System.out.println("]");
}
}
}
}
package com.test.four;
import java.util.ArrayList;
import java.util.Iterator;
public class Test4 {
public static void main(String[] args) {
// store the result
ArrayList<Integer[]> ret = new ArrayList<Integer[]>();
// the value of total sum which you can change
final int SET = 10;
// input
Integer[] aa = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
for (int i = 0; i < aa.length; i++) {
for (int j = i + 1; j < aa.length; j++) {
for (int k = j + 1; k < aa.length; k++) {
if (aa[i] + aa[j] + aa[k] <= SET) {
try {
ret.add(new Integer[] { aa[i], aa[j], aa[k] });
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
}
// confirm the results
for (int i = 0; i < ret.size(); i++) {
Iterator<Integer[]> it = (Iterator<Integer[]>) ret.iterator();
while (it.hasNext()) {
Integer temp[] = (Integer[]) it.next();
System.out.print("[");
for (int j = 0; j < temp.length; j++) {
if (j == 0 || j == 1)
System.out.print(temp[j] + ", ");
else
System.out.print(temp[j]);
}
System.out.println("]");
}
}
}
}
package com.test.four;
import java.util.ArrayList;
import java.util.Iterator;
public class Test4 {
public static void main(String[] args) {
// store the result
ArrayList<Integer[]> ret = new ArrayList<Integer[]>();
// the value of total sum which you can change
final int SET = 10;
// input
Integer[] aa = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
for (int i = 0; i < aa.length; i++) {
for (int j = i + 1; j < aa.length; j++) {
for (int k = j + 1; k < aa.length; k++) {
if (aa[i] + aa[j] + aa[k] <= SET) {
try {
ret.add(new Integer[] { aa[i], aa[j], aa[k] });
} catch (Exception e) {
e.printStackTrace();
}
}
}
}
}
// confirm the results
for (int i = 0; i < ret.size(); i++) {
Iterator<Integer[]> it = (Iterator<Integer[]>) ret.iterator();
while (it.hasNext()) {
Integer temp[] = (Integer[]) it.next();
System.out.print("[");
for (int j = 0; j < temp.length; j++) {
if (j == 0 || j == 1)
System.out.print(temp[j] + ", ");
else
System.out.print(temp[j]);
}
System.out.println("]");
}
}
}
}
While O(n^3) is indeed a correct bound, its not the tightest bound (just like how any O(n) algorithm is also O(n^2)).
Following algorithm should do the job. It relies on the following basic idea: If a+b+c <= d, then c <= d-(a+b).
Sort the array. This is O(nlogn). Then for every pair of indices (i, j), compute offset(i,j) = d - a(i) - a(j). Search the array for the largest index k, such that a(k) <= offset(i, j). This can be done by binary search, modified into linear search in case of duplicate matches in the array. When there are few duplicate matches, which is quite common, the runtime would be O(n^2 logn).
Remember that it is not necessary to print all triplets as output of the program. The following compressed output would suffice. Print the sorted array, and all triplets of the form (a(i), a(j), k) such that k is the largest index for which a(k) <= offset(i, j).
Check out code below. However, it does not print out the output in compressed form.
#include <iostream>
#include <stdlib.h>
#include <time.h>
int compare (void const * a, void const * b)
{
return ( *(int*)a - *(int*)b );
}
int binary_search(int * arr, int n, int val)
{
int first = 0;
int last = n-1;
int a = first, b = last;
while (a <= b)
{
int mid = a + (b-a)/2;
if (arr[mid] < val)
{
if (mid == last || (mid+1 < n && arr[mid+1] > val))
{
return mid;
}
a = mid+1;
}
else if (arr[mid] > val)
{
b = mid-1;
}
else
{
// val found
// have to find the rightmost occurrence (linear search)
while (++mid < n && arr[mid] == val);
return mid - 1;
}
}
return -1;
}
int main(int argc, char ** argv)
{
int len = 10, range = 25, d = 15;
if (argc > 1)
{
len = atoi(argv[1]);
}
if (argc > 2)
{
range = atoi(argv[2]);
}
if (argc > 3)
{
d = atoi(argv[3]);
}
srand(time(NULL));
int arr[len];
for (int i = 0; i < len; ++i)
{
int r = rand() % range - range/2;
arr[i] = r;
std::cout << r << " ";
}
std::cout << std::endl;
// Sort the array
qsort(arr, len, sizeof(int), compare);
std::cout << "Sorted array is as follows.." << std::endl;
for (int i = 0; i < len; ++i)
{
std::cout << arr[i] << " ";
}
std::cout << std::endl;
// Find all pair sums (offset by d)
for (int i = 0; i < len - 1; ++i)
{
for (int j = i+1; j < len; ++j)
{
int offsetSum = d - arr[i] - arr[j];
int indexOfOffsetSum = binary_search(arr, len, offsetSum);
if (indexOfOffsetSum >= 0)
{
for (int k = 0; k <= indexOfOffsetSum; ++k)
{
if (k != i && k != j)
{
std::cout << "("
<< arr[i] << "+"
<< arr[j] << "+"
<< arr[k] << ") = "
<< arr[i] + arr[j] + arr[k]
<< std::endl;
}
}
}
}
}
return 0;
}
Million integer numbers that is not a big deal. It is only 4Mb memory.
Sort it in memory nLogn and just print all triplets before sum reaches d with no overhead at all.
void print_all_triplets(int arr[], int len, int d) {
sort(arr, len);
for (int a = 0; a < len && arr[a] < d ; a++) {
for (int b = a+1; b < len && arr[a]+arr[b] < d; b++) {
for (c = b+1; c < len && arr[a]+arr[b]+arr[c] <= d; c++) {
printf("%d, %d, %d\n", arr[a], arr[b], arr[c]);
}
}
}
}
#include<iostream>
using namespace std;
int main(){
int aa[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int size =10;
int d =15;
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size-1; j++) {
for (int k = j + 1; k < size-2; k++) {
if (aa[i] + aa[j] + aa[k] <= d) {
cout<<aa[i]<<" "<<aa[j]<<" "<<aa[k];
cout<<endl;
}
}
}
}
return 0;
}
O(n^2) algorithm:
Firstly sort array with O(nlogn)
for( k=0; k<n ;k++){
i = 0; j = n-1;
while( i<n && j>=0 ){
if( a[i] + a[j] + a[k] <= d ){
system.out.println (a[i] +" "+ a[j] + " "+ a[k]);
i++;j--;
}
else if( a[i] + a[j] + a[k] > d ){
j--
}
else
i++;
}
}
also for handling duplicates we can maintain hash table.
Please do comment if you find anything wrong!!
There can't be a worst case O(n^2) algorithm. Printing the output in worst case is O(n^3). Consider the case when, d = Integer.MAX_VALUE and array [1, 2, 3, .. 1000,000]. All possible subset of size 3 will be answer.
Although if the problem is to print the number of such 3 tuple, then I can think of a simple O(n^2log n) algorithm :-
sorted_array <- input.sort()
pairs <- All pair s.t pair.first + pair.second < d // O(n^2)
count <- 0
for pair in pairs:-
idx <- sorted_array.bsearch(d - pair.first - pair.second)
count <- count + idx - pair.first.index
count
inputing the sorted array.
1) to sort the array complexity would be NlogN
2) choosing A, complexity would be N
3) choosing B, complexity would be again N.
4) choosing C, max number such that c<=d-a-b
overall complexity would be NlogN + N^2logN = N^2logN
sum3([] arr, index, D, nth, List<int>AB)
{
if(nth==1)
{
c=binarySearch(arr, D)
for(int i=c;i>=0;i--) print(AB, arr[i])
}
else
{
List<int> AB = new List<int>();
for(int i=index;i>0; i--)
{
if(D<arr[i]) continue;
sum3(arr, i, nth-1, AB.add(arri[i]));
}
AB.remove(arr[i]);
}
}
inputing the sorted array.
1) to sort the array complexity would be NlogN
2) choosing A, complexity would be N
3) choosing B, complexity would be again N.
4) choosing C, max number such that c<=d-a-b
overall complexity would be NlogN + N^2logN = N^2logN
sum3([] arr, index, D, nth, List<int>AB)
{
if(nth==1)
{
c=binarySearch(arr, D)
for(int i=c;i>=0;i--) print(AB, arr[i])
}
else
{
List<int> AB = new List<int>();
for(int i=index;i>0; i--)
{
if(D<arr[i]) continue;
sum3(arr, i, nth-1, AB.add(arri[i]));
}
AB.remove(arr[i]);
}
}
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package myPrograms;
import java.util.Arrays;
import java.util.Scanner;
public class Find3NumbersWhoseSumLessthanGiven {
public Find3NumbersWhoseSumLessthanGiven() {
super();
}
private static int findFirstRightLessThanNumber(int input[],int left,int right,int D){
int N=input.length;
if(left<0||left == N||right <0||right == N){
return -1;
}
int mid,temp;
if(left == right){
if(input[left]>D){
return -1;
}else{
return left;
}
}else{
mid=(left+right)/2;
if(input[mid]>D){
right=mid-1;
return findFirstRightLessThanNumber(input,left,right,D);
}else {
temp=findFirstRightLessThanNumber(input,mid+1,right,D);
if(temp == -1){
return mid;
}else{
return temp;
}
}
}
}
public static void printNumbers(int[]inputArray,int D){
Arrays.sort(inputArray);
int N=inputArray.length;
int third;
int second;
int first;
int x,y,z;
third=findFirstRightLessThanNumber(inputArray,0,N-1,D);
if(third==-1){
return;
}
for( x=third;x>1;x--){
second=findFirstRightLessThanNumber(inputArray, 0, third-1, D-inputArray[x]);
if(second == -1){
continue;
}else{
for(y=second;y>0;y--){
first=findFirstRightLessThanNumber(inputArray, 0, second-1, D-inputArray[x]-inputArray[y]);
if(first == -1){
continue;
}else{
for(z=0;z<=first;z++){
System.out.println(inputArray[z]+" "+ inputArray[y]+" "+inputArray[x]);
}
}
}
}
}
}
public static void main(String[] args) {
System.out.println("Enter Size of Integer Array");
Scanner scn=new Scanner(System.in);
int N=scn.nextInt();
int[] inputArray= new int[N];
System.out.println("Enter Integer Array Elements");
int i;
for(i=0;i<N;i++){
inputArray[i]=scn.nextInt();
}
System.out.println("Enter D:");
int D=scn.nextInt();
printNumbers(inputArray, D);
}
}
Since there are a million integers, time and space efficiency are important.
- One solution is to store all the integers as keys in a map (BST/hash table) for fast lookup.
- For each key c in the hash map, search for all pairs of integers (a,b) summing to d - c
- For each key b in the hash map devoid of c, recursively search for d - c - b. If such a key a exists, add (a,b,c) to the possible results.
Further optimisation -
- Use hash tables instead of binary search trees for storing keys
- Use dynamic programming to store possible pairs (a,b) for each sum
Here is the source code for the above logic in java
import java.util.Arrays;
public class ThreeElementsInArrayToSum {
static int[] input = {1,6,3,5,4,2,7,9,8};
public static void main(String[] args) {
int d = 13;
//Step1: sort the array
Arrays.sort(input);
//Step2-5: Run for loop for a and increment, decrement counters for b and c
int b = 0, c = 0;
for(int a=0; a<input.length-3; a++) {
b = a+1;
c = input.length-1;
while(b<c) {
if(input[a]+input[b]+input[c] <= d) {
System.out.println("Numbers <= " + d + " are a = " + input[a] + " b = " + input[b] + " c = " + input[c]);
b++;
c--;
}else {
c--;
}
}
}
}
}
Result of the program
Numbers <= 13 are a = 1 b = 2 c = 9
Numbers <= 13 are a = 1 b = 3 c = 8
Numbers <= 13 are a = 1 b = 4 c = 7
Numbers <= 13 are a = 1 b = 5 c = 6
Numbers <= 13 are a = 2 b = 3 c = 8
Numbers <= 13 are a = 2 b = 4 c = 7
Numbers <= 13 are a = 2 b = 5 c = 6
Numbers <= 13 are a = 3 b = 4 c = 6
True, good solution. To reduce the no of comparisons it is better to avoid the elements whose value > d.
While sorting note down the index (say x) whose value (array[x]) > d. Instead of processing complete array, we process above loop till x.
1. first loop till x-2
2. assign b from first element + 1 till x-1
3. assign c to x
Thanks Dinesh, good suggestion especially if the value of d is way smaller than the actual element values in the array.
But there is a caveat though, here you are making an additional assumption that array elements are non negative. In that case its better to state that assumption beforehand. These interviewers are smart, they usually like to corner the candidate on such smaller missed points :)
The solution is almost complete. I think u just need to handle the case when no such numbers are present that can satisfy the required condition
Almost good but... when you make d++ and c-- at the same time you can skip the correct combination as jiangok2006 noticed above.
slight fixing required.
here is a proposed fix
if(input[a]+input[b]+input[c] <= d) {
System.out.println("Numbers <= " + d + " are a = " + input[a] + " b = " + input[b] + " c = " + input[c]);
b++;
c--; //not required.
}else {
b=a+1:
c--;
}
Now try to use your algorithm for this array {3, 3, 3, 3, 3, 3, 3, 3, 3} and see what you'll get.
So your idea doesn't works.
here is corrected variant of your algorithm
import java.util.Arrays;
public class Test {
static int[] input = {1, 6, 3, 5, 4, 2, 7, 9, 8};
public static void main(String[] args) {
int d = 13;
//Step1: sort the array
Arrays.sort(input);
//Step2-5: Run for loop for a and increment, decrement counters for b and c
int a = 0, b = 0, c = 0;
int _a = 0, _b = 0, _c = 0; //for duplicate check
boolean flag = true;
for (a = 0; a <= input.length - 3; a++) {
b = a + 1;
c = input.length - 1;
while (b < c) {
if (input[a] + input[b] + input[c] <= d) {
if ((_a != input[a]) || (_b != input[b]) || (_c != input[c])) {
System.out.println("a = " + input[a] + " b = " + input[b] + " c = " + input[c]);
_a = input[a];
_b = input[b];
_c = input[c];
}
}
if (flag) {
b++;
flag = false;
} else {
c--;
flag = true;
}
}
}
}
}
It is a weird question because when d is large compared to the elements of the array the number of possible triplets are Omega(n^3), hence there cannot be any O(n^2) solution. So is the obvious solution pointed out in the earlier comments everything that there is about this problem? weird!
So let me make my point clear by means of an example: let the array be 1,2,3,...,n and let d = 3*n. Then every 3 distinct numbers a,b,c in your array is going to satisfy a+b+c < d, and there are n \choose 3 many of them which is of order O(n^3).
- Marboni July 02, 2014