## Google Interview Question for Software Engineer / Developers

Team: Hangouts
Country: United States
Interview Type: In-Person

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

``````package google;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;

import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;

public class SumOfThree {
@Test
public void test() {
int[][] expected = new int[][] {
{1, 2, 3},
{1, 2, 4}
};
ArrayList<int[]> actual = findTriplets(new int[]{4, 5, 6, 7, 1, 2, 3}, 7);
assertEquals(expected.length, actual.size());
for (int i = 0; i < expected.length; i++) {
assertArrayEquals(expected[i], actual.get(i));
}
}

public static ArrayList<int[]> findTriplets(int[] values, int n) {
Arrays.sort(values);

ArrayList<int[]> result = new ArrayList<int[]>();

for (int i = 0; 3 * values[i] <= n; i++) {
int maxRestOfTwo = n - values[i];
for (int j = i + 1; 2 * values[j] <= maxRestOfTwo; j++) {
int maxRestOfOne = maxRestOfTwo - values[j];
for (int k = j + 1; values[k] <= maxRestOfOne; k++) {
}
}
}
return result;
}
}``````

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

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

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

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

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

@hamoon
it's legit to define the complexity in means of d ... i.e. O(d)

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

@hamoon
It's legit to define the complexity in means of d, like O(d).
In fact, that's probably why "n" is a million in the question, and not variable ...

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

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

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

I think the million integers indicates complexity should be atmost nlogn.
Yours is way too slow O(n^3).

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

One does not simply establish the fact that complexity is restricted.

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

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

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

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

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

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

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

Seems to be a variant of the classical 3SUM problem.

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

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

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

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

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

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

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

int sum(int[] array, int target) {
int sum = 0;
for(int i = 0; i < array.length; i++) {
int left = i + 1, right = array.length - 1;
while(left < right) {
if(array[left] + array[right] + array[i] <= target) {
sum += right - left;
left++;
}
else {
right--;
}
}
}
return sum;
}

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

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!!

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

Does this satisfy the given example? 1 2 3 4 5 6 7 and d = 7

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

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

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

- minor: i or j in your code might be equal k, or equal to each other, which is wrong
- major: you need to list all possible combinations. And in case of a[i] + a[j] + a[k] <= d it might be [i, j, k] and/or [i+1, j, k] and/or [i, j + 1, k]. That gives O(N^3)

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

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;
}
AB.remove(arr[i]);
}

}``````

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

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;
}
AB.remove(arr[i]);
}

}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

/*
* 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);

}
}

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

OMG, use '{ { {' for marking your code

Comment hidden because of low score. Click to expand.
-2
of 2 vote

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

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

Correction - the above solution is for a+b+c=d and not a+b+c <= d.

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

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

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

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

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

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

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

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

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

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

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

is it not 3SUM solution?

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

The second solution is wrong. The example misses the return (1, 3, 9)

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

Almost good but... when you make d++ and c-- at the same time you can skip the correct combination as jiangok2006 noticed above.

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

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

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

Now try to use your algorithm for this array {3, 3, 3, 3, 3, 3, 3, 3, 3} and see what you'll get.

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

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

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

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

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.