CareerCup

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++) {
                    result.add(new int[]{values[i], values[j], values[k]});
                }
            }
        }
        return result;
    }
}

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

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

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

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

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

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

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

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

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

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

With the million integer numbers clue, interviewer probably mean to convey 2 points
1. They all fit in main memory (as 1 million numbers each represented using 32 bit integers in java would be 32 million bits which would be less than 1GB memory space so they would ideally fit in main memory)
2. The performance of the algorithm is very critical as the number count is very high.

O(N^3) - Simple Solution:
Simple solution is to run 3 for loops one inside another for a, b and c and in the 3rd for loop add all together to find if a+b+c<=d
Time complexity O(n^3)


Better Solution: O(nLog n + n^2)

This can be solved in O(nLog n + n^2) with the following approach.

Step1: Sort the array O(nLogn)
Step2: For the first element (a) start for loop from 0 to n-2
Step3: For the 2nd (b) and 3rd element (c), assign b to first element + 1 (till n-1) and c to n
Step4: If a + b + c <= d then return
Step5: If a + b + c > d decrement c by 1
Time complexity for step 2 to 5 is O(n^2)

Total Time complexity: O (N log N + N ^ 2)

I will post the java solution in short time.