Twitter Interview Question
Software Engineer InternsCountry: United States
convert A+B+C=D to A+B=D-C, where A,B,C,D are numbers in array.
calculate all the A+B,D-C need two double loops.
we can calculate A+B and hash it, remember to record A,B pos in array.
for each D-C, check if it exist in hash, besides the 4 pos are different.
overall complexity is O(n*n), with O(n) space.
another way is calc A+B and sort it, then for each D-C do a binary search,to find if it exist in A+B array.
public void problem1()
{
int[] arry = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
for (int i = 0; i < arry.Length -2 ; i++)
{
int frstNumberIndx = i;
int secNumberIndx = i + 1;
int trdNumberIndx = i + 2;
int sumOfAllNum = arry[frstNumberIndx] + arry[secNumberIndx] + arry[trdNumberIndx];
for (int j = 0; j < arry.Length; j++)
{
if (sumOfAllNum == arry[j])
{
Console.WriteLine(arry[frstNumberIndx] + " +" + arry[secNumberIndx] + " +" + arry[trdNumberIndx] + " =" + arry[j]);
}
}
}
}
I believe A,B,C,D need to be distinct elements here. It will fail for [-1, 0, 1, 10] because it will think -1 + 0 + 1 = 0.
It also fails to find A,B,C when they aren't consecutive: [1, 2, 3, 4, 7]. In this case it should be 1 + 2 + 4 = 7
Lets initialize an empty hash H.
In this hash, we will store sum as key and pairs of indices as value. For example. if A[1]=5 and A[3]=10. then key=15 and value= arr[pair<1,3>..]. Value is array of pairs as there could be more than one pair leading up to the same sum.
For each pair of integers in the array(2 nested for loops) do the following:
if -(A[i]+A[j]) is present in Hj], then get the value arr. Scan the array to see if there is a pair other than i,j or j,i. If there is a pair say x,y. Then A[i]+A[j]+A[x]+A[y] =0
else add A[i]+A[j] as key and a pair (i,j) as value
Just realized I solved a wrong problem. The above is for finding if sum of 2 elements in array = sum of another 2 elements in the array.
Have 2 hashes one for sum S and another for difference D.
In S, you store sum of pairs.
In D you store difference of pairs. While filling up D check if there is a entry in S, then you got a solution.
A+B+C=D is same as A+B=D-C , so there is a sum pair equal to a difference pair.
In the hash you have to store indices as value (just as mentioned above for the misunderstood problem), so you return only the indices of all 4 numbers are different.
9 -1 0 10
9 3 -4 10
-1 3 -4 0
-50 0 10 40
30 0 10 40
chris:algorithms dlzhang$ vi find4sum.java
chris:algorithms dlzhang$ vi find4sum.java
public class find4sum{
public static void main(String [] args){
int [] ia = {-100, 9, -1, 3, -4, -50, 30, 0, 10, 40};
findSum(ia);
}
public static void findSum(int [] ia){
for(int i = 0 ; i < ia.length - 3 ; i++ ){
for(int j = i + 1; j < ia.length -2; j++){
for(int m = j + 1; m < ia.length - 1; m++ ){
for(int n = m + 1; n < ia.length; n++ ){
if ( ia[i] == ia[j] + ia[m]+ia[n] ||
ia[j] == ia[i] + ia[m]+ia[n] ||
ia[m] == ia[j] + ia[i]+ia[n] ||
ia[n] == ia[j] + ia[m]+ia[i] )
System.out.println( ia[i] + " " + ia[j] + " " + ia[m] + " " + ia[n]);
}
}
}
}
}
}
// a+b+c=d
// by ma5termind
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<limits.h>
#include<cstring>
#include<cstdlib>
#include<cfloat>
#include<cassert>
#define maxm(a,b) a>b?a:b;
#define minm(a,b) a<b?a:b;
using namespace std;
//M lazy ;)
typedef long long ll;
typedef vector <int> vi;
typedef pair< int ,int > pii;
typedef istringstream iss;
typedef ostringstream oss;
typedef map<int,int> mp;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz size()
#define ln length()
#define rep(i,n) for(int i=0;i<n;i++)
#define fu(i,a,n) for(int i=a;i<=n;i++)
#define fd(i,n,a) for(int i=n;i>=a;i--)
#define all(a) a.begin(),a.end()
#define ESP (1e-9)
#define gi(n) scanf("%d",&n)
#define gl(n) cin >> n
#define pi(n) printf("%d",n)
#define pl(n) cout << n
#define ps printf(" ")
#define pn printf("\n")
#define dg(n,s); printf("%s %d",s,n)
#define imax numeric_limits<int>::max()
#define imin numeric_limits<int>::min()
#define lmax numeric_limits<ll>::max()
#define lmin numeric_limits<ll>::min()
#define traverse_map(a,b) for(mp::iterator it=a;it!=b;++it)
#define MOD 1000000007
#define MAX 1000001
#define cases() int t; cin>>t; while(t--)
// fast input function
#define getcx getchar_unlocked
// fast input function
#ifdef ONLINE_JUDGE
inline void inp( int &n )
{
n=0;
int ch=getcx();int sign=1;
while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();}
while( ch >= '0' && ch <= '9' )
n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
n=n*sign;
}
#else
inline void inp(int &n){
cin>>n;
}
#endif
int main(){
int t;
inp(t);
while(t--){
int n;
inp(n);
int i;
vi array;
rep(i,n){
int x;
inp(x);
array.pb(x);
}
sort(array.begin(),array.end());// sort
int A=0,B=0,C=0,D=0,sum;
bool flag=0;
for(int i=0;i<n&&!flag;i++)
{
for(int j=0;j<n&&!flag;j++)
{
if(i==j)
continue;
sum=array[i]-array[j];
int l,k;
for(k=0,l=n-1;!flag&&k<l;){
if(k==i||k==j){
k++;
continue;
}
if(l==i||l==j){
l--;
continue;
}
if(sum==(array[k]+array[l]))
{
D=i;
A=j;
B=l;
C=k;
flag=1;
}
else if(sum>(array[l]+array[k]))
{
k++;
}
else
{
l--;
}
// 1 2 3 4 7
//cout<<"hello"<<l<<k<<sum<<" "<<i<<" "<<j<<" "<<endl;
}
}
}
// time complexity for this is O(n^3)
if(array[A]+array[B]+array[C]==array[D])
cout<<array[A]<<" "<<array[B]<<" "<<array[C]<<" "<<array[D]<<endl;
else
cout<<"no such numbers exist"<<endl;
}
return 0;
}
int A=0,B=0,C=0,D=0,sum;
bool flag=0;
for(int i=0;i<n&&!flag;i++)
{
for(int j=0;j<n&&!flag;j++)
{
if(i==j)
continue;
sum=array[i]-array[j];
int l,k;
for(k=0,l=n-1;!flag&&k<l;){
if(k==i||k==j){
k++;
continue;
}
if(l==i||l==j){
l--;
continue;
}
if(sum==(array[k]+array[l]))
{
D=i;
A=j;
B=l;
C=k;
flag=1;
}
else if(sum>(array[l]+array[k]))
{
k++;
}
else
{
l--;
}
// 1 2 3 4 7
//cout<<"hello"<<l<<k<<sum<<" "<<i<<" "<<j<<" "<<endl;
}
}
}
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
/*
* Given an array with numbers, your task is to find 4 numbers that will satisfy this equation:
* A + B + C = D
*/
public class PrintSumCombinations2 {
static int[] a = { 1, 1, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
public static void main(String[] args) {
//Sort the array here if it not already sorted
//Arrays.sort(a);
HashSet set = new HashSet();
printCombinations(0, set, 0);
}
private static void printCombinations(int index, HashSet set, int setTotal) {
for (int i = index; i < a.length; i++) {
if (set.size() == 3 && setTotal == a[i]) {
System.out.println(set + " " + a[i]);
}
if (set.size() < 3 && !set.contains(a[i])) {
set.add(a[i]);
printCombinations(i + 1, set, setTotal + a[i]);
set.remove(a[i]);
}
}
}
}
/*
Sort the array first. And recursively call on printCombinations(int index, Set set, int setTotal)
sort Time - O(n log n)
print Combinations - O(n^2)
I used the approach similar to this - question (id =5098263317315584)
*/
I think we don't need the sorting step at all and the set can be replaced with a list so that it can handle duplicate elements as well.
public class FindFourNumbersThatAddUp {
public void printFourNumbersThatAddUp(int[] inputNumbers) {
if (inputNumbers == null) {
System.out.println("Input is null");
return;
}
if (inputNumbers.length < 4) {
System.out.println("Not enough numbers");
return;
}
findFourNumbers(inputNumbers, 0);
}
/*
* Using recursion add 3 continuous numbers and check if they match with
* numbers after. Move the starting pointer and recursively check rest of
* the numbers.
*/
private void findFourNumbers(int[] backUp, int startingPointer) {
int secondPointer = startingPointer + 1;
if (secondPointer >= backUp.length - 3) {
return;
}
int thirdPointer = secondPointer + 1;
if (thirdPointer >= backUp.length - 2) {
return;
}
for (int i = startingPointer; i < backUp.length - 3; i++) {
int sum = backUp[startingPointer] + backUp[secondPointer]
+ backUp[thirdPointer];
// check the sum starting from the first [0] number.
for (int j = 0; j < backUp.length; j++) {
if (sum == backUp[j]) {
System.out.println("Found a match : " + "A("
+ backUp[startingPointer] + ") + B("
+ backUp[secondPointer] + ") + C("
+ +backUp[thirdPointer] + ") = " + backUp[j]);
return;
}
}
}
// move the starting pointer by 1.
findFourNumbers(backUp, startingPointer + 1);
}
public static void main(String[] args) {
FindFourNumbersThatAddUp f = new FindFourNumbersThatAddUp();
// test case1
int[] fourSum1 = { 39, 0, 1, 2, 4, 5, 8, 10, 21, 139, 75, 95 };
f.printFourNumbersThatAddUp(fourSum1);
// test case2
int[] fourSum2 = { -100, 9, -1, 3, -4, -50, 30, 0, 10, 40 };
f.printFourNumbersThatAddUp(fourSum2);
// test case3
int[] fourSum3 = { 4, 1, 1, 2, 2, 3, 5, 6, 7, 8, 9, 10 };
f.printFourNumbersThatAddUp(fourSum3);
// test case4
int[] fourSum4 = { 0, 1, 2 };
f.printFourNumbersThatAddUp(fourSum4);
}
}
public class FindFourNumbersThatAddUp {
public void printFourNumbersThatAddUp(int[] inputNumbers) {
if (inputNumbers == null) {
System.out.println("Input is null");
return;
}
if (inputNumbers.length < 4) {
System.out.println("Not enough numbers");
return;
}
findFourNumbers(inputNumbers, 0);
}
/*
* Using recursion add 3 continuous numbers and check if they match with
* numbers after. Move the starting pointer and recursively check rest of
* the numbers.
*/
private void findFourNumbers(int[] backUp, int startingPointer) {
int secondPointer = startingPointer + 1;
if (secondPointer >= backUp.length - 3) {
return;
}
int thirdPointer = secondPointer + 1;
if (thirdPointer >= backUp.length - 2) {
return;
}
for (int i = startingPointer; i < backUp.length - 3; i++) {
int sum = backUp[startingPointer] + backUp[secondPointer]
+ backUp[thirdPointer];
// check the sum starting from the first [0] number.
for (int j = 0; j < backUp.length; j++) {
if (sum == backUp[j]) {
System.out.println("Found a match : " + "A("
+ backUp[startingPointer] + ") + B("
+ backUp[secondPointer] + ") + C("
+ +backUp[thirdPointer] + ") = " + backUp[j]);
return;
}
}
}
// move the starting pointer by 1.
findFourNumbers(backUp, startingPointer + 1);
}
public static void main(String[] args) {
FindFourNumbersThatAddUp f = new FindFourNumbersThatAddUp();
// test case1
int[] fourSum1 = { 39, 0, 1, 2, 4, 5, 8, 10, 21, 139, 75, 95 };
f.printFourNumbersThatAddUp(fourSum1);
// test case2
int[] fourSum2 = { -100, 9, -1, 3, -4, -50, 30, 0, 10, 40 };
f.printFourNumbersThatAddUp(fourSum2);
// test case3
int[] fourSum3 = { 4, 1, 1, 2, 2, 3, 5, 6, 7, 8, 9, 10 };
f.printFourNumbersThatAddUp(fourSum3);
// test case4
int[] fourSum4 = { 0, 1, 2 };
f.printFourNumbersThatAddUp(fourSum4);
}
}
didn't like it that much but works:
/*
Given an array with numbers, your task is to find 4 numbers that will satisfy this equation:
A + B + C = D
*/
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec {6, 1, 2, 3, 4, 5};
for(int d: vec) {
for(int a: vec) {
for(int b: vec) {
for(int c: vec) {
if((c + b + a) == d) {
// FOUND
std::cout
<< d << " = "
<< a << " + "
<< b << " + "
<< c << std::endl;
}
}
}
}
}
return 0;
}
short moification of 4SUM
- Anonymous December 11, 2013